direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Pan Hui's Publications

Albatross Sampling: Robust and Effective Hybrid Vertex Sampling for Social Graphs
Zitatschlüssel JCHDWVDL-ASREHVSSG-11
Autor Jin, Long and Chen, Yang and Hui, Pan and Ding, Cong and Wang, Tianyi and Vasilakos, Athanasios and Deng, Beixing and Li, Xing
Buchtitel Proceedings of ACM MobySys Workshop on Hot Topics in Planet-scale Measurements (HotPlanet '11)
Seiten 11–16
Jahr 2011
ISBN 978-1-4503-0742-0
DOI http://dx.doi.org/10.1145/2000172.2000178
Ort Washington, D.C., USA
Adresse New York, NY, USA
Monat June
Verlag ACM
Zusammenfassung 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 zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe