Community Detection and Stochastic Block Models

2017/03/29 by Emmanuel Abbé, Abbe, Emmanuel · 40 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Opinion Dynamics and Social Influence #Probability (math.PR) #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.1703.10146

openalex publication_date 2017/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatorial statistics and more generally data science. This monograph surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic 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, the optimal SNR-mutual information tradeoff for partial recovery, and the gap between information-theoretic and computational thresholds. The monograph gives a principled derivation of the main algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, (linearized) belief propagation, classical/nonbacktracking spectral methods and graph powering. Extensions to other block models, such as geometric block models, and a few open problems are also discussed.

Cited by

• Exact Recovery in the Geometric SBM
• Graph energy as a measure of community detectability in networks
• The Colombian legislative process, 2014-2025: networks, topics, and polarization
• Generating temporal networks with the Ascona model
• Optimal Transport-Based Clustering of Attributed Graphs with an Application to Road Traffic Data
• A Doubled Adjacency Spectral Embedding Approach to Graph Clustering
• Differentially Private Community Detection in h-uniform Hypergraphs
• Phase Transition for Stochastic Block Model with more than √(n) Communities (II)
• Variational Estimators for Node Popularity Models
• Quantifying and Minimizing Perception Gap in Social Networks
• PCA recovery thresholds in low-rank matrix inference with sparse noise
• Decoder-only Clustering in Attributed Graphs
• A Probabilistic Approach to Pose Synchronization for Multi-Reference Alignment with Applications to MIMO Wireless Communication Systems
• Finite-sample certification and operating envelopes for spectral clustering and graph centrality
• The value of random zero-sum games
• A roadmap for curvature-based geometric data analysis and learning
• A Geometric Analysis of PCA
• Asymptotic distribution of the global clustering coefficient in a random annulus graph
• Hypothesis testing for the uniformity of random geometric graph
• Non-asymptotic goodness-of-fit tests and model selection in valued stochastic blockmodels
• Structure-Aware Spectral Sparsification via Uniform Edge Sampling
• Hypothesis testing for the dimension of random geometric graph
• Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency
• Time-Frequency Filtering Meets Graph Clustering
• Spin glasses and the Parisi formula
• GraphUniverse: Synthetic Graph Generation for Evaluating Inductive Generalization
• On Graph-Informed Distance Metrics for Comparing Graph Partitions
• Perceived fairness in networks
• Text Meets Topology: Rethinking Out-of-distribution Detection in Text-Rich Networks
• Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation
• Phase Transition for Stochastic Block Model with more than √(n) Communities
• Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals
• Aligning LLMs for the Classroom with Knowledge-Based Retrieval -- A Comparative RAG Study
• Network Signflip Parallel Analysis for Selecting the Embedding Dimension
• On the Optimization of Methods for Establishing Well-Connected Communities
• A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations
• SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion
• Simultaneous estimation of connectivity and dimensionality in samples of networks
• Robust Detection of Planted Subgraphs in Semi-Random Models
• Multi-Community Spectral Clustering for Geometric Graphs

Related

• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Community Detection in the Multi-View Stochastic Block Model
• Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs
• How Robust are Reconstruction Thresholds for Community Detection?
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery