Walk, Not Wait: Faster Sampling Over Online Social Networks

In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specif-ically, unlike traditional random walk which wait for the conver-gence of sampling distribution to a predetermined target distribu-tion- a waiting process that incurs a high query cost- we de-velop WALK-ESTIMATE, which starts with a much shorter ran-dom 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 distri-bution. We present a novel backward random walk technique which provides provably unbiased estimations for the sampling probabil-ity, and demonstrate the superiority of WALK-ESTIMATE over traditional random walks through theoretical analysis and extensive experiments over real world online social networks. 1