A tale of three graphs: Sampling design on hybrid social-affiliation networks
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractRandom walk-based graph sampling methods have become increasingly popular and important for characterizing large-scale complex networks. While powerful, they are known to exhibit problems when the graph is loosely connected, which slows down the convergence of a random walk and can result in poor estimation accuracy. In this work, we observe that many graphs under study, called target graphs, usually do not exist in isolation. In many situations, a target graph is often related to an auxiliary graph and an affiliation graph, and the target graph becomes better connected when viewed from these three graphs as a whole, or what we called a hybrid social-affiliation network. This viewpoint brings extra benefits to the graph sampling framework, e.g., when directly sampling a target graph is difficult or inefficient, we can efficiently sample it with the assistance of auxiliary and affiliation graphs. We propose three sampling methods on such a hybrid social-affiliation network to estimate target graph characteristics, and conduct extensive experiments on both synthetic and real datasets, to demonstrate the effectiveness of these new sampling methods.
All Author(s) ListZhao J., Lui J.C.S., Towsley D., Wang P., Guan X.
Name of Conference2015 31st IEEE International Conference on Data Engineering, ICDE 2015
Start Date of Conference13/04/2015
End Date of Conference17/04/2015
Place of ConferenceSeoul
Country/Region of ConferenceSouth Korea
Detailed description This conference was considered as a tier-A conference venue as classified by the external visiting committee in FoE in 2011.
Volume Number2015-May
Pages939 - 950
LanguagesEnglish-United Kingdom

Last updated on 2020-22-05 at 00:47