一种基于标签传播的社团检测算法

谭玉玲

(罗定职业技术学院 信息工程系,广东 罗定 527200)

复杂网络可看作是一个包含大量节点的无向图或者有向图，边上的权值是节点与节点之间的相似度，相似度高的节点可最终被划分进入同一个社团.通过对社团的检测，可以了解到整个复杂网络的发展趋势以及整个群体的关键特征，并且有利于了解到网络的拓扑结构并提取出隐藏在复杂网络中的有利信息[1].正是因为社团检测在日常生活中应用地越来越广泛，如何精确划分复杂网络成为社团就成了人们关注的重点.

对于传统的社团检测算法大致可分为图划分方法、基于层次聚类的算法、基于进化的算法等[2].标签传播算法是一种经典的被广泛使用的社团检测算法，有着简单、快速等优点.文献[3]提出了最经典的GN算法，文献[4]提出了一种新的标签传播的社团检测RAK算法，分类效果好且复杂度较低.文献[5]对RAK算法进行改进，引入目标函数，将算法的社团检测变为一个模块度最大化的问题.文献[6]中改进了节点标签的更新方式，但是容易陷入局部最优.文献[7]提出了一种基于社团核的标签传播算法，改善了算法性能，但需要提前给出社团核数目，导致检测结果可能变得随机.

已有的标签传播算法具有很强的随机性且其鲁棒性较差等问题.本文针对基于标签传播算法中存在的社团检测结果不稳定的情况，提出了一个基于循环查找核节点的标签传播算法，实验结果证……