Community detection in stochastic block models via spectral methods

Abstract:

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á.

Presentation slides

Biography:

Laurent Massoulié graduated from École Polytechnique in 1991, obtained his PhD thesis from Université Paris Sud in 1995 and his Habilitation thesis from Université Paris 7 in 2010. From 1995 to 1998 he was a researcher at France Telecom R&D, where he developed mathematical models of data transport over the Internet. He joined Microsoft Research Cambridge in 1999, where he worked on distributed algorithms for Peer-to-Peer systems, and in particular on "epidemic" methods for information propagation. In 2006 he joined Technicolor, then known as Thomson. His research there dealt with design of Peer-to-Peer systems for media streaming and analysis of social networks for information dissemination. At Technicolor, he held positions of Director of the Paris Research Lab and Distinguished Scientist, and was elected as a Technicolor Fellow in 2010. In 2012, he joined Inria as Director of the Microsoft Research - Inria Joint Centre. He is the co-author of over 80 scientific papers and 16 patents. He has co-authored the Best Paper Award-winning papers of IEEE INFOCOM'99, ACM SIGMETRICS'05 and ACM CONEXT'07 conferences.