# Community recovery in non-binary and temporal stochastic block models

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2020.

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

- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [Multilayer hypergraph clustering using the aggregate similarity matrix](https://mlsanity.com/paper/2301.11657/) (2023)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [A network community detection method with integration of data from multiple layers and node attributes](https://mlsanity.com/paper/2305.13012/) (2023)
- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)

## Abstract (arXiv)

This article studies the estimation of latent community memberships from pairwise interactions in a network of N nodes, where the observed interactions can be of arbitrary type, including binary, categorical, and vector-valued, and not excluding even more general objects such as time series or spatial point patterns. As a generative model for such data, we introduce a stochastic block model with a general measurable interaction space mathcal S, for which we derive information-theoretic bounds for the minimum achievable error rate. These bounds yield sharp criteria for the existence of consistent and strongly consistent estimators in terms of data sparsity, statistical similarity between intra- and inter-block interaction distributions, and the shape and size of the interaction space. The general framework makes it possible to study temporal and multiplex networks with mathcal S = 0,1T, in settings where both N → ∞ and T → ∞, and the temporal interaction patterns are correlated over time. For temporal Markov interactions, we derive sharp consistency thresholds. We also present fast online estimation algorithms which fully utilise the non-binary nature of the observed data. Numerical experiments on synthetic and real data show that these algorithms rapidly produce accurate estimates even for very sparse data arrays.