郑文萍^1,2,3,车晨浩²,钱宇华^1,2,3,王杰²

¹(山西大学大数据科学与产业研究院 太原 030006); ²(山西大学计算机与信息技术学院 太原 030006); ³(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006) (wpzheng@sxu.edu.cn)

出版日期: 2018-09-01


基金资助:国家自然科学基金项目(61672332,61572005);国家自然科学基金优秀青年科学基金项目(61322211);山西省回国留学人员科研资助项目(2017-014) This work was supported by the National Natural Science Foundation of China (61672332, 61572005), the National Natural Science Foundation of China for Excellent Young Scientists (61322211), and the Research Project of Shanxi Scholarship Council of China (2017-014).

A Two-Stage Community Detection Algorithm Based on Label Propagation

Zheng Wenping^1,2,3, Che Chenhao², Qian Yuhua^1,2,3, Wang Jie²

¹(Research Institute of Big Data Science and Industry, Shanxi University, Taiyuan 030006); ²(School of Computer and Information Technology, Shanxi University, Taiyuan 030006); ³(Key Laboratory of Computational Intelligence and Chinese Information Processing (Shanxi University), Ministry of Education, Taiyuan 030006)

Online: 2018-09-01

摘要/Abstract

摘要： 针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题，提出一种基于标签传播的两阶段社区发现算法(a two-stage community detection algorithm based on label propagation, LPA-TS)，通过参与系数确定节点更新顺序，并在标签传播过程中依据节点间相似性更新节点标签，得到初始社区划分.将社区看作节点，社区间连边数作为边权重，得到社区关系网络.按照参与系数由低到高的顺序合并社区关系网络中的节点，得到最终社区划分结果.算法LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性；在第2阶段，将不符合弱社区定义的初始社区与连边最多的相邻社区合并，再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量.通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS算法表现了良好的稳定性，在NMI、ARI、模块性等方面表现良好.

参考文献

相关文章 15

[1]	刘海姣, 马慧芳, 赵琪琪, 李志欣. 融合用户兴趣偏好与影响力的目标社区发现[J]. 计算机研究与发展, 2021, 58(1): 70-82.
[2]	赵霞, 张泽华, 张晨威, 李娴. RGNE：粗糙粒化的网络嵌入式重叠社区发现方法[J]. 计算机研究与发展, 2020, 57(6): 1302-1311.
[3]	郑文萍,吴志康,杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880.
[4]	涂盼鹏,王兴伟,李婕,黄敏. BIRI：支持信息中心范型的BBO启发式MSN路由算法[J]. 计算机研究与发展, 2019, 56(9): 1918-1926.
[5]	李明月,罗向阳,柴理想,袁福祥,甘勇. 基于网络节点聚类的目标IP城市级定位方法[J]. 计算机研究与发展, 2019, 56(3): 467-479.
[6]	杜航原，王文剑，白亮. 基于网络节点中心性度量的重叠社区发现算法[J]. 计算机研究与发展, 2018, 55(8): 1619-1630.
[7]	潘伟丰,姜波,李兵,胡博,宋贝贝. 基于组合历史的交互式服务推荐方法[J]. 计算机研究与发展, 2018, 55(3): 613-628.
[8]	张雪松,贾彩燕. 一种基于频繁词集表示的新文本聚类方法[J]. 计算机研究与发展, 2018, 55(1): 102-112.
[9]	张远鹏,邓赵红,钟富礼,杭文龙,王士同. 基于代表点评分策略的快速自适应聚类算法[J]. 计算机研究与发展, 2018, 55(1): 163-178.
[10]	傅广垣,余国先,王峻,郭茂祖. 基于正负样例的蛋白质功能预测[J]. 计算机研究与发展, 2016, 53(8): 1753-1765.
[11]	陈俊宇,周刚,南煜,曾琦. 一种半监督的局部扩展式重叠社区发现方法[J]. 计算机研究与发展, 2016, 53(6): 1376-1388.
[12]	王莹,于海,朱志良. 基于软件节点重要性的集成测试序列生成方法[J]. 计算机研究与发展, 2016, 53(3): 517-530.
[13]	潘伟丰,李兵,周晓燕,何鹏. 基于错误传播网络的回归测试用例排序方法[J]. 计算机研究与发展, 2016, 53(3): 550-558.
[14]	李全刚,刘峤,秦志光. 基于主题模型的通信网络建模与仿真[J]. 计算机研究与发展, 2016, 53(1): 206-215.
[15]	辛宇,杨静,汤楚蘅, 葛斯乔. 基于局部语义聚类的语义重叠社区发现算法[J]. 计算机研究与发展, 2015, 52(7): 1510-1521.

PDF全文下载地址:

https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3769