Accessibility Tools

Web Accessibility plugin by DJ-Extensions.com

Ciclo de Seminários do PESC

Sampling Node Pairs in Large Graphs

Don Towsley, Distinguished University Professor, University of Massachusetts (UMass), Amherst, EUA
19 de agosto às 11h

Resumo - Slides

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 suspicious BBN summer intern 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 OSNs and characterize the homophily present in each.

Biografia resumida

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 numerous journals. He has served as Program Co-chair of INFOCOM 2009, Performance 2002, 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 2007 IEEE Koji Kobayashi Award and several achievement award. He has also received numerous best paper awards including the IEEE Communications Society 1998 William Bennett Paper Award, several test of time awards and conference best paper awards. Last, he has been elected Fellow of both the ACM and IEEE.

Topo