一种改进的标签传播快速社区发现方法

摘要

Compared with existing community detection algorithms, the label propagation algorithm (LPA) has the following advantages including simplicity, low time complexity and no specification of the number of communities. But the accuracy of LPA is lower than that of the classical algorithms such as GN. In this paper, an improved label propagation algorithm called label propagation algorithm based on local similarity(LPALS) is proposed. The experimental results show that LPALS is more accurate than LPA without spending too much time.%标签传播社区发现方法LPA(Label Propagation Algorithm,简称LPA)和已有的一些算法相比具有算法复杂度低、思想简单、不需要指定社区数量等优点,但相比于传统社区发现方法(如GN)也有准确率较低的缺点.文章提出了一种改进的、基于节点局部相似性的标签传播算法LPALS (Label Propagation Algorithm based on Local Similarity,简称LPALS).实验结果表明,LPALS算法在提高准确率的同时也保证了算法具有较低的时间复杂度.