2009/02/28 by Olivier Martin, O. C. Martin, Petr Šulc +1
Computer Science · Mathematics · Physics and Astronomy · #Bayesian Methods and Mixture Models #Combinatorics #Complex Network Analysis Techniques #Discrete mathematics #Graph #Hitting time #Limit (mathematics) #Mathematical analysis #Mathematics #Random graph #Random walk #Statistics #Stochastic processes and statistical mechanics #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.81.031111
published as Physical Review E, vol. 81, Issue 3, id. 031111, March 2010 · changes in text, new figures
openalex publication_date 2010/03/11 · arxiv created 2010/09/08 · arxiv updated 2015/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider random walks on random graphs, focusing on return probabilities and hitting times for sparse Erdös-Rényi 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.