Community Detection and Stochastic Block Models

Community Detection and Stochastic Block Models

25 Oct 2023 | Emmanuel Abbe
This monograph surveys recent developments in community detection within the stochastic block model (SBM), focusing on information-theoretic and computational limits for exact, partial, and weak recovery. The SBM is a random graph model where vertices are partitioned into communities with different connection probabilities. It serves as a canonical model for studying clustering and community detection, highlighting trade-offs between statistical and computational challenges. The monograph discusses phase transitions for exact recovery at the Chernoff-Hellinger threshold and weak recovery at the Kesten-Stigum threshold. It also explores the optimal SNR-mutual information tradeoff for partial recovery and the gap between information-theoretic and computational thresholds. Key algorithms include graph-splitting, semi-definite programming, belief propagation, and spectral methods. Extensions to other block models, such as geometric block models, are also covered, along with open problems. The SBM is defined by parameters including the number of communities, a probability vector for community assignments, and a symmetric matrix of connection probabilities. The monograph analyzes recovery requirements, including exact, partial, and weak recovery, and discusses their fundamental limits and efficient algorithms. It also addresses the performance of algorithms in different regimes, such as constant and logarithmic degree settings. The monograph provides a comprehensive overview of the SBM, its properties, and the challenges in community detection. It highlights the importance of the SBM in understanding the interplay between statistical and computational barriers, and its role in testing algorithms like SDPs, spectral methods, and belief propagation. The work also discusses the implications of the SBM for real-world applications, such as social networks, protein interactions, and recommendation systems. The monograph concludes with an analysis of the information-computation gap and open problems in the field.This monograph surveys recent developments in community detection within the stochastic block model (SBM), focusing on information-theoretic and computational limits for exact, partial, and weak recovery. The SBM is a random graph model where vertices are partitioned into communities with different connection probabilities. It serves as a canonical model for studying clustering and community detection, highlighting trade-offs between statistical and computational challenges. The monograph discusses phase transitions for exact recovery at the Chernoff-Hellinger threshold and weak recovery at the Kesten-Stigum threshold. It also explores the optimal SNR-mutual information tradeoff for partial recovery and the gap between information-theoretic and computational thresholds. Key algorithms include graph-splitting, semi-definite programming, belief propagation, and spectral methods. Extensions to other block models, such as geometric block models, are also covered, along with open problems. The SBM is defined by parameters including the number of communities, a probability vector for community assignments, and a symmetric matrix of connection probabilities. The monograph analyzes recovery requirements, including exact, partial, and weak recovery, and discusses their fundamental limits and efficient algorithms. It also addresses the performance of algorithms in different regimes, such as constant and logarithmic degree settings. The monograph provides a comprehensive overview of the SBM, its properties, and the challenges in community detection. It highlights the importance of the SBM in understanding the interplay between statistical and computational barriers, and its role in testing algorithms like SDPs, spectral methods, and belief propagation. The work also discusses the implications of the SBM for real-world applications, such as social networks, protein interactions, and recommendation systems. The monograph concludes with an analysis of the information-computation gap and open problems in the field.
Reach us at info@study.space
[slides] Community detection and stochastic block models%3A recent developments | StudySpace