# Large network community detection by fast label propagation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2022.

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

- [A Comprehensive Review of Community Detection in Graphs](https://mlsanity.com/paper/2309.11798/) (2023)
- [Probabilistic Label Spreading: Efficient and Consistent Estimation of Soft Labels with Epistemic Uncertainty on Graphs](https://mlsanity.com/paper/2602.04574/) (2026)
- [Efficient Recommendations via Graph Coarsening and Label Propagation](https://mlsanity.com/paper/2607.22287/) (2026)
- [Semantic Networks as Clues: A Theoretical Foundation and Process Optimization for Semantic Network Construction](https://mlsanity.com/paper/2608.01936/) (2026)
- [ComNetX: Local Hierarchical Adaptation for Dynamic Community Detection](https://mlsanity.com/paper/2608.16906/) (2026)

## Abstract (arXiv)

Many networks exhibit some community structure. There exists a wide variety of approaches to detect communities in networks, each offering different interpretations and associated algorithms. For large networks, there is the additional requirement of speed. In this context, the so-called label propagation algorithm (LPA) was proposed, which runs in near-linear time. In partitions uncovered by LPA, each node is ensured to have most links to its assigned community. We here propose a fast variant of LPA (FLPA) that is based on processing a queue of nodes whose neighbourhood recently changed. We test FLPA exhaustively on benchmark networks and empirical networks, finding that it can run up to 700 times faster than LPA. In partitions found by FLPA, we prove that each node is again guaranteed to have most links to its assigned community. Our results show that FLPA is generally preferable to LPA.