Graduation Semester and Year

2015

Language

English

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science and Engineering

First Advisor

Gautam Das

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.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS