Estimating graph parameters with random walks

  • Anna Ben-Hamou

    Sorbonne Université, Paris, France
  • Roberto I. Oliveira

    Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brazil
  • Yuval Peres

    Microsoft Research, Redmond, USA


An algorithm observes the trajectories of random walks over an unknown graph , starting from the same vertex , as well as the degrees along the trajectories. For all finite connected graphs, one can estimate the number of edges up to a bounded factor in steps, where is the relaxation time of the lazy random walk on and is the minimum degree in . Alternatively, can be estimated in , where is the number of vertices and is the uniform mixing time on . The number of vertices can then be estimated up to a bounded factor in an additional steps. Our algorithms are based on counting the number of intersections of random walk paths , i.e. the number of pairs such that . This improves on previous estimates which only consider collisions (i.e.~times with ). We also show that the complexity of our algorithms is optimal, even when restricting to graphs with a prescribed relaxation time. Finally, we show that, given either or the mixing time of , we can compute the "other parameter" with a self-stopping algorithm.

Cite this article

Anna Ben-Hamou, Roberto I. Oliveira, Yuval Peres, Estimating graph parameters with random walks. Math. Stat. Learn. 1 (2018), no. 3/4, pp. 375–399

DOI 10.4171/MSL/9