Unbiased Sampling Method Analysis on Online Social Network

DOI

10.2991/icmeit-19.2019.39How to use a DOI?

Keywords

OSN, Unbiased Sampling, online convergence test.

Abstract

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.

Copyright

© 2019, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

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  - Proceedings of the 3rd International Conference on Mechatronics Engineering and Information Technology (ICMEIT 2019)
PB  - Atlantis Press
SP  - 224
EP  - 230
SN  - 2352-538X
UR  - https://doi.org/10.2991/icmeit-19.2019.39
DO  - 10.2991/icmeit-19.2019.39
ID  - Wang2019/04
ER  -