Princeton University

School of Engineering & Applied Science

Community Detection in Networks: Algorithms, Complexity, and Information Limits

Jiaming Xu, UC Berkeley
E-Quad, B205
Tuesday, February 23, 2016 - 4:30pm

Many datasets can be viewed as networks where nodes represent objects and edges encode pairwise interactions between objects. An interesting problem is to identify communities consisting of similar objects from observation of the network topology. The problem is popularly known as community detection, and has found numerous applications such as recommending friends in online social networks, predicting user preferences in recommender systems, and discovering gene or protein functions in biology. Learning communities in a large-scale network is both statistically and computationally challenging, and many different algorithms have been proposed over the years. Nevertheless, it remains unclear when it is computationally feasible to infer the communities. In the first part of the talk, I will present our recent progress on understanding the information-theoretic limits and computation limits for community detection under the stochastic block model (SBM). In particular, sharp performance characterizations of two computationally efficient methods: belief propagation (BP) and semidefinite programming (SDP) relaxation will be given. However, the capability for modeling real-world networks by SBM is limited by its assumption that all nodes in the same community are statistically equivalent with identical expected degrees. In the second part of the talk, I will move beyond this simple model, and introduce a new community detection methodology by leveraging the idea of SDP relaxations, and demonstrate its effectiveness in both theoretical guarantees and real-data applications. This is based on joint work with Bruce Hajek and Yihong Wu from UIUC, Yudong Chen from Cornell, and Xiaodong Li from UC Davis.
Jiaming Xu received the B.E. degree from Tsinghua University in 2009, the M.S. degree from UT-Austin in 2011, and the Ph.D. degree from UIUC in 2014 under the supervision of Prof. Bruce Hajek, all in electrical and computer engineering. He is a research fellow in the Simons Institute for the Theory of Computing at UC Berkeley, supported by a Simons-Berkeley Research Fellowship, in Spring 2016. He was a postdoctoral fellow with Department of Statistics, The Wharton School, University of Pennsylvania, in 2015. His research interests are in network science, high-dimensional statistics, information theory, optimization, machine learning, game theory, communications, and networking.