Global mean first-passage times of random walks on complex networks
Top Cited Papers
- 29 December 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 80 (6), 065104
- https://doi.org/10.1103/physreve.80.065104
Abstract
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.Keywords
This publication has 36 references indexed in Scilit:
- Critical phenomena in complex networksReviews of Modern Physics, 2008
- Random walks on complex treesPhysical Review E, 2008
- Laplacian spectra of, and random walks on, complex networks: Are scale-free architectures really important?Physical Review E, 2008
- Origins of fractality in the growth of complex networksNature Physics, 2006
- What is special about diffusion on scale-free nets?New Journal of Physics, 2005
- Self-similarity of complex networksNature, 2005
- Random Walks on Complex NetworksPhysical Review Letters, 2004
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Diameter of the World-Wide WebNature, 1999
- Collective dynamics of ‘small-world’ networksNature, 1998