sur ce site

Accueil du site > Résumés des séminaires > Community detection in stochastic block models via spectral methods

Community detection in stochastic block models via spectral methods

Community detection consists in identification of groups of similar items within a population. In the context of online social networks, it is a useful primitive for recommending either contacts or news items to users. We will consider a particular generative probabilistic model for the observations, namely the so-called stochastic block model, and generalizations thereof. We will describe spectral transformations and associated clustering schemes for partitioning objects into distinct groups.

Exploiting results on the spectrum of random graphs, we will establish consistency of these approaches under suitable assumptions, namely presence of a sufficiently strong signal in the observed data. We will also discuss open questions on phase transitions for cluster detectability in such models when the signal becomes weak. In particular we will introduce a novel spectral method which provably allows detection of communities down to a critical threshold, thereby settling an open conjecture of Decelle, Krzakala, Moore and Zdeborová.

Based on :

“ Edge Label Inference in Generalized Stochastic Block Models : from Spectral Theory to Impossibility Results”

Jiaming Xu, Laurent Massoulié, Marc Lelarge, COLT 2014

“Community detection thresholds and the weak Ramanujan property”, Laurent Massoulié, ACM STOC 2014.

CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46