Global mean first-passage times of random walks on complex networks
Global mean first-passage times of random walks on complex networks
复制标题
DOI：
10.1103/physreve.80.065104
复制
发表时间：
2009-12-01
影响因子：
2.4
通讯作者：
Voituriez, R.
中科院分区：
文献类型：
--
作者：
Tejedor, V.;Benichou, O.;Voituriez, R.
我们给出了一个适用于复杂网络上的一类随机游动的一般框架，它提供了随机游走者到达目标站点的平均首次通过时间的严格下界，即所谓的全局平均首次通过时间。这一界限简单地用目标处的平衡分布来表示，并且意味着GMFPT随网络规模的最小缩放。我们证明了这种可以任意慢的最小标度是在简单的条件下实现的，即随机游动在目标位置是瞬时的，并且与网络的小世界、无标度或分形性质无关。最后，由于目标的平均GMFPT满足更多的限制条件，我们提出了对特定目标的GMFPT不是网络的代表性性质。
We present a general framework, applicable to a broad class of random walks on complex networks, which provides a rigorous lower bound for the mean first-passage time of a random walker to a target site averaged over its starting position, the so-called global mean first-passage time (GMFPT). This bound is simply expressed in terms of the equilibrium distribution at the target and implies a minimal scaling of the GMFPT with the network size. We show that this minimal scaling, which can be arbitrarily slow, is realized under the simple condition that the random walk is transient at the target site and independently of the small-world, scale-free, or fractal properties of the network. Last, we put forward that the GMFPT to a specific target is not a representative property of the network since the target averaged GMFPT satisfies much more restrictive bounds.