Graduation Semester and Year




Document Type


Degree Name

Master of Science in Computer Science


Computer Science and Engineering

First Advisor

Gautam Das


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.


Computer Sciences | Physical Sciences and Mathematics


Degree granted by The University of Texas at Arlington