# Hierarchical community detection by recursive partitioning

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

## Key facts

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

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

- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations](https://mlsanity.com/paper/2204.05885/) (2022)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Exploiting Expert Knowledge for Assigning Firms to Industries: A Novel Deep Learning Method](https://mlsanity.com/paper/2209.05943/) (2022)
- [flexBART: Flexible Bayesian regression trees with categorical predictors](https://mlsanity.com/paper/2211.04459/) (2022)
- [Subgraph nomination: Query by Example Subgraph Retrieval in Networks](https://mlsanity.com/paper/2101.12430/) (2021)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [T-Stochastic Graphs](https://mlsanity.com/paper/2309.01301/) (2023)
- [Fitting Low-rank Models on Egocentrically Sampled Partial Networks](https://mlsanity.com/paper/2303.11230/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Two-cluster test](https://mlsanity.com/paper/2507.08382/) (2025)
- [Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics](https://mlsanity.com/paper/2511.18056/) (2025)
- [Matching and mixing: Matchability of graphs under Markovian error](https://mlsanity.com/paper/2601.20020/) (2026)

## Abstract (arXiv)

The problem of community detection in networks is usually formulated as finding a single partition of the network into some "correct" number of communities. We argue that it is more interpretable and in some regimes more accurate to construct a hierarchical tree of communities instead. This can be done with a simple top-down recursive partitioning algorithm, starting with a single community and separating the nodes into two communities by spectral clustering repeatedly, until a stopping rule suggests there are no further communities. This class of algorithms is model-free, computationally efficient, and requires no tuning other than selecting a stopping rule. We show that there are regimes where this approach outperforms K-way spectral clustering, and propose a natural framework for analyzing the algorithm's theoretical performance, the binary tree stochastic block model. Under this model, we prove that the algorithm correctly recovers the entire community tree under relatively mild assumptions. We apply the algorithm to a gene network based on gene co-occurrence in 1580 research papers on anemia, and identify six clusters of genes in a meaningful hierarchy. We also illustrate the algorithm on a dataset of statistics papers.