Alexandre Proutiere: Community detection in large random graphs: Fundamental limits and efficient algorithms

We consider the problem of identifying communities in graphs. This problem has been extensively studied in statistics, physics, and computer science, and has many important applications in diverse contexts such as biology, social networks, and distributed computing. A central question for such a problem is to characterize conditions under which communities can be efficiently detected using low complexity algorithms. We address this question (i) when the graph is generated through the so-called stochastic block model (also known as the planted partition model), and (ii) when the graph can be only partially observed. We report recent results related to this model. We provide fundamental performance limits satisfied by any community detection algorithm (irrespective of its complexity), and design a spectral-based algorithm (an extension of a scheme recently proposed by A. Coja-Oghlan) whose performance approaches these limits in some relevant cases.