Fundamental Limits of Community Detection in Stochastic Block Models

Tuesday, April 28, 2015 - 4:00pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Emmanuel Abbe

Affiliation

Princeton

Building and Room Number

32-155

Abstract

Abstract: With the abundance of networks and data sets organized as similarity graphs, community detection is a fast growing field. Yet the methodologies are still mainly driven by heuristics. This talk focuses on a popular network model called the stochastic block model. It is shown that for this model, community detection has a fundamental limit, which we characterize in terms of an f-divergence. This defines a notion of clustering capacity analog to Shannon’s channel capacity. We then show that the limit can be efficiently achieved, in fact, with a quasi-linear time algorithm. Joint work with Colin Sandon arXiv:1503.00609.

Biography

Emmanuel Abbe received his Ph.D. from the EECS Department at MIT and his M.S. from the Mathematics Department at EPFL. He is now an assistant professor at Princeton University, in the Program for Applied and Computational Mathematics and the Electrical Engineering Department. His research interests are in information theory, networks, machine learning, and in particular in the interplay between these fields. He received the Latsis International Prize for his work on network polar codes, and the 2014 Bell Prize for his research on the fundamental limits of community detection.

Reception information

Reception to follow.