Estimating graph parameters with random walks

DOI10.4171/MSL/9MaRDI QIDQ2319818zbMATH OpenOpenAlexFDO

Authors Anna Ben-Hamou, Yuval Peres, Roberto I. Oliveira

Publication date 20 August 2019

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.00869

zbMATH Keywords

graph inferenceintersections of random walks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Markov processes: estimation; hidden Markov models (62M05)

Abstract: 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 $Oleft(t_{mathrmrel}^{3/4}sqrtm/dight)$ steps, where $t_{mathrmrel}$ 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 $Oleft(t_{mathrmunif}+t_{mathrmrel}^{5/6}sqrtnight)$, where $n$ is the number of vertices and $t_{mathrmunif}$ is the uniform mixing time on $G$. The number of vertices $n$ can then be estimated up to a bounded factor in an additional $Oleft(t_{mathrmunif}fracmnight)$ 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.

Review text

Summary: 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.

Recommendations

• Estimating graph parameters via random walks with restarts
• scientific article; zbMATH DE number 878897
• Fast low-cost estimation of network properties using random walks
• A Chernoff Bound for Random Walks on Expander Graphs
• Fast Low-Cost Estimation of Network Properties Using Random Walks

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• Brief announcement: How large is your graph?
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Distributed random walks
• Estimating graph parameters via random walks with restarts
• Estimating sizes of social networks via biased sampling
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Intersection and mixing times for reversible chains
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Sharp bounds on random walk eigenvalues via spectral embedding
• The probability that a random multigraph is simple
• Waiting for a Bat to Fly By (in Polynomial Time)

Cited in

(8)

• Fast low-cost estimation of network properties using random walks
• scientific article; zbMATH DE number 1743766 (Why is no real title available?)
• Estimating graph parameters via random walks with restarts
• Moment-Based Estimation of Stochastic Kronecker Graph Parameters
• Fast Low-Cost Estimation of Network Properties Using Random Walks
• How large is your graph?
• Structural results for the tree builder random walk
• Reconstruction of graphs based on random walks

This page was built for publication: Estimating graph parameters with random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319818)