# Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

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

- [Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs](https://mlsanity.com/paper/2103.03561/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [An embedding-based distance for temporal graphs](https://mlsanity.com/paper/2401.12843/) (2024)
- [Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph](https://mlsanity.com/paper/2608.03695/) (2026)

## Abstract (arXiv)

This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is proposed, which benefits from the positive correlation in the class labels and in their temporal evolution and is designed to be applicable to any dynamical graph with a community structure. Under the dynamical degree-corrected stochastic block model, in the case of two classes of equal size, we demonstrate and support with extensive simulations that our proposed algorithm is capable of making non-trivial community reconstruction as soon as theoretically possible, thereby reaching the optimal detectability threshold and provably outperforming competing spectral methods.