Towards Unbiased Sampling of Online Social Networks
Unbiased sampling of Online Social Networks (OSNs) makes it possible to get accurate statistical properties of large-scale OSNs. However, the most used sampling methods, Breadth-First-Search (BFS) and Greedy, are known to be biased towards high-degree nodes, yielding inaccurate statistical results. To give a general requirement for unbiased sampling, the authors model the crawling process as a Markov Chain and deduce a necessary and sufficient condition, which enables them to design various efficient unbiased sampling methods. To the best of their knowledge, they are among the first to give such a condition.