Proceedings of the VLDB Endowment · 2015 · 31 citations · 34 references
ComputingData ScienceDistributed SystemsQueuing TheoryStatisticsMonte Carlo SimulationRandom WalksSampling MethodsSampling TechniquesSampling TheorySocial Network AnalysisNetwork SamplingRandom Sampling AlgorithmsRandom Walk AlgorithmsRandom Walk ModelsRandom Walks On NetworksRejection SamplingSampling
In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specifically, unlike traditional random walks 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.
34
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
What is Twitter, a social network or a news media?
Haewoon Kwak, Changhyun Lee, Hosung Park et al. · 2010 · 6.7K citations · Full text
Measurement and analysis of online social networks
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi et al. · 2007 · 3.1K citations
Practical Markov Chain Monte Carlo
Charles J. Geyer · Statistical Science · 1992 · 2.1K citations
Engineering, Mathematics, Statistics +16