Tuesday, April 28, 2015 - 4:00pm to Wednesday, April 29, 2015 - 3:55pm
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.