| Author |
Jin, Long and Chen, Yang and Hui, Pan and Ding, Cong and Wang, Tianyi and Vasilakos, Athanasios and Deng, Beixing and Li, Xing |
| Abstract |
Nowadays, Online Social Networks (OSNs) become dramatically popular and the study of social graph attracts the interests of a large number of researchers. One critical challenge is the huge size of the social graph, which makes the graph analyzing or even the data crawling incredibly time consuming, and sometimes impossible to do to completion. Thus, graph sampling algorithms have been introduced to obtain a smaller subgraph which reflects the properties of the original huge graph well. Breadth-First Sampling (BFS) is very widely used in graph sampling but it is biased towards high-degree vertices during the process of sampling. Besides, Metropolis-Hasting Random Walk (MHRW), which is proposed to get unbiased samples of the social graph, requires the graph to be well connected. In this paper, we propose a vertex sampling algorithm, so-called Albatross Sampling (AS), which introduces adaptive random jump strategy into MHRW during the sampling process. The embedded random jump makes the sampling procedure more flexible and avoids being trapped in some locally well connected part. According to our evaluation, we find that no matter using tightly or loosely connected graphs, AS performs significantly better than MHRW and BFS. On one hand, AS estimates the degree distribution with much lower Normalized Mean Square Error (NMSE) by consuming the same resource budget. One the other hand, to get an acceptable estimation of the degree distribution, AS requires much fewer resource budget. |
