# Consistency of Spectral Clustering on Hierarchical Stochastic Block Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

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

- [Graph Embedding with Hierarchical Attentive Membership](https://mlsanity.com/paper/2111.00604/) (2021)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (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)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)

## Abstract (arXiv)

We study the hierarchy of communities in real-world networks under a generic stochastic block model, in which the connection probabilities are structured in a binary tree. Under such model, a standard recursive bi-partitioning algorithm is dividing the network into two communities based on the Fiedler vector of the unnormalized graph Laplacian and repeating the split until a stopping rule indicates no further community structures. We prove the strong consistency of this method under a wide range of model parameters, which include sparse networks with node degrees as small as O(log n). In addition, unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude, which comprise an important class of models that are practically relevant but technically challenging to deal with. Finally we demonstrate the performance of our algorithm on synthetic data and real-world examples.