稳定标签传播的社区发现方法

摘要

为提高标签传播算法的稳定性，解决标签传播算法随机性导致社区发现结果相差较大的问题，对标签初始化、随机队列设置和标签传播中随机选择过程进行了改进，提出一种稳定的标签传播社区发现方法。该方法首先通过寻找不重叠三角形进行标签初始化，然后以节点标签的熵确定节点队列并分段随机排序，最后考虑邻接点的邻接点标签分布情况进行标签选择。实验结果表明，在Zachary’ s Karate Club、Dolphin Social Network和American College Football 3个社会网络上，本文方法的稳定指标和质量指标结果均高于其他方法。稳定标签传播的社区发现方法保持了标签传播算法优点的同时，提高了社区发现结果的质量和稳定性。%In order to improve the stability of label propagation algorithm and reduce the randomness which causes difference in the results of community discovery, labels initialization, random nodes queues setting and labels random selection are improved respectively, and a stable label propagation method for community discovery is proposed. This method first initializes labels by searching for non⁃overlapping triangles in the networks, and then forms nodes queues based on labels entropy and random sorted nodes in the sub queues. At last, this method chooses labels for each node by the distribution of adjacent nodes labels. Experimental results shows that, stability indexes and quality indexes of our method are higher than other methods ’ on three social networks—Zachary ’ s Karate club, dolphin social network and American College football. Community discovery based on stable label propagation method not only maintains the advantages of label propagation algorithm, but also improves the quality and stability of community discovery results.