A framework for overlapping and non-overlapping communities detection based on seed extension and label propagation

Jianyong Yu, Yuqi Liu, Wei Liang, Xue Han and Neal N. Xiong

Physica A: Statistical Mechanics and its Applications, 2025, vol. 660, issue C

Abstract: Current social networks driven by Internet technology are characterized by complexity, overlap and large-scale. However, the label propagation algorithm, despite its near-linear time complexity that has drawn significant attention, remains a challenge in meeting the demands for high accuracy and stability. We introduce LPANIS (Label Propagation Algorithm with Node Importance and Similarity), a novel community detection algorithm that utilizes a combination of seed extension and label propagation. This approach enables the detection of both overlapping and non-overlapping communities concurrently, providing a solution to the challenges mentioned above. Initially, the seed node is identified and similarity is employed to preprocess the labels of nodes adjacent to the seed node. Subsequently, a predetermined sequence determined by node importance is utilized for the execution of label propagation. Finally, the community structure is detected using label propagation ability and label update strategy. We evaluate the effectiveness of our method by comparing experiments on five real networks and five synthetic networks, using seven comparison algorithms. Multiple sets of experiments show that LPANIS obtains the best results in both modularity and normalized mutual information. In seventy-five percent of synthetic networks, the accuracy of detecting overlapping nodes is not less than 0.83 according to the F−score.

Keywords: Community detection; Label propagation; Node importance; Similarity between nodes (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437125000147
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:660:y:2025:i:c:s0378437125000147

DOI: 10.1016/j.physa.2025.130362

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().