# Merge-split Markov chain Monte Carlo for community detection

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

## Key facts

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

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

- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [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)
- [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)
- [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)
- [Uncertainty quantification and posterior sampling for network reconstruction](https://mlsanity.com/paper/2503.07736/) (2025)
- [Bayesian Detection of Mesoscale Structures in Pathway Data on Graphs](https://mlsanity.com/paper/2301.11120/) (2023)

## Abstract (arXiv)

We present a Markov chain Monte Carlo scheme based on merges and splits of groups that is capable of efficiently sampling from the posterior distribution of network partitions, defined according to the stochastic block model (SBM). We demonstrate how schemes based on the move of single nodes between groups systematically fail at correctly sampling from the posterior distribution even on small networks, and how our merge-split approach behaves significantly better, and improves the mixing time of the Markov chain by several orders of magnitude in typical cases. We also show how the scheme can be straightforwardly extended to nested versions of the SBM, yielding asymptotically exact samples of hierarchical network partitions.