Asymptotic analysis of first passage time in complex networks

Abstract

The first passage time (FPT) distribution for random walk in complex networks is calculated through an asymptotic analysis. For network with size $N$ and short relaxation time $\tau \ll N$, the computed mean first passage time (MFPT), which is inverse of the decay rate of FPT distribution, is inversely proportional to the degree of the destination. These results are verified numerically for the paradigmatic networks with excellent agreement. We show that the range of validity of the analytical results covers networks that have short relaxation time and high mean degree, which turn out to be valid to many real networks.

6 pages, 4 figures, 1 table

References in corpus (10)

• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Biased random walks on complex networks: the role of local navigation rules
• Fractality in complex networks: critical and supercritical skeletons
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Occupation times of random walks in confined geometries: From random trap model to diffusion limited reactions
• Spectral Coarse Graining and Synchronization in Oscillator Networks
• Ring structures and mean first passage time in networks
• Spectral densities of scale-free networks
• Random Walks on Complex Networks

Cited by in corpus (11)

• Random walks and diffusion on networks
• Random walks on weighted networks
• Characteristic times of biased random walks on complex networks
• Cover time for random walks on arbitrary complex networks
• Mean-field theory for double-well systems on degree-heterogeneous networks
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Unexpected advantages of exploitation for target searches in complex networks
• Metapopulation models imply non-Poissonian statistics of interevent times
• Temporal-varying failures of nodes in networks
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula