New label propagation algorithms based on the law of universal gravitation for community detection

Wencong Li, Jihui Wang and Jiansheng Cai

Physica A: Statistical Mechanics and its Applications, 2023, vol. 627, issue C

Abstract: Many networks in reality are undirected networks, such as the cooperative network, the network of protein interactions in biomedicine, etc. Discovering community structure in the complex network is an important aspect of network analysis. We propose three enhanced label propagation algorithms based on the law of universal gravitation and give two methods (the number of triangles and the algorithm of random walk with restart) that replace the distance in the traditional physical meaning to reduce the time complexity of our algorithms. The obtained attraction between nodes is used as the weight of the edge to propagate labels. Moreover, we propose a new label propagation rule to address the shortcoming of the LPA algorithm in the label propagation process. Based on the two methods mentioned above that replace the distance, we obtain the LPA_T and LPA_R algorithms, respectively. Additionally, we consider combining these two methods by setting the parameter θ to form a new enhanced label propagation algorithm (LPA_P). The effectiveness of our algorithms in finding community structure is tested on real and synthetic networks, and the results show that our algorithms can effectively detect communities on networks. Experiments also show that the proposed algorithms are close to linear time complexity, have better accuracy than LPA, and perform satisfactorily in running time.

Keywords: Community detection; Undirected networks; Universal gravitation; Random walk (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437123006957
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:627:y:2023:i:c:s0378437123006957

DOI: 10.1016/j.physa.2023.129140

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 ().