Incremental Similarity‐Based Label Propagation Algorithm for Dynamic Community Detection

Abstract

ABSTRACT We propose an incremental similarity‐based label propagation algorithm (DLPA‐S) for detecting dynamic community structures. As the network evolves, the method efficiently updates the communities over time via local label updates driven by changes in network topology—including edge and vertex additions or removals—and vertex similarity. This incremental approach significantly reduces computational cost while preserving accuracy in capturing community evolution. We evaluate DLPA‐S using a comprehensive set of quality metrics that assess both the structural properties of the network and the agreement between detected communities and ground‐truth partitions. Experiments are conducted on synthetic and real‐world dynamic networks, varying key graph characteristics such as the number of vertices and the average degree, as well as across diverse community scenarios. The results show that DLPA‐S consistently achieves stable and high‐performing results, maintains high NMI and F1 scores, ensures strong internal connectivity, clear community separability, and avoids disconnected communities, while remaining computationally efficient.