Community detection using constrained label propagation algorithm with nodes exemption
Document Type
Article
Publication Date
2-1-2022
Abstract
The detection of community structure plays an important role in understanding the properties and characteristics of complex networks. The label propagation algorithm (LPA) emerges as a popular community detection method, due to its simplicity and low computational cost. Nonetheless, the LPA is not without its limitations so that the Semi Synchronous Constrained Label Propagation Algorithm (SSCLPA) is a modified LPA that implements various constraints to ameliorate the stability of the LPA. Aside from giving accurate and deterministic detection, it can avoid trivial detection. In this paper the SSCLPA is extended into weighted and directed networks, so that nodes which fulfill certain conditions are updated separately at the end of the algorithm. Furthermore, some modifications are performed on the propagation processes in the SSCLPA. These new features and modifications improve the time efficiency of the SSCLPA with only marginal loss in the quality of the detection. Our proposed method is tested and compared to the other community detection methods in various benchmark and real-world networks. The results showed that the proposed method is a well-balanced method with features that takes into account the stability, quality and time efficiency of the detection.
Keywords
Complex networks, Community structure, Community detection, Label propagation algorithm
Divisions
MathematicalSciences
Funders
University of Malaya HIR Grant [Grant No: UM.C/625/1/HIR/MOHE/SC/13],University of Malaya HIR GRAS
Publication Title
Computing
Volume
104
Issue
2
Publisher
Springer Wien
Publisher Location
SACHSENPLATZ 4-6, PO BOX 89, A-1201 WIEN, AUSTRIA