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

Area of Science:

• Graph theory
• Statistical physics
• Network science

Background:

• Random walks are fundamental processes on graphs.
• Understanding first-passage time is crucial for analyzing diffusion and search processes.
• Previous studies often focused on specific graph structures or trap locations.

Purpose of the Study:

• To derive an explicit formula for the global mean first-passage time (GMFPT) in general graphs with a fixed trap.
• To establish tight lower and upper bounds for GMFPT.
• To analyze GMFPT scaling in various graph types, including sparse and scale-free networks.

Main Methods:

• Derivation of GMFPT formula using eigenvalues and eigenvectors of the graph Laplacian matrix.
• Analysis of the formula to deduce lower bounds based on graph properties (nodes, edges, trap degree).
• Investigation of GMFPT scaling in complete, star, sparse, scale-free, and bar-bell graphs.

Main Results:

• An explicit formula for GMFPT is provided in terms of graph Laplacian properties.
• A tight lower bound for GMFPT is established, scaling with system size and inverse trap degree for sparse graphs.
• For scale-free graphs, the lower bound scales as N(1-1/γ) when the trap is on the most connected node.
• An upper bound for GMFPT is shown to be at most N(3).

Conclusions:

• The derived formula offers a unified framework for understanding trapping phenomena in diverse graphs.
• The study provides precise scaling laws for GMFPT in different network architectures.
• This work enhances the comprehension of first-passage times in the context of network processes and search strategies.