Proceedings of the 3rd International Conference on Mechatronics Engineering and Information Technology (ICMEIT 2019)

Unbiased Sampling Method Analysis on Online Social Network

Authors
Siyao Wang, Bo Liu, Jiajun Zhou, Guangpeng Li
Corresponding Author
Siyao Wang
Available Online April 2019.
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)

Volume Title
Proceedings of the 3rd International Conference on Mechatronics Engineering and Information Technology (ICMEIT 2019)
Series
Advances in Computer Science Research
Publication Date
April 2019
ISBN
978-94-6252-708-9
ISSN
2352-538X
DOI
10.2991/icmeit-19.2019.39How to use a DOI?
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/).

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  - 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  -