Community detection thresholds and the weak Ramanujan property

Опубликовано 21 июня 2016, 19:11

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.