Community detection thresholds and the weak Ramanujan property

Community detection amounts to identifying groups of similar nodes in a graph. Random graphs drawn according to the so-called stochastic block model constitute an adequate playground for analyzing candidate community detection algorithms. For such stochastic block models, Decelle, Krzakala, Moore and Zdeborova conjectured the existence of a phase transition on the model parameters: below a certain threshold, no algorithm would be able to perform community detection with accuracy better than that of random guessing, while above the threshold, non-trivial community detection would be feasible. The negative part of the conjecture has been established by Mossel, Neeman and Sly. In this talk we prove the positive part of the conjecture. To do so we introduce a modified adjacency matrix counting self-avoiding paths in the original graph, and show that its spectrum enjoys a separation property akin to that of Ramanujan graphs. This in turn entails that spectral clustering based on this matrix achieves the desired non-trivial reconstruction.

Speaker Details

Laurent Massoulié graduated from École Polytechnique in 1991, obtained his PhD thesis from Université Paris Sud in 1995 and his Habilitation thesis from Université Paris 7 in 2010. From 1995 to 1998 he was a researcher at France Telecom R&D, where he developed mathematical models of data transport over the Internet. He joined Microsoft Research Cambridge in 1999, where he worked on distributed algorithms for Peer-to-Peer systems, and in particular on “epidemic” methods for information propagation. In 2006 Laurent Massoulié joined Technicolor, then known as Thomson. His research there dealt with design of Peer-to-Peer systems for media streaming and analysis of social networks for information dissemination. At Technicolor, he held positions of Director of the Paris Research Lab and Distinguished Scientist, and was elected as a Technicolor Fellow in 2010. In 2012, he joined Inria as Director of the Microsoft Research – Inria Joint Centre. He is the co-author of over 80 scientific papers and 16 patents. He has co-authored the Best Paper Award-winning papers of IEEE INFOCOM’99, ACM SIGMETRICS’05 and ACM CONEXT’07 conferences.

Series:
Microsoft Research Talks
Date:
Speakers:
Laurent Massoulie
Affiliation:
MSR-INRIA center

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks