Consistency thresholds for community detection in random graphs

Community detection is a fundamental problem in the modern science of networks, with broad applications ranging from sociology to biology and infrastructure. In this thesis, we investigate the theoretical limits of recovering communities in random graphs, focusing in particular on the phenomenon of consistency, that is the ability of an algorithm to correctly identify community labels with high probability as the graph size grows. We analyze the behavior of community detection algorithms in the planted bisection model, the simplest variant of the stochastic block model. Using probabilistic tools combined with graph theory, we explore both sufficient and necessary conditions for strong consistency, based on recent advances in the literature. A central part of the work is dedicated to threshold phenomena: we highlight the critical regimes where the transition between consistency and inconsistency occurs, and review the major contributions in the field, including those by Mossel, Neeman, Sly and Abbe. We also present an application to the analysis of power grid networks, with a case study of the 2003 Italian blackout.