Sampling Node Pairs Over Large Graphs
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited
Web of Science2WOS source URL (as at 29/10/2020) Click here for the latest count

Other information
AbstractCharacterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large scale nature of such networks, it is infeasible to enumerate all user pairs and so sampling is used. In this paper, we show that it is a great challenge even for OSN service providers to characterize user pair relationships even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution of user pairs with constraints such as existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, since an unbiased sampling technique such as UVS is usually not allowed, and exploring the OSN graph topology is expensive. To address these challenges, we present asymptotically unbiased sampling methods to characterize user pair properties based on UVS and RW techniques respectively. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to two Chinese OSNs, Doudan and Xiami, and discover significant homophily is present in these two networks.
All Author(s) ListWang PH, Zhao JZ, Lui JCS, Towsley D, Guan XH
Name of Conference29th IEEE International Conference on Data Engineering (ICDE)
Start Date of Conference08/04/2013
End Date of Conference12/04/2013
Place of ConferenceBrisbane
Country/Region of ConferenceAustralia
Detailed descriptionorganized by IEEE,\n\nTo ORKTS: ICDE Conference is considered as the top tier conference by the engineering external committee
Year2013
Month1
Day1
PublisherIEEE
Pages781 - 792
ISBN978-1-4673-4908-6
eISBN978-1-4673-4909-3
ISSN1084-4627
LanguagesEnglish-United Kingdom
Web of Science Subject CategoriesComputer Science; Computer Science, Information Systems

Last updated on 2020-30-10 at 00:37