Community detection and Ramanujan graphs: A proof of the « spectral redemption conjecture »
vendredi 29 mai 2015, 9h30 - 10h30
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 , 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.
 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.