Mean first-passage time for random walks on undirected networks

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 $N$ with a degree distribution $P(d)\sim d^{-\gamma }$, the scaling of the lower bound is $N^{1-1/\gamma }$. 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.

7 pages, no figures; definitive version published in European Physical Journal B

References in corpus (15)

• Critical phenomena in complex networks
• Intermittent search strategies
• First-passage times in complex scale-invariant media
• Scaling theory of transport in 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
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• 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
• 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