Large network community detection by fast label propagation
arXiv:2209.13338 · doi:10.1038/s41598-023-29610-z
Abstract
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.
References in corpus (13)
- Fast unfolding of communities in large networks
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Comparing community structure identification
- Statistical Mechanics of Community Detection
- An information-theoretic framework for resolving community structure in complex networks
- Narrow scope for resolution-limit-free community detection
- Detecting network communities by propagating labels under constraints
- Towards real-time community detection in large networks
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Note on the equivalence of the label propagation method of community detection and a Potts model approach