Walking in Facebook: A Case Study of Unbiased Sampling of OSNs

With more than 250 million active users, FaceBook (FB) is currently one of the most important online social networks. The authors' goal in this paper is to obtain a representative (unbiased) sample of Facebook users by crawling its social graph. In this quest, they consider and implement several candidate techniques. Two approaches that are found to perform well are the Metropolis-Hasting Random Walk (MHRW) and a Re-Weighted Random Walk (RWRW). Both have pros and cons, which they demonstrate through a comparison to each other as well as to the "Ground-truth" (UNI - obtained through true UNIform sampling of FB user-IDs). In contrast, the traditional Breadth-First-Search and Random Walk (without re-weighting) perform quite poorly, producing substantially biased results.

Provided by: EPFL Topic: Software Date Added: Dec 2009 Format: PDF

Download Now

Find By Topic