# Detectability thresholds and optimal algorithms for community structure in dynamic networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2015.

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

- [Using Motif Transitions for Temporal Graph Generation](https://mlsanity.com/paper/2306.11190/) (2023)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)
- [Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis](https://mlsanity.com/paper/2208.01365/) (2022)
- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)
- [Graph energy as a measure of community detectability in networks](https://mlsanity.com/paper/2601.05065/) (2026)
- [Mathematics of Data Science](https://mlsanity.com/paper/2607.11938/) (2026)
- [Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph](https://mlsanity.com/paper/2608.03695/) (2026)
- [Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling](https://mlsanity.com/paper/2608.03696/) (2026)

## Abstract (arXiv)

We study the fundamental limits on learning latent community structure in dynamic networks. Specifically, we study dynamic stochastic block models where nodes change their community membership over time, but where edges are generated independently at each time step. In this setting (which is a special case of several existing models), we are able to derive the detectability threshold exactly, as a function of the rate of change and the strength of the communities. Below this threshold, we claim that no algorithm can identify the communities better than chance. We then give two algorithms that are optimal in the sense that they succeed all the way down to this limit. The first uses belief propagation (BP), which gives asymptotically optimal accuracy, and the second is a fast spectral clustering algorithm, based on linearizing the BP equations. We verify our analytic and algorithmic results via numerical simulation, and close with a brief discussion of extensions and open questions.