2004/10/12 by Vishal Sood, V. Sood, S. Redner +2 · 4 citations
Biochemistry, Genetics and Molecular Biology · Mathematics · Physics and Astronomy · #Combinatorics #Complex Network Analysis Techniques #Diffusion and Search Dynamics #First-hitting-time model #Graph #Mathematical analysis #Mathematics #Monotonic function #Percolation (cognitive psychology) #Percolation threshold #Physics #Quantum mechanics #Random graph #Random walk #Statistical physics #Statistics #Stochastic processes and statistical mechanics #Traverse #cond-mat.stat-mech #math.PR
paper · pdf · doi:10.1088/0305-4470/38/1/007
published as J. Phys. A 38, 109-123 (2005) · 10 pages, 9 figures, 2-column revtex4 format
arxiv created 2004/10/12 · openalex publication_date 2004/12/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the mean time for a random walk to traverse between two arbitrary sites of the Erdős–Renyi random graph. We develop an effective medium approximation that predicts that the mean first-passage time between pairs of nodes, as well as all moments of this first-passage time, are insensitive to the fraction p of occupied links. This prediction qualitatively agrees with numerical simulations away from the percolation threshold. Near the percolation threshold, the statistically meaningful quantity is the mean transit rate, namely, the inverse of the first-passage time. This rate varies non-monotonically with p near the percolation transition. Much of this behaviour can be understood by simple heuristic arguments.