Mean first-passage time for random walks on undirected networks
arXiv:1111.1500 · doi:10.1140/epjb/e2011-20834-1
Abstract
In this paper, by using two different techniques we derive an explicit formula for the mean first-passage time (MFPT) between any pair of nodes on a general undirected network, which is expressed in terms of eigenvalues and eigenvectors of an associated matrix similar to the transition matrix. We then apply the formula to derive a lower bound for the MFPT to arrive at a given node with the starting point chosen from the stationary distribution over the set of nodes. We show that for a correlated scale-free network of size with a degree distribution , the scaling of the lower bound is . Also, we provide a simple derivation for an eigentime identity. Our work leads to a comprehensive understanding of recent results about random walks on complex networks, especially on scale-free networks.
arXiv comment7 pages, no figures; definitive version published in European Physical Journal B
References in corpus (30)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Assortative mixing in networks
- Evolution of networks
- Mixing patterns in networks
- Critical phenomena in complex networks
- Breakdown of the Internet under intentional attack
- Scale-Free Networks are Ultrasmall
- Intermittent search strategies
- First-passage times in complex scale-invariant media
- Origins of fractality in the growth of complex networks
- Optimal search strategies for hidden targets
- Scaling theory of transport in complex networks
- Global mean first-passage times of random walks on complex networks
- Complex Systems: A Survey
- Exact mean first-passage time on the T-graph
- Exact solution for mean first-passage time on a pseudofractal scale-free web
- First Passage Properties of the Erdos-Renyi Random Graph
- Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
- Random Walks on deterministic Scale-Free networks: Exact results
- Determining mean first-passage time on a class of treelike regular fractals
- Trapping in complex networks
- Random walks on the Apollonian network with a single trap
- Effective target arrangement in a deterministic scale-free graph
- Trapping in scale-free networks with hierarchical organization of modularity
- Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
- Close or connected? Distance and connectivity effects on transport in networks
- Anomalous behavior of trapping on a fractal scale-free network
- Impact of degree heterogeneity on the behavior of trapping in Koch networks
- Random Walks on Complex Networks
Cited by in corpus (20)
- Random walks on weighted networks
- Random walk centrality in interconnected multilayer networks
- Long-Range Navigation on Complex Networks using Lévy Random Walks
- Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
- Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
- Random walks in modular scale-free networks with multiple traps
- Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
- Random walks on complex networks with first-passage resetting
- Random walks on complex networks under node-dependent stochastic resetting
- Fractional random walk lattice dynamics
- Origin of the hub spectral dimension in scale-free networks
- On recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
- Mean encounter times for multiple random walkers on networks
- Random walks on complex networks with multiple resetting nodes: a renewal approach
- Exact eigenvalue spectrum of a class of fractal scale-free networks
- Contact statistics in populations of noninteracting random walkers in two dimensions
- Centrality measures and opinion dynamics in two-layer networks with replica nodes
- On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival
- Characterizing network topology using first-passage analysis
- Trapping problem on star-type graphs with applications