| Speaker : | Laurent Massoulié |
| INRIA and Microsoft Research | |
| Date: | 15/01/2014 |
| Time: | 2:00 pm - 3:00 pm |
| Location: | LINCS Meeting Room 40 |
Abstract
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á.