Estimating graph parameters with random walks
Anna Ben-Hamou
Sorbonne Université, Paris, FranceRoberto I. Oliveira
Instituto de Matemática Pura e Aplicada, Rio de Janeiro, BrazilYuval Peres
Microsoft Research, Redmond, USA
![Estimating graph parameters with random walks cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fserial-issues%2Fcover-msl-volume-1-issue-3.png&w=3840&q=90)
Abstract
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