Mean first-passage time for random walks in general graphs with a deep trap

Abstract

We provide an explicit formula for the global mean first-passage time (GMFPT) for random walks in a general graph with a perfect trap fixed at an arbitrary node, where GMFPT is the average of mean first-passage time to the trap over all starting nodes in the whole graph. The formula is expressed in terms of eigenvalues and eigenvectors of Laplacian matrix for the graph. We then use the formula to deduce a tight lower bound for the GMFPT in terms of only the numbers of nodes and edges, as well as the degree of the trap, which can be achieved in both complete graphs and star graphs. We show that for a large sparse graph the leading scaling for this lower bound is proportional to the system size and the reciprocal of the degree for the trap node. Particularly, we demonstrate that for a scale-free graph of size $N$ with a degree distribution $P(d)\sim d^{-\gamma }$ characterized by $\gamma$, when the trap is placed on a most connected node, the dominating scaling of the lower bound becomes $N^{1-1/\gamma }$, which can be reached in some scale-free graphs. Finally, we prove that the leading behavior of upper bounds for GMFPT on any graph is at most $N^3$ that can be reached in the bar-bell graphs. This work provides a comprehensive understanding of previous results about trapping in various special graphs with a trap located at a specific location.

Definitive version accepted for publication in The Journal of Chemical Physics

References in corpus (29)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Hierarchical organization of modularity in metabolic networks
• Critical phenomena in complex networks
• Self-similarity of complex networks
• Breakdown of the Internet under intentional attack
• First-passage times in complex scale-invariant media
• Origins of fractality in the growth of complex networks
• Theory of resistor networks: The two-point resistance
• Global mean first-passage times of random walks on complex networks
• 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
• Coherent exciton transport in dendrimers and continuous-time quantum walks
• Random Walks on deterministic Scale-Free networks: Exact results
• Exact calculations of first-passage quantities on recursive networks
• 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
• Trapping in dendrimers and regular hyperbranched polymers
• 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
• Random walks in modular scale-free networks with multiple traps
• Role of fractal dimension in random walks on scale-free networks
• Anomalous behavior of trapping on a fractal scale-free network
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• Complete spectrum of stochastic master equation for random walks on treelike fractals

Cited by in corpus (13)

• Random walks on weighted networks
• Cover time for random walks on arbitrary 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
• Controlling the efficiency of trapping in treelike fractals
• Generalization of the small-world effect on a model approaching the Erdős-Rényi random graph
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• Thermodynamic Characterization of Synchronization-Optimized Oscillator-Networks
• Unexpected advantages of exploitation for target searches in complex networks
• Controlling the shape of small clusters with and without macroscopic fields