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.

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)