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

O. C. Martin ^1, 2, P. Sulc ¹

Physical Review E: Statistical, Nonlinear, and Soft Matter Physics 81 (2009) 031111

We consider random walks on random graphs, focusing on return probabilities and hitting times for sparse Erdos-Renyi graphs. We show how to solve for the distribution of these quantities in the thermodynamic limit and we find that these distributions exhibit structures on all scales.

• 1. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
  CNRS : UMR8626 – Université Paris XI – Paris Sud
• 2. Génétique Végétale (GV),
  CNRS : UMR8120 – Institut national de la recherche agronomique (INRA) : UMR0320 – Université Paris XI – Paris Sud – Institut National Agronomique Paris-Grignon