Faster Sampling Over Theoritical And Online Social Networks

Abstract

Online social networks have become very popular recently and are used bymillions of users. Researchers increasingly want to leverage the rich variety ofinformation available. However, social networks often feature a web interface that onlyallows local-neighborhood queries - i.e., given a user of the online social network asinput, the system returns the immediate neighbors of the user. Additionally, they alsohave rate limits that restrict the number of queries issued over a given time period. Theserestrictions make third party analytics extremely challenging. The traditional approach ofusing random walks is not effective as they require significant burn-in period before theirstationary distribution converges to target distribution. In this thesis, we build a prototypesystem SN-WALK-ESTIMATER that starts with a much shorter random walk and usesacceptance-rejection sampling to get samples according to a desired distribution. Usingonly minimal information about the graph such as diameter, SN-WALK-ESTIMATERproduces high quality samples with a much lower query cost. We test the system overseveral theoretical graph families and real world social networks.