Estimating and Sampling Graphs with Multidimensional Random Walks
arXiv:1002.1751
Abstract
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 -dimensional random walk that uses 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.
References in corpus (4)
Cited by in corpus (28)
- A Walk in Facebook: Uniform Sampling of Users in Online Social Networks
- Network Sampling: From Static to Streaming Graphs
- Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling
- Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks
- Online Myopic Network Covering
- Waddling Random Walk: Fast and Accurate Mining of Motif Statistics in Large Graphs
- Social Sensor Placement in Large Scale Networks: A Graph Sampling Perspective
- Practical Characterization of Large Networks Using Neighborhood Information
- Characterizing Directed and Undirected Networks via Multidimensional Walks with Jumps
- Sampling-based Estimation of In-degree Distribution with Applications to Directed Complex Networks
- Sampling Content Distributed Over Graphs
- Coarse-Grained Topology Estimation via Graph Sampling
- Towards Unbiased BFS Sampling
- Multigraph Sampling of Online Social Networks
- Space-Efficient Sampling from Social Activity Streams
- Walk, Not Wait: Faster Sampling Over Online Social Networks
- On sampling social networking services
- A Community-Based Sampling Method Using DPL for Online Social Network
- Sampling Online Social Networks via Heterogeneous Statistics
- Sampling Online Social Networks by Random Walk with Indirect Jumps
- 2.5K-Graphs: from Sampling to Generation
- Synthetic Generation of Social Network Data With Endorsements
- True Nonlinear Dynamics from Incomplete Networks
- Design of Efficient Sampling Methods on Hybrid Social-Affiliation Networks
- Non-Backtracking Centrality Based Random Walk on Networks
- ComPAS: Community Preserving Sampling for Streaming Graphs
- Estimation of Vertex Degrees in a Sampled Network
- Efficiently Estimating Motif Statistics of Large Networks