Estimating and sampling graphs with multidimensional random walks
By Bruno Ribeiro, D. Towsley. ACM/SIGCOMM Internet Measurement Conference, 2010
367 citations recorded by the source corpus.
Estimating characteristics of large graphs via sampling is a vital part of the study of complex networks. Current sampling methods such as (independent) random vertex and random walks are useful but have drawbacks. Random vertex sampling may require too many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.
Subfields: Computational Theory and Mathematics, Mathematical Physics, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/bb6b76a319386a946b6ff46d89f70cd32e15677e
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Steven L. Brunton
- J. Nathan Kutz
- Krithika Manohar
- Athanasios V. Vasilakos
- Bingni W. Brunton
- Pan Hui
- Maizar Raissi
In Mathematical Physics
In Statistical and Nonlinear Physics
- Steven L. Brunton
- J. Nathan Kutz
- Bingni W. Brunton
- Krithika Manohar
- Maizar Raissi
- Joshua L. Proctor
- Igor Mezi'c
- G. Em Karniadakis
Citations in the corpus
- GraphSAINT: Graph Sampling Based Inductive Learning Method (2019, methodology): “In the experiments, we implement a regular random walk sampler (with r root nodes selected uniformly at random and each walker goes h hops), and also a multi-dimensional random walk sampler defined in Ribeiro & Towsley (2010).”
- Understanding user behavior in online social networks: a survey (2013, background): “Ribeiro et al. [5] show that FS is more suitable for estimating the tail of degree distribution than random vertex sampling.”
- Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known Patterns (2017, background): “Sparse sensing has additionally been explored in signal processing for sampling and estimating signals over graphs [139], [140], [141], [142].”
- Ladies First: Analyzing Gender Roles and Behaviors in Pinterest (2013, neutral): “Although the BFS technique is simple and efficient, it exhibits several well-known limitations such as the bias towards sampling high degree nodes, which may affect the degree distribution (Ribeiro and Towsley 2010; Gjoka et al. 2009).”