# Community Detection in the Stochastic Block Model by Mixed Integer Programming

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 47 references that are in the map.
- First posted on arXiv 26 Jan 2021.

## Builds on (most cited first, 12 of 12)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [JuMP: A Modeling Language for Mathematical Optimization](https://mlsanity.com/paper/1508.01982/) (2015)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Detecting Overlapping Communities in Networks Using Spectral Methods](https://mlsanity.com/paper/1412.3432/) (2014)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Optimization Problems for Machine Learning: A Survey](https://mlsanity.com/paper/1901.05331/) (2019)
- [Community detection in networks: Modularity optimization and maximum likelihood are equivalent](https://mlsanity.com/paper/1606.02319/) (2016)
- [HG-means: A scalable hybrid genetic algorithm for minimum sum-of-squares clustering](https://mlsanity.com/paper/1804.09813/) (2018)
- [Linear Programming and Community Detection](https://mlsanity.com/paper/2006.03213/) (2020)

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

- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals](https://mlsanity.com/paper/2509.15989/) (2025)
- [Alzheimer's Disease Brain Network Mining](https://mlsanity.com/paper/2512.17276/) (2025)

## Abstract (arXiv)

The Degree-Corrected Stochastic Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. The standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE). Current techniques for the MLE problem are heuristics, and therefore do not guarantee convergence to the optimum. We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph. We compare these exact methods with classical heuristic algorithms based on expectation-maximization (EM). The solutions given by exact methods give us a principled way of measuring the experimental performance of classical heuristics and comparing different variations thereof.