Random Walks on Complex Networks
Top Cited Papers
- 18 March 2004
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 92 (11), 118701
- https://doi.org/10.1103/physrevlett.92.118701
Abstract
We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality , which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.
Keywords
Other Versions
This publication has 23 references indexed in Scilit:
- Exact scaling properties of a hierarchical network modelPhysical Review E, 2003
- Stability of shortest paths in complex networks with random edge weightsPhysical Review E, 2002
- Optimal Network Topologies for Local Search with CongestionPhysical Review Letters, 2002
- First- and second-order phase transitions in scale-free networksPhysical Review E, 2002
- Ising model on networks with an arbitrary distribution of connectionsPhysical Review E, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Adaptive random walks on the class of Web graphsZeitschrift für Physik B Condensed Matter, 2001
- Scientific collaboration networks. II. Shortest paths, weighted networks, and centralityPhysical Review E, 2001
- Resilience of the Internet to Random BreakdownsPhysical Review Letters, 2000
- Relaxation properties of small-world networksPhysical Review E, 2000