An improved label propagation algorithm based on the similarity matrix using random walk

作者：Zhang, Xian-Kun^*; Song, Chen; Jia, Jia; Lu, Zeng-Lei; Zhang, Qian

来源：International Journal of Modern Physics B, 2016, 30(16): 1650093.

DOI：10.1142/S0217979216500934

• Random walk
• label propagation
• community detection
• similarity
• division

Community detection based on label propagation algorithm (LPA) has attracted widespread concern because of its high efficiency. But it is difficult to guarantee the accuracy of community detection as the label spreading is random in the algorithm. In response to the problem, an improved LPA based on random walk (RWLPA) is proposed in this paper. Firstly, a matrix measuring similarity among various nodes in the network is obtained through calculation. Secondly, during the process of label propagation, when a node has more than a neighbor label with the highest frequency, not the label of a random neighbor but the label of the neighbor with the highest similarity will be chosen to update. It can avoid label propagating randomly among communities. Finally, we test LPA and the improved LPA in benchmark networks and real-world networks. The results show that the quality of communities discovered by the improved algorithm is improved compared with the traditional algorithm.

• 出版日期2016-6-30
• 单位天津科技大学