基于共同邻居相似度的改进标签传播算法

An Improved Label Propagation Algorithm Based on Common Neighbors Similarity

标签传播算法是一种重要的社区发现算法,具有不需要先验知识、时间复杂度低的优点.针对传统标签传播算法随机性强导致社区发现结果稳定性差的问题,提出基于共同邻居相似度的改进标签传播算法LPACN,在选择邻居节点中出现次数最多的标签时,将邻居节点与该节点的相似度一并考虑,降低了标签选择的随机性,提高了算法的稳定性.在4个基准网络数据集上进行了对比实验,实验结果表明基于共同邻居相似度的改进标签传播算法能够得到更好的社区划分.

Label propagation is an important community detection algorithm,which doesn′t require prior knowledge and has low time complexity. In view of the poor stability of community discovery results caused by the randomness of traditional label propagation algorithm,an improved label propagation algorithm based on common neighbors similarity is proposed. When choosing the most frequent labels of neighbor nodes,the similarity between neighbor nodes and the current node is considered together,which reduces the randomness of label selection and improves the stability of the algorithm. We evaluate the proposed algorithm on four benchmark networks,and the experimental results show that the improved label propagation algorithm based on common neighbors similarity obtains better community partition results.