# Algorithmic detectability threshold of the stochastic block model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2017.

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

- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)

## Abstract (arXiv)

The assumption that the values of model parameters are known or correctly learned, i.e., the Nishimori condition, is one of the requirements for the detectability analysis of the stochastic block model in statistical inference. In practice, however, there is no example demonstrating that we can know the model parameters beforehand, and there is no guarantee that the model parameters can be learned accurately. In this study, we consider the expectation--maximization (EM) algorithm with belief propagation (BP) and derive its algorithmic detectability threshold. Our analysis is not restricted to the community structure, but includes general modular structures. Because the algorithm cannot always learn the planted model parameters correctly, the algorithmic detectability threshold is qualitatively different from the one with the Nishimori condition.