Community detection: recent results and open problems

Community detection, similar to graph partitioning, consists in identification of groups of similar items within a population based on observed interactions. 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 methods for community detection. 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 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á. We will conclude with open problems of current interest in the field.

Speaker Details

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 Laurent Massoulié 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.

Date:
Speakers:
Laurent Massoulie
Affiliation:
MSR-INRIA center

    • Portrait of Jeff Running

      Jeff Running