Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Community detection thresholds and the weak Ramanujan property

Speaker  Laurent Massoulie

Affiliation  MSR-INRIA center

Host  Yuval Peres

Duration  00:36:13

Date recorded  4 March 2014

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.

©2014 Microsoft Corporation. All rights reserved.
By the same speaker
People also watched
> Community detection thresholds and the weak Ramanujan property