Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs

Abstract

We consider random walks on random graphs, focusing on return probabilities and hitting times for sparse Erdos-Renyi graphs. Using the tree approach which is expected to be exact in the large graph limit, we show how to solve for the distribution of these quantities and we find that these distributions exhibit a form of self-similarity.

changes in text, new figures

References in corpus (5)

• Optimal search strategies for hidden targets
• Sparse random matrices: the eigenvalue spectrum revisited
• First Passage Properties of the Erdos-Renyi Random Graph
• Ring structures and mean first passage time in networks
• Random Walks on Complex Networks

Cited by in corpus (8)

• Analytical results for the distribution of first return times of random walks on random regular graphs
• Analysis of fluctuations in the first return times of random walks on regular branched 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
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• Temporal-varying failures of nodes in networks
• 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