# Walk, Not Wait: Faster Sampling Over Online Social Networks

arXiv: https://arxiv.org/abs/1410.7833 · HTML: https://mlsanity.com/paper/1410.7833/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2014.

## Built on by (most cited first, 1 of 1)

- [Smart Crawling: A New Approach toward Focus Crawling from Twitter](https://mlsanity.com/paper/2110.06022/) (2021)

## Abstract (arXiv)

In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specifically, unlike traditional random walk which wait for the convergence of sampling distribution to a predetermined target distribution - a waiting process that incurs a high query cost - we develop WALK-ESTIMATE, which starts with a much shorter random walk, and then proactively estimate the sampling probability for the node taken before using acceptance-rejection sampling to adjust the sampling probability to the predetermined target distribution. We present a novel backward random walk technique which provides provably unbiased estimations for the sampling probability, and demonstrate the superiority of WALK-ESTIMATE over traditional random walks through theoretical analysis and extensive experiments over real world online social networks.