# Recovering communities in the general stochastic block model without knowing the parameters

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2015.

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

- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [Community Recovery in the Geometric Block Model](https://mlsanity.com/paper/2206.11303/) (2022)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Multi-View Stochastic Block Models](https://mlsanity.com/paper/2406.04860/) (2024)
- [Community and hyperedge inference in multiple hypergraphs](https://mlsanity.com/paper/2505.04967/) (2025)
- [Exact Recovery in the Data Block Model](https://mlsanity.com/paper/2602.05852/) (2026)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## Abstract (arXiv)

Most recent developments on the stochastic block model (SBM) rely on the knowledge of the model parameters, or at least on the number of communities. This paper introduces efficient algorithms that do not require such knowledge and yet achieve the optimal information-theoretic tradeoffs identified in [AS15] for linear size communities. The results are three-fold: (i) in the constant degree regime, an algorithm is developed that requires only a lower-bound on the relative sizes of the communities and detects communities with an optimal accuracy scaling for large degrees; (ii) in the regime where degrees are scaled by ω(1) (diverging degrees), this is enhanced into a fully agnostic algorithm that only takes the graph in question and simultaneously learns the model parameters (including the number of communities) and detects communities with accuracy 1-o(1), with an overall quasi-linear complexity; (iii) in the logarithmic degree regime, an agnostic algorithm is developed that learns the parameters and achieves the optimal CH-limit for exact recovery, in quasi-linear time. These provide the first algorithms affording efficiency, universality and information-theoretic optimality for strong and weak consistency in the general SBM with linear size communities.