Community Detection Using An Improved Label Propagation Algorithm

Label propagation is a promising engine for community detection, widely utilized in anomaly analysis and recommendation systems. However, traditional label propagation algorithms struggle with large-scale networks due to poor stability, slow convergence, and low accuracy. Despite its advancements, the state-of-the-art variant LBLD (Local Balanced Label Diffusion) also faces challenges, such as limited utilization of similarity and a rudimentary approach to constructing the initial community framework, which diminishes the quality of the final results.To address these limitations, we introduce PNLP, a novel similarity-based label propagation algorithm. The key innovations of PNLP include: (i) Integrating similarity throughout the entire process of label propagation, enhancing the robustness and accuracy of community detection. (ii) Defining a Node Importance metric (NI) to provide a more comprehensive assessment of node influence. (iii) Introducing a novel method for identifying rough seed nodes and constructing a tighter initial framework for communities using conductance.Furthermore, PNLP employs a similarity-based influence metric to guide the label updating process, ensuring a more refined and accurate detection of community structures. Extensive experiments conducted on both real-world and synthetic networks demonstrate the superior performance of PNLP, which significantly outperforms established methods such as Infomap, Louvain, Leiden, LPA, and LBLD in terms of accuracy by factors of up to 1.39 times, 1.48 times, 1.44 times, 2.05 times and 1.25 times, respectively.