TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

Albatross Sampling: Robust and Effective Hybrid Vertex Sampling for Social Graphs
Author Jin, Long and Chen, Yang and Hui, Pan and Ding, Cong and Wang, Tianyi and Vasilakos, Athanasios and Deng, Beixing and Li, Xing
Title of Book Proceedings of ACM MobySys Workshop on Hot Topics in Planet-scale Measurements (HotPlanet '11)
Pages 11–16
Year 2011
ISBN 978-1-4503-0742-0
DOI http://dx.doi.org/10.1145/2000172.2000178
Location Washington, D.C., USA
Address New York, NY, USA
Month June
Publisher ACM
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.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe