# Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2013.

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

- [DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization](https://mlsanity.com/paper/2312.12697/) (2023)
- [Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning](https://mlsanity.com/paper/2405.16435/) (2024)
- [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)
- [Multilayer Networks for Text Analysis with Multiple Data Types](https://mlsanity.com/paper/2106.15821/) (2021)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [CACTUS: a Comprehensive Abstraction and Classification Tool for Uncovering Structures](https://mlsanity.com/paper/2308.12031/) (2023)
- [Generating Directed Graphs with Dual Attention and Asymmetric Encoding](https://mlsanity.com/paper/2506.16404/) (2025)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks](https://mlsanity.com/paper/2310.01144/) (2023)
- [Towards Faster Graph Partitioning via Pre-training and Inductive Inference](https://mlsanity.com/paper/2409.00670/) (2024)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)
- [Computational limits to the legibility of the imaged human brain](https://mlsanity.com/paper/2309.07096/) (2023)
- [InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Corrections](https://mlsanity.com/paper/2508.19737/) (2025)
- [Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model](https://mlsanity.com/paper/2601.06262/) (2026)
- [Cluster Attention for Graph Machine Learning](https://mlsanity.com/paper/2604.07492/) (2026)
- [Synwalk -- Community Detection via Random Walk Modelling](https://mlsanity.com/paper/2101.08623/) (2021)
- [The Feature-First Block Model](https://mlsanity.com/paper/2105.13762/) (2021)
- [SamBaS: Sampling-Based Stochastic Block Partitioning](https://mlsanity.com/paper/2108.06651/) (2021)
- [Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs](https://mlsanity.com/paper/2209.14825/) (2022)
- [Balancing Summarization and Change Detection in Graph Streams](https://mlsanity.com/paper/2311.18694/) (2023)
- [PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms](https://mlsanity.com/paper/2412.13592/) (2024)
- [Robust Markov stability for community detection at a scale learned based on the structure](https://mlsanity.com/paper/2504.11621/) (2025)
- [Building Models of Neurological Language](https://mlsanity.com/paper/2506.06208/) (2025)
- [How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?](https://mlsanity.com/paper/2506.11869/) (2025)
- [Urban delineation through the lens of commute networks: Leveraging graph embeddings to distinguish socioeconomic groups in cities](https://mlsanity.com/paper/2507.11057/) (2025)
- [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)
- [Instance Discrimination for Link Prediction](https://mlsanity.com/paper/2605.20257/) (2026)

## Abstract (arXiv)

We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, with an almost linear O(Nln2N) complexity, where N is the number of nodes in the network, independent on the number of blocks being inferred. We show that the heuristic is capable of delivering results which are indistinguishable from the more exact and numerically expensive MCMC method in many artificial and empirical networks, despite being much faster. The method is entirely unbiased towards any specific mixing pattern, and in particular it does not favor assortative community structures.