First Passage Properties of the Erdos-Renyi Random Graph

Abstract

We study the mean time for a random walk to traverse between two arbitrary sites of the Erdos-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 behavior can be understood by simple heuristic arguments.

10 pages, 9 figures, 2-column revtex4 format

References in corpus (4)

• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Scaling Properties of Random Walks on Small-World Networks
• Return times of random walk on generalized random graphs
• Random Walks on Complex Networks

Cited by in corpus (50)

• Voter Model on Heterogeneous Graphs
• Random walks and diffusion on networks
• Global mean first-passage times of random walks on complex networks
• First passage time for random walks in heterogeneous networks
• The noisy voter model on complex networks
• 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
• Characteristic times of biased random walks on complex networks
• Anomalous Transport in Complex Networks
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Exact calculations of first-passage quantities on recursive networks
• Mean first-passage time for random walks on undirected networks
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Ring structures and mean first passage time in networks
• Trapping in scale-free networks with hierarchical organization of modularity
• Random walks in modular scale-free networks with multiple traps
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Analytical results for the distribution of shortest path lengths in random networks
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• A Unified Approach to Gated Reactions on Networks
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Origin of the hub spectral dimension in scale-free networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Transport of multiple users in complex networks
• Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs
• Anomalous biased diffusion in networks
• Random walks on networks: cumulative distribution of cover time
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Exact eigenvalue spectrum of a class of fractal scale-free networks
• Anomalous electrical and frictionless flow conductance in complex networks
• Inter-arrival times of message propagation on directed networks
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Structural and temporal heterogeneities on networks
• The joint distribution of first return times and of the number of distinct sites visited by a 1D random walk before returning to the origin
• Gaussian Networks Generated by Random Walks
• First return times on sparse random graphs
• New tab page recommendations cause a strong suppression of exploratory web browsing behaviors
• On the Markov transition kernels for first-passage percolation on the ladder
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula