Laurent Massoulié (Inria Saclay & Microsoft Research)

Community detection and Ramanujan graphs: A proof of the « spectral redemption conjecture »

vendredi 29 mai 2015, 9h30 - 10h30

Salle de réunion, espace Turing

Community detection consists in clustering graph nodes into groups with
homogeneous properties. When the observed random graph is drawn from the stochastic block model (a multi-type version of the Erdös-Rényi model),
phase transitions on feasibility of community detection occur.
The spectral redemption conjecture, formulated in [1], states that right
above the transition point, community detection can be made on the basis of
the leading eigenvectors of the so-called non-backtracking matrix. In this
talk I will present our proof of this conjecture. In the process
Ramanujan-like properties of random graphs will be discussed.

[1] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborova, P.
Zhang, « Spectral redemption: clustering sparse graphs ».

Joint work with Charles Bordenave and Marc Lelarge.