# Estimating the number of clusters of a Block Markov Chain

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 60 references that are in the map.
- First posted on arXiv 25 Jul 2024.

## Builds on (most cited first, 19 of 19)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Accelerated Hierarchical Density Clustering](https://mlsanity.com/paper/1705.07321/) (2017)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [A goodness-of-fit test for stochastic block models](https://mlsanity.com/paper/1412.4857/) (2014)
- [State Aggregation Learning from Markov Transition Data](https://mlsanity.com/paper/1811.02619/) (2018)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Spectral State Compression of Markov Processes](https://mlsanity.com/paper/1802.02920/) (2018)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [Learning Markov models via low-rank optimization](https://mlsanity.com/paper/1907.00113/) (2019)
- [Estimating the number of communities in a network](https://mlsanity.com/paper/1605.02753/) (2016)
- [Scalable MCMC for Mixed Membership Stochastic Blockmodels](https://mlsanity.com/paper/1510.04815/) (2015)
- [Spectral community detection in sparse networks](https://mlsanity.com/paper/1308.6494/) (2013)
- [Nearly Optimal Latent State Decoding in Block MDPs](https://mlsanity.com/paper/2208.08480/) (2022)
- [Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering](https://mlsanity.com/paper/1904.02926/) (2019)
- [Bayesian estimation of the latent dimension and communities in stochastic blockmodels](https://mlsanity.com/paper/1904.05333/) (2019)
- [Detection and Evaluation of Clusters within Sequential Data](https://mlsanity.com/paper/2210.01679/) (2022)
- [Determine the Number of States in Hidden Markov Models via Marginal Likelihood](https://mlsanity.com/paper/2405.12343/) (2024)

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

- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)

## Abstract (arXiv)

Clustering algorithms frequently require the number of clusters to be chosen in advance, but it is usually not clear how to do this. To tackle this challenge when clustering within sequential data, we present a method for estimating the number of clusters when the data is a trajectory of a Block Markov Chain. Block Markov Chains are Markov Chains that exhibit a block structure in their transition matrix. The method considers a matrix that counts the number of transitions between different states within the trajectory, and transforms this into a spectral embedding whose dimension is set via singular value thresholding. The number of clusters is subsequently estimated via density-based clustering of this spectral embedding, an approach inspired by literature on the Stochastic Block Model. By leveraging and augmenting recent results on the spectral concentration of random matrices with Markovian dependence, we show that the method is asymptotically consistent - in spite of the dependencies between the count matrix's entries, and even when the count matrix is sparse. We also present a numerical evaluation of our method, and compare it to alternatives.