TY - GEN
T1 - Faster random walks by rewiring online social networks on-the-fly
AU - Zhou, Zhuojie
AU - Zhang, Nan
AU - Gong, Zhiguo
AU - Das, Gautam
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - Many online social networks feature restrictive web interfaces which only allow the query of a user's local neighborhood through the interface. To enable analytics over such an online social network through its restrictive web interface, many recent efforts reuse the existing Markov Chain Monte Carlo methods such as random walks to sample the social network and support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required (i.e., a long "mixing time") for a random walk to reach a desired (stationary) sampling distribution. In this paper, we consider a novel problem of enabling a faster random walk over online social networks by "rewiring" the social network on-the-fly. Specifically, we develop Modified TOpology (MTO)-Sampler which, by using only information exposed by the restrictive web interface, constructs a "virtual" overlay topology of the social network while performing a random walk, and ensures that the random walk follows the modified overlay topology rather than the original one. We show that MTO-Sampler not only provably enhances the efficiency of sampling, but also achieves significant savings on query cost over real-world online social networks such as Google Plus, Epinion etc.
AB - Many online social networks feature restrictive web interfaces which only allow the query of a user's local neighborhood through the interface. To enable analytics over such an online social network through its restrictive web interface, many recent efforts reuse the existing Markov Chain Monte Carlo methods such as random walks to sample the social network and support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required (i.e., a long "mixing time") for a random walk to reach a desired (stationary) sampling distribution. In this paper, we consider a novel problem of enabling a faster random walk over online social networks by "rewiring" the social network on-the-fly. Specifically, we develop Modified TOpology (MTO)-Sampler which, by using only information exposed by the restrictive web interface, constructs a "virtual" overlay topology of the social network while performing a random walk, and ensures that the random walk follows the modified overlay topology rather than the original one. We show that MTO-Sampler not only provably enhances the efficiency of sampling, but also achieves significant savings on query cost over real-world online social networks such as Google Plus, Epinion etc.
UR - http://www.scopus.com/inward/record.url?scp=84881320115&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84881320115&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2013.6544873
DO - 10.1109/ICDE.2013.6544873
M3 - Conference contribution
AN - SCOPUS:84881320115
SN - 9781467349086
T3 - Proceedings - International Conference on Data Engineering
SP - 769
EP - 780
BT - ICDE 2013 - 29th International Conference on Data Engineering
T2 - 29th International Conference on Data Engineering, ICDE 2013
Y2 - 8 April 2013 through 11 April 2013
ER -