Community detection in stochastic block models via spectral methods

Speaker : Laurent Massoulié
INRIA and Microsoft Research
Date: 15/01/2014
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


Community detection consists in identification of groups of similar items within a population. In the context of online social networks, it isa useful primitive for recommending either contacts or news items tousers. We will consider a particular generative probabilistic model forthe observations, namely the so-called stochastic block model, andgeneralizations thereof. We will describe spectral transformations andassociated clustering schemes for partitioning objects into distinctgroups. Exploiting results on the spectrum of random graphs, we willestablish consistency of these approaches under suitable assumptions,namely presence of a sufficiently strong signal in the observed data. Wewill also discuss open questions on phase transitions for clusterdetectability in such models when the signal becomes weak. In particularwe will introduce a novel spectral method which provably allows detectionof communities down to a critical threshold, thereby settling an openconjecture of Decelle, Krzakala, Moore and Zdeborová.