Sampling Theory of Large Graphs

Add to your list(s) Download to your calendar using vCal

• John C.S. Lui (Chinese University of Hong Kong)
• Friday 04 July 2014, 11:00-12:00
• FW26, Computer Laboratory, William Gates Builiding.

If you have a question about this talk, please contact Eiko Yoneki.

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 talk, we show that it is a great challenge even for OSN service providers to characterize user pair relationships even when they posses 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.

Bio: John C.S. Lui was born in Hong Kong and is currently a full professor in the Department of Computer Science & Engineering at The Chinese University of Hong Kong. He received his Ph.D. in Computer Science from UCLA . After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various research and development projects on file systems and parallel I/O architectures. He later joined the Department of Computer Science and Engineering at The Chinese University of Hong Kong. His current research interests are in Internet, network sciences with large data implications (e.g., online social networks, large scale data analytics,..etc), network/system security (e.g., cloud security, mobile security, ...etc), network economics, large scale distributed systems and performance evaluation theory. John served as the chairman of the CSE Department from 2005-2011. He received various departmental teaching awards and the CUHK Vice-Chancellor’s Exemplary Teaching Award. John received the CUHK Faculty of Engineering Research Excellence Award (2011-2012). John is a co-recipient of the IFIP WG 7 .3 Performance 2005 and IEEE /IFIP NOMS 2006 Best Student Paper Awards. He is an elected member of the IFIP WG 7 .3, Fellow of ACM , Fellow of IEEE , Senior Research Fellow of the Croucher Foundation and is currently the chair of the ACM SIGMETRICS . His personal interests include films and general reading.

This talk is part of the Computer Laboratory Systems Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• CL's SRG seminar
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Systems Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• FW26, Computer Laboratory, William Gates Builiding
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.