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


全文

引用次數

其它資訊
摘要Characterizing 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.
著者Wang PH, Zhao JZ, Lui JCS, Towsley D, Guan XH
會議名稱29th IEEE International Conference on Data Engineering (ICDE)
會議開始日08.04.2013
會議完結日12.04.2013
會議地點Brisbane
會議國家/地區澳大利亞
詳細描述organized by IEEE,\n\nTo ORKTS: ICDE Conference is considered as the top tier conference by the engineering external committee
出版年份2013
月份1
日期1
出版社IEEE
頁次781 - 792
國際標準書號978-1-4673-4908-6
電子國際標準書號978-1-4673-4909-3
國際標準期刊號1084-4627
語言英式英語
Web of Science 學科類別Computer Science; Computer Science, Information Systems

上次更新時間 2020-20-10 於 01:19