The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Mathematical Statistics and Learning


Full-Text PDF (326 KB) | Metadata | Table of Contents | MSL summary
Online access to the full text of Mathematical Statistics and Learning is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
Volume 1, Issue 3/4, 2018, pp. 375–399
DOI: 10.4171/MSL/9

Published online: 2019-05-18

Estimating graph parameters with random walks

Anna Ben-Hamou[1], Roberto I. Oliveira[2] and Yuval Peres[3]

(1) Sorbonne Université, Paris, France
(2) Instituto de Matem√°tica Pura e Aplicada, Rio de Janeiro, Brazil
(3) Microsoft Research, Redmond, USA

An algorithm observes the trajectories of random walks over an unknown graph $G$, starting from the same vertex $x$, as well as the degrees along the trajectories. For all finite connected graphs, one can estimate the number of edges $m$ up to a bounded factor in $O(t_{\mathrm {rel}}^{3/4}\sqrt{m/d}\,)$ steps, where $t_{\mathrm {rel}}$ is the relaxation time of the lazy random walk on $G$ and $d$ is the minimum degree in $G$. Alternatively, $m$ can be estimated in $O(t_{\mathrm {unif}} + t_{\mathrm {rel}}^{5/6}\sqrt{n}\,)$, where $n$ is the number of vertices and $t_{\mathrm {unif}}$ is the uniform mixing time on $G$. The number of vertices $n$ can then be estimated up to a bounded factor in an additional $O(t_{\mathrm {unif}}\frac{m}{n})$ steps. Our algorithms are based on counting the number of intersections of random walk paths $X,Y$, i.e. the number of pairs $(t,s)$ such that $X_t=Y_s$. This improves on previous estimates which only consider collisions (i.e.~times $t$ with $X_t=Y_t$). 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 $m$ or the mixing time of $G$, we can compute the "other parameter" with a self-stopping algorithm.

Keywords: Graph inference, intersections of random walks

Ben-Hamou Anna, Oliveira Roberto, Peres Yuval: Estimating graph parameters with random walks. Math. Stat. Learn. 1 (2018), 375-399. doi: 10.4171/MSL/9