First passage time for random walks in heterogeneous networks
arXiv:1207.2553 · doi:10.1103/PhysRevLett.109.088701
Abstract
The first passage time (FPT) for random walks is a key indicator of how fast information diffuses in a given system. Despite the role of FPT as a fundamental feature in transport phenomena, its behavior, particularly in heterogeneous networks, is not yet fully understood. Here, we study, both analytically and numerically, the scaling behavior of the FPT distribution to a given target node, averaged over all starting nodes. We find that random walks arrive quickly at a local hub, and therefore, the FPT distribution shows a crossover with respect to time from fast decay behavior (induced from the attractive effect to the hub) to slow decay behavior (caused by the exploring of the entire system). Moreover, the mean FPT is independent of the degree of the target node in the case of compact exploration. These theoretical results justify the necessity of using a random jump protocol (empirically used in search engines) and provide guidelines for designing an effective network to make information quickly accessible.
arXiv comment5 pages, 3 figures
References in corpus (16)
- Emergence of scaling in random networks
- The diameter of the world wide web
- First-passage times in complex scale-invariant media
- Geometry-controlled kinetics
- Fractal and Transfractal Recursive Scale-Free Nets
- Global mean first-passage times of random walks on complex networks
- Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
- Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
- Exact solution for mean first-passage time on a pseudofractal scale-free web
- First Passage Properties of the Erdos-Renyi Random Graph
- Random Walks on deterministic Scale-Free networks: Exact results
- Spectral dimensions of hierarchical scale-free networks with shortcuts
- Close or connected? Distance and connectivity effects on transport in networks
- Organization of complex networks without multiple connections
- Approaching the thermodynamic limit in equilibrated scale-free networks
- Random Walks on Complex Networks
Cited by in corpus (43)
- Random walks and diffusion on networks
- Towards real-world complexity: an introduction to multiplex networks
- Random walks on weighted networks
- Characteristic times of biased random walks on complex networks
- Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
- Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
- Mean first-passage time for maximal-entropy random walks in complex networks
- Heterogeneous continuous time random walks
- Random walks on complex networks with first-passage resetting
- Scaling laws for diffusion on (trans)fractal scale-free networks
- Random walks on complex networks under node-dependent stochastic resetting
- A Unified Approach to Gated Reactions on Networks
- Controlling the efficiency of trapping in treelike fractals
- Exact results for the first-passage properties in a class of fractal networks
- Origin of the hub spectral dimension in scale-free networks
- Maximal entropy random walk improves efficiency of trapping in dendrimers
- Random walks on complex networks with multiple resetting nodes: a renewal approach
- Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
- Impact of sequential disorder on the scaling behavior of airplane boarding time
- Epidemic extinction in networks: Insights from the 12,110 smallest graphs
- Analysis of fluctuations in the first return times of random walks on regular branched networks
- Universal cover-time distribution of heterogeneous random walks
- Statistical analysis of the first passage path ensemble of jump processes
- Random walks in unweighted and weighted modular scale-free networks with a perfect trap
- Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
- Anomalous behavior of trapping in extended dendrimers with a perfect trap
- Fast Algorithm for Relaxation Processes in Big-data Systems
- Giant component in a configuration-model power-law graph with a variable number of links
- Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
- Bifractality of fractal scale-free networks
- Structural and temporal heterogeneities on networks
- Scale-free tree network with an ultra-large diameter
- Average Trapping time on the 3-dimensional 3-level Sierpinski gasket network with a set of trap nodes
- Navigation by anomalous random walks on complex networks
- The Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks
- Heterogeneous Mean First-Passage Time Scaling in Fractal Media
- Heterogeneous Network Topology Induces the Widom Line
- "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
- Random walks on stochastic uniform growth trees: Analytical formula for mean first-passage time
- Exact mean first-passage time on generalized Vicsek fractal
- First passage times of transport on planar spatial networks and their connections to off-network planar diffusion
- Diffusive search and trajectories on spatial networks: a propagator approach
- Fixation times in differentiation and evolution in the presence of bottlenecks, deserts, and oases