# Minimax Rates of Community Detection in Stochastic Block Models

arXiv: https://arxiv.org/abs/1507.05313 · HTML: https://mlsanity.com/paper/1507.05313/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2015.

## Built on by (most cited first, 25 of 25)

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model](https://mlsanity.com/paper/2102.13135/) (2021)
- [Structured Optimal Variational Inference for Dynamic Latent Space Models](https://mlsanity.com/paper/2209.15117/) (2022)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models](https://mlsanity.com/paper/2412.15496/) (2024)
- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Strongly Consistent Community Detection in Popularity Adjusted Block Models](https://mlsanity.com/paper/2506.07224/) (2025)
- [A network community detection method with integration of data from multiple layers and node attributes](https://mlsanity.com/paper/2305.13012/) (2023)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)
- [Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection](https://mlsanity.com/paper/2602.17104/) (2026)
- [Near-optimal node-private community estimation in polynomial-time](https://mlsanity.com/paper/2607.09441/) (2026)

## Abstract (arXiv)

Recently network analysis has gained more and more attentions in statistics, as well as in computer science, probability, and applied mathematics. Community detection for the stochastic block model (SBM) is probably the most studied topic in network analysis. Many methodologies have been proposed. Some beautiful and significant phase transition results are obtained in various settings. In this paper, we provide a general minimax theory for community detection. It gives minimax rates of the mis-match ratio for a wide rage of settings including homogeneous and inhomogeneous SBMs, dense and sparse networks, finite and growing number of communities. The minimax rates are exponential, different from polynomial rates we often see in statistical literature. An immediate consequence of the result is to establish threshold phenomenon for strong consistency (exact recovery) as well as weak consistency (partial recovery). We obtain the upper bound by a range of penalized likelihood-type approaches. The lower bound is achieved by a novel reduction from a global mis-match ratio to a local clustering problem for one node through an exchangeability property.