Department of Engineering Science, University of Oxford, Oxford, United Kingdom.
Phys Rev E. 2017 Sep;96(3-1):032309. doi: 10.1103/PhysRevE.96.032309. Epub 2017 Sep 12.
In a wide range of complex networks, the links between the nodes are temporal and may sporadically appear and disappear. This temporality is fundamental to analyzing the formation of paths within such networks. Moreover, the presence of the links between the nodes is a random process induced by nature in many real-world networks. In this paper, we study random temporal networks at a microscopic level and formulate the probability of accessibility from a node i to a node j after a certain number of discrete time units T. While solving the original problem is computationally intractable, we provide an upper and two lower bounds on this probability for a very general case with arbitrary time-varying probabilities of the links' existence. Moreover, for a special case where the links have identical probabilities across the network at each time slot, we obtain the exact probability of accessibility between any two nodes. Finally, we discuss scenarios where the information regarding the presence and absence of links is initially available in the form of time duration (of presence or absence intervals) continuous probability distributions rather than discrete probabilities over time slots. We provide a method for transforming such distributions to discrete probabilities, which enables us to apply the given bounds in this paper to a broader range of problem settings.
在广泛的复杂网络中，节点之间的联系是时间相关的，可能会偶尔出现和消失。这种暂时性对于分析这些网络中路径的形成至关重要。此外，在许多现实网络中，节点之间的联系的存在是由自然引起的随机过程。在本文中，我们从微观层面研究随机时间网络，并制定了在经过一定数量的离散时间单位 T 后，从节点 i 到节点 j 的可访问性概率。虽然解决原始问题在计算上是不可行的，但我们针对非常一般的情况，即链接存在的时间变化概率任意，为这个概率提供了一个上界和两个下界。此外，对于链接在每个时隙在整个网络上具有相同概率的特殊情况，我们获得了任意两个节点之间的可访问性概率的精确值。最后，我们讨论了这样的情况：关于链接存在与否的信息最初是以时间持续时间（存在或不存在间隔）连续概率分布的形式存在，而不是随时间变化的离散概率。我们提供了一种将这种分布转换为离散概率的方法，这使我们能够将本文中的给定界限应用于更广泛的问题设置。
