Plenary Speakers
Shang-Hua Teng
Computer Science Department, University of Southern California
- Title: Identification of Communities and Significant Members in Social Networks: From the Lens of Social Choice Theory and Spectral Graph Theory
- Abstract: I will discuss some recent progress in addressing two basic questions in network analysis:
- [Conceptual question]: What constitutes a community in a social network?
- [Algorithmic question]: Can we identify significant members in a network without exploring the entire network?
The journey towards understanding these two fundamental questions lead us to Social Choice Theory and Spectral Graph Theory. The talk is based on joint work with Christian Borgs, Michael Brautbar, Jennifer Chayes, and Adrian Marple. - Bio: Shang-Hua Teng is the Seeley G. Mudd Professor at the Computer Science Department, Viterbi School of Engineering, USC. Teng's main research is in algorithm design, analysis, and applications, and he holds over ten patents. He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machines Corporation, and NASA Ames Research Center. He and coauthor Dan Spielman received the Godel Prize (2008) and Fulkerson Prize (2009) for developing Smoothed Analysis. Teng is an ACM Fellow, Alfred P. Sloan Fellow, winner of Senior Xerox Award for Outstanding Faculty Research (UIUC), and NSF CAREER Award. He was recently selected by Simons Foundation as a Simons Investigator.
- Web page: http://www-bcf.usc.edu/~shanghua/
Stefano Leonardi
Department of Computer, Control and Management Engineering, Sapienza University of Rome
- Title: Similarity Ranking in Multi-categorical Bipartite Graphs
- Abstract: An important task of web usage mining is to identify users that exhibit common traits, as can be detected from the interaction with web applications. The interaction between users and applications is often represented by a large-scale bipartite graph, where the two sides of the graph represent users and items extracted from logs, and the items are labeled with an arbitrary set of category identifiers depending on the specific application. The problem has several real-world applications, including identifying competing advertisers and suggesting related queries in an online advertising system or finding users with similar interests and suggesting content to them.
In these settings, we are interested in computing on-the-fly rankings of similar actors, given an actor and an arbitrary subset of categories of interest. Two main challenges arise: First, the bipartite graphs are huge and often lopsided (e.g. the system might receive billions of queries while presenting only millions of advertisers). Second, the sheer number of possible combinations of categories prevents the pre-computation of the results for all of them.
In this talk it is presented a novel algorithmic framework that addresses both issues for the computation of several graph-theoretical similarity measures. The accuracy of the approach is shown experimentally with real-world data, using both public graphs and a very large dataset from Google AdWords.
(Based on a joint work with A. Epasto, J, Feldman, S. Lattanzi and V. Mirrokni appeared at WWW 2014.) - Bio: Stefano Leonardi is Full Professor at Sapienza University of Rome, Department of Computer and Systems Sciences, Faculty of Engineering. His research focuses on web search and data mining, large-scale complex networks, online social networks, online algorithms, algorithmic Game Theory. Stefano has served on over 40 program committees, and chaired many meetings including WAW'04 and the upcoming WWW'15. He is a Senior Research Fellow, Sapienza School for Advanced Studies, and won a Google Research Award 2012 (in Economics and Market Algorithms). He serves on the editorial board of Journal of Interconnection Networks and ACM Transactions on Algorithms.
- Web page: http://www.dis.uniroma1.it/~leon/