Community detection and the stochastic block model recent developments
The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model for clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs occurring in network and data sciences. This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to statistical and computational tradeoffs, and for various recovery requirements such as exact, partial and weak recovery. The main results discussed are the phase transitions for exact recovery at the Chernoff Hellinger threshold, the phase transition for weak recovery at the Kesten Stigum threshold, and the optimal distortion SNR tradeoff for partial recovery. The note also covers the algorithms developed in the quest of achieving the limits, in particular two rounds algorithms via graph splitting, semi definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. Finally, it discusses the discrepancies between statistical and computational thresholds and a few open problems. *Program in Applied and Computational Mathematics, and Department of Electrical Engineering, Princeton University, Princeton, USA, eabbe@princeton.edu, www.princeton.edu/~eabbe. This research was partly supported by the NSF CAREER Award CCF 1552131, ARO grant W911NF16 1 0051, NSF Center for the Science of Information NSF CCF 0939370, and the Google Faculty Research Award.