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

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.