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

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

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