计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (9): 1959-1971.doi: 10.7544/issn1000-1239.2018.20180277
所属专题: 2018优青专题
郑文萍1,2,3,车晨浩2,钱宇华1,2,3,王杰2
Zheng Wenping1,2,3, Che Chenhao2, Qian Yuhua1,2,3, Wang Jie2
摘要: 针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题,提出一种基于标签传播的两阶段社区发现算法(a two-stage community detection algorithm based on label propagation, LPA-TS),通过参与系数确定节点更新顺序,并在标签传播过程中依据节点间相似性更新节点标签,得到初始社区划分.将社区看作节点,社区间连边数作为边权重,得到社区关系网络.按照参与系数由低到高的顺序合并社区关系网络中的节点,得到最终社区划分结果.算法LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性;在第2阶段,将不符合弱社区定义的初始社区与连边最多的相邻社区合并,再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量.通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS算法表现了良好的稳定性,在NMI、ARI、模块性等方面表现良好.
中图分类号: