Unbiased Sampling Method Analysis on Online Social Network
- Siyao Wang, Bo Liu, Jiajun Zhou, Guangpeng Li
- Corresponding Author
- Siyao Wang
Available Online April 2019.
- https://doi.org/10.2991/icmeit-19.2019.39How to use a DOI?
- OSN, Unbiased Sampling, online convergence test.
- The study of social graph structure has become extremely popular with the development of the Online Social Network (OSN). The main bottleneck is that the large account of social data makes it difficult to obtain and analyze, which consume extensive bandwidth, storage and computing resources. Thus unbiased sampling of OSN makes it possible to get accurate and representative properties of OSN graph. The widely used algorithm, Breadth-First Sampling (BFS)and Random Walking (RW) both are proved that there exists substantial bias towards high-degree nodes. By contrast the Metropolis-Hasting random walking (MHRW), re-weighted random walking (RWRW) and the unbiased sampling with reduced self-loop (USRS)which are all based on Markov Chain Monte Carlo(MCMC) method could produce approximate uniform samples. In this paper, we analyze the similarities and differences among the four algorithms, and show the performance of unbiased estimation and crawling efficient on the data set of Facebook. In addition, we provide formal convergence test to determine when the crawling process attain an equilibrium state and the number of nodes should be discarded.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
TY - CONF AU - Siyao Wang AU - Bo Liu AU - Jiajun Zhou AU - Guangpeng Li PY - 2019/04 DA - 2019/04 TI - Unbiased Sampling Method Analysis on Online Social Network BT - 3rd International Conference on Mechatronics Engineering and Information Technology (ICMEIT 2019) PB - Atlantis Press SN - 2352-538X UR - https://doi.org/10.2991/icmeit-19.2019.39 DO - https://doi.org/10.2991/icmeit-19.2019.39 ID - Wang2019/04 ER -