# Information-theoretic Limits for Community Detection in Network Models

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2018.

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

- [Federated Myopic Community Detection with One-shot Communication](https://mlsanity.com/paper/2106.07255/) (2021)
- [Efficient data selection employing Semantic Similarity-based Graph Structures for model training](https://mlsanity.com/paper/2402.14888/) (2024)
- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)
- [Exact Inference in High-order Structured Prediction](https://mlsanity.com/paper/2302.03236/) (2023)
- [Information-Theoretic Bounds for Integral Estimation](https://mlsanity.com/paper/2102.10199/) (2021)
- [Query-Limited Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/2606.02055/) (2026)

## Abstract (arXiv)

We analyze the information-theoretic limits for the recovery of node labels in several network models. This includes the Stochastic Block Model, the Exponential Random Graph Model, the Latent Space Model, the Directed Preferential Attachment Model, and the Directed Small-world Model. For the Stochastic Block Model, the non-recoverability condition depends on the probabilities of having edges inside a community, and between different communities. For the Latent Space Model, the non-recoverability condition depends on the dimension of the latent space, and how far and spread are the communities in the latent space. For the Directed Preferential Attachment Model and the Directed Small-world Model, the non-recoverability condition depends on the ratio between homophily and neighborhood size. We also consider dynamic versions of the Stochastic Block Model and the Latent Space Model.