CS SEMINAR

Unbiased Sampling of Node Pairs over Large Graphs

Speaker
Professor Don Towsley
Department of Computer Science
University of Massachusetts

Chaired by
Dr Richard MA Tianbai, Associate Professor, School of Computing
tbma@comp.nus.edu.sg

17 Feb 2015 Tuesday, 02:00 PM to 04:00 PM

Executive Classroom, COM2-04-02

Abstract:

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 necessarily used. In this talk I focus on this problem from two perspectives, from an OSN service provider with access to the complete network and from a poor PhD student with limited access to the network. Characterizing pair relationships poses a great challenge to an OSN provider even when it possesses the complete topology. The reason is that when sampling techniques, e.g., uniform vertex sampling (UVS) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution statistics of user pairs such as 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 topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and random walks (RWs) respectively. We evaluate our methods to show their accuracy and efficiency. Finally, we apply our methods to several OSN and characterize the homophily present in each.


Biodata:

Don Towsley holds a B.A. in Physics (1971) and a Ph.D. in Computer Science (1975) from University of Texas. He is currently a Distinguished Professor at the University of Massachusetts in the Department of Computer Science. He has held visiting positions at numerous universities and research labs including University of Paris VI, IBM Research, AT&T Research, Microsoft Research, and INRIA. His research interests include networks and performance evaluation.

He currently serves as Co-Editor-in-Chief of the new ACM Transactions on Modeling and Performance Evaluation of Computing Systems (ToMPECS). He served as Editor-in-Chief of the IEEE/ACM Transactions on Networking and as an Associate Editor of Journal of the ACM, IEEE Journal of Selected Areas of Communications, IEEE Transactions on Communications, and several other editorial boards. He has served as Program Co-chair of INFOCOM 2009, Performance'02, and the joint 1992 ACM SIGMETRICS/Performance Conference as well as General Chair of COMSNETS 2012. He is a member of ACM and IEEE.

He has received numerous IEEE and ACM awards including the IEEE Communications Society 1998 William Bennett Paper Award, the 2007 IEEE Koji Kobayashi Award, the 2007 ACM SIGMETRICS Achievement Awardm, the 2008 ACM SIGCOMM Achievement Award, and the 2011 IEEE INFOCOM Achievement Award. He has also received numerous best paper awards including the IEEE Communications Society 1998 William Bennett Paper Award, a 2008 ACM SIGCOMM Test of Time Award, the 10+ Year 2010 DASFAA Best Paper Award, the 2012 ACM SIGMETRICS Test of Time Award and three ACM SIGMETRICS Best paper awards. Last, he has been elected Fellow of both the ACM and IEEE.