基于随机游走相似度矩阵的改进标签传播算法

摘要

Community detection algorithm based on label propagation attracts widespread concerns because of its high time efficiency.But it is difficult for the algorithm to guarantee the accuracy of community partition as the label propagates randomly.In response to the problem,in this paper we propose a random walk-based improved label propagation algorithm.First,we introduce the random walk idea to get a matrix measuring the similarity among various nodes of the network through calculation.Secondly,during the process of label propagation,when a neighbour node has more than one label with the highest occurrence frequency,we will not randomly select one label of a neighbour node but will choose the label owned by a neighbour node having highest similarity and update it.This avoids the random label propagation among com-munities.Finally,we test the label propagation algorithm and the improved label propagation algorithm in different real networks.Results show that in community detection the improved algorithm has better performance than the primitive label propagation algorithm.%基于标签传播的社区发现算法因其时间效率高而得到广泛关注。针对该算法因标签传播的随机性导致其社区划分准确度难以保证的问题，提出一种基于随机游走的改进算法。首先，引入随机游走思想，计算得到一种衡量网络节点间相似度的矩阵；其次，在标签传播过程中，当邻居节点中标签出现频率存在多个最高时，不是随机选择一个，而是选择相似度最高的邻居节点所拥有的标签来更新，避免了标签在社区之间的任意传播；最后，用不同的真实网络进行测试，结果表明在社区发现中该算法比原始标签传播算法取得更好的表现。