Community Detection and Stochastic Block Models

Community Detection and Stochastic Block Models

25 Oct 2023 | Emmanuel Abbe
This monograph by Emmanuel Abbe provides a comprehensive survey of recent developments in community detection within the stochastic block model (SBM), a widely used random graph model for studying clustering and community detection. The SBM is characterized by different groups of vertices connecting differently, making it a canonical model for understanding information-theoretic and computational trade-offs in combinatorial statistics and data science. The monograph covers fundamental limits for community detection, including phase transitions for exact recovery at the Chernoff-Hellinger threshold, weak recovery at the Kesten-Stigum threshold, and partial recovery with optimal SNR-mutual information tradeoffs. It also discusses the gap between information-theoretic and computational thresholds. Key algorithms discussed include two-round algorithms via graph-splitting, semi-definite programming, belief propagation, spectral methods, and graph powering. The monograph extends these results to other block models, such as geometric block models, and highlights open problems in the field. The introduction provides a detailed overview of community detection, clustering, and block models, emphasizing their importance in various applications, from social networks to biological systems. It also discusses the historical development of the SBM and its role in various scientific communities. The monograph is structured into several chapters, each focusing on specific aspects of community detection, including the definition of the SBM, recovery requirements, and detailed proofs for exact, weak, and partial recovery. It concludes with a discussion of other block models and open problems, providing a comprehensive resource for researchers and practitioners in the field.This monograph by Emmanuel Abbe provides a comprehensive survey of recent developments in community detection within the stochastic block model (SBM), a widely used random graph model for studying clustering and community detection. The SBM is characterized by different groups of vertices connecting differently, making it a canonical model for understanding information-theoretic and computational trade-offs in combinatorial statistics and data science. The monograph covers fundamental limits for community detection, including phase transitions for exact recovery at the Chernoff-Hellinger threshold, weak recovery at the Kesten-Stigum threshold, and partial recovery with optimal SNR-mutual information tradeoffs. It also discusses the gap between information-theoretic and computational thresholds. Key algorithms discussed include two-round algorithms via graph-splitting, semi-definite programming, belief propagation, spectral methods, and graph powering. The monograph extends these results to other block models, such as geometric block models, and highlights open problems in the field. The introduction provides a detailed overview of community detection, clustering, and block models, emphasizing their importance in various applications, from social networks to biological systems. It also discusses the historical development of the SBM and its role in various scientific communities. The monograph is structured into several chapters, each focusing on specific aspects of community detection, including the definition of the SBM, recovery requirements, and detailed proofs for exact, weak, and partial recovery. It concludes with a discussion of other block models and open problems, providing a comprehensive resource for researchers and practitioners in the field.
Reach us at info@study.space