# Nonparametric Bayesian inference of the microcanonical stochastic block model

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2016.

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

- [Learning physical properties of anomalous random walks using graph neural networks](https://mlsanity.com/paper/2103.11738/) (2021)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Normalized mutual information is a biased measure for classification and community detection](https://mlsanity.com/paper/2307.01282/) (2023)
- [Disentangling homophily, community structure and triadic closure in networks](https://mlsanity.com/paper/2101.02510/) (2021)
- [Network reconstruction via the minimum description length principle](https://mlsanity.com/paper/2405.01015/) (2024)
- [RelDiff: Relational Data Generative Modeling with Graph-Based Diffusion Models](https://mlsanity.com/paper/2506.00710/) (2025)
- [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)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)
- [Estimation of partial rankings from sparse, noisy comparisons](https://mlsanity.com/paper/2501.02505/) (2025)
- [Mutual information and the encoding of contingency tables](https://mlsanity.com/paper/2405.05393/) (2024)
- [Unraveling the graph structure of tabular data through Bayesian and spectral analysis](https://mlsanity.com/paper/2110.01421/) (2021)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)
- [Large-scale multi-objective influence maximisation with network downscaling](https://mlsanity.com/paper/2204.06250/) (2022)
- [Revealing Patient-Reported Experiences in Healthcare from Social Media using the DAPMAV Framework](https://mlsanity.com/paper/2210.04232/) (2022)
- [Uncertainty quantification and posterior sampling for network reconstruction](https://mlsanity.com/paper/2503.07736/) (2025)
- [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)
- [Reliable data clustering with Bayesian community detection](https://mlsanity.com/paper/2510.15013/) (2025)
- [Community Detection on Model Explanation Graphs for Explainable AI](https://mlsanity.com/paper/2510.27655/) (2025)
- [Scalable inference of spatial regions and temporal signatures from time series](https://mlsanity.com/paper/2605.05008/) (2026)

## Abstract (arXiv)

A principled approach to characterize the hidden structure of networks is to formulate generative models, and then infer their parameters from data. When the desired structure is composed of modules or "communities", a suitable choice for this task is the stochastic block model (SBM), where nodes are divided into groups, and the placement of edges is conditioned on the group memberships. Here, we present a nonparametric Bayesian method to infer the modular structure of empirical networks, including the number of modules and their hierarchical organization. We focus on a microcanonical variant of the SBM, where the structure is imposed via hard constraints, i.e. the generated networks are not allowed to violate the patterns imposed by the model. We show how this simple model variation allows simultaneously for two important improvements over more traditional inference approaches: 1. Deeper Bayesian hierarchies, with noninformative priors replaced by sequences of priors and hyperpriors, that not only remove limitations that seriously degrade the inference on large networks, but also reveal structures at multiple scales; 2. A very efficient inference algorithm that scales well not only for networks with a large number of nodes and edges, but also with an unlimited number of modules. We show also how this approach can be used to sample modular hierarchies from the posterior distribution, as well as to perform model selection. We discuss and analyze the differences between sampling from the posterior and simply finding the single parameter estimate that maximizes it. Furthermore, we expose a direct equivalence between our microcanonical approach and alternative derivations based on the canonical SBM.