基于相似性模块度的层次聚合社区发现算法

doi:10.16182/j.issn1004731x.joss.201705013

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (5): 1028-1032.doi: 10.16182/j.issn1004731x.joss.201705013

基于相似性模块度的层次聚合社区发现算法

占文威, 席景科, 王志晓

中国矿业大学计算机学院, 江苏徐州 221116

收稿日期:2016-04-30 修回日期:2016-08-08 出版日期:2017-05-08 发布日期:2020-06-03
作者简介:占文威(1990-),男,湖北,硕士,研究方向为数据挖掘;席景科(1972-),男,河南,博士,副教授,研究方向为数据挖掘。
基金资助:
国家自然科学基金(61402482), 中国博士后基金(2015T80555), 江苏省博士后基金(1501012A)

Hierarchical Agglomerative Community Detection Algorithm Based on Similarity Modularity

Zhan Wenwei, Xi Jingke, Wang Zhixiao

College of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China

Received:2016-04-30 Revised:2016-08-08 Online:2017-05-08 Published:2020-06-03

摘要/Abstract

摘要： Fast Unfolding是一种基于模块度优化的层次聚合社区发现算法,其优点是运行速度很快,不足之处是准确度有待提升,这是因为该算法采用传统模块度作为合并社区的衡量标准,而传统模块度函数在计算时只考虑节点间的链接信息,忽略邻居节点的影响,导致会出现两个节点共同邻居较多但由于节点间链接信息较弱不能被合并的情况,从而影响结果的准确度。针对该不足之处,通过引入优化后的相似度来改进Fast Unfolding算法的模块度函数,提出一种基于相似性模块度的层次聚合社区发现算法,并采用归一化互信息量即NMI(Normalized Mutual Information)作为评价算法准确性的指标,在真实网络和LFR(Lancichinetti Fortunato Radicchi)人工合成网络上进行实验,结果表明改进算法检测社区结构的准确度有明显改善。

关键词: Fast Unfolding算法, 模块度, 节点相似度, 社区发现

Abstract: Fast Unfolding is a hierarchical community detection algorithm based on modularity. It runs very fast, but the accuracy needs to be improved. Because the algorithm adopts traditional modularity to merger communities, it only considers node link information and ignores the neighbor nodes. Therefore, two nodes that have common neighbors and weak link information may not be merged, thus affecting the accuracy. In view of the shortcomings, a hierarchical agglomerative community detection algorithm based on similarity modularity was proposed through introducing optimized similarity to improve the modularity. It adopts NMI as the accuracy measurement. Experiments on the real network and LFR synthetic network show that the accuracy of detecting community is obviously improved.

Key words: fast unfolding algorithm, modularity, similarity, community detection

中图分类号:

TP393

占文威, 席景科, 王志晓. 基于相似性模块度的层次聚合社区发现算法[J]. 系统仿真学报, 2017, 29(5): 1028-1032.

Zhan Wenwei, Xi Jingke, Wang Zhixiao. Hierarchical Agglomerative Community Detection Algorithm Based on Similarity Modularity[J]. Journal of System Simulation, 2017, 29(5): 1028-1032.

参考文献

[1] Pothen A, Simon H D, Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J]. Siam Journal on Matrix Analysis and Applications (S0895-4798), 1990, 11(3): 430-452.
[2] Kemighan B W, Lin S.An efficient heuristic procedure for partioning graphs[J]. Bell System Technical Journal (S0005-8580), 1970, 49(2): 291-307.
[3] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America (S0027-8424), 2002, 99(12): 7821-7826.
[4] Newman M E.Fast algorithm for detecting community structure in networks[J]. Physical Review E Statistical Nonlinear and Soft Matter Physics (S1539-3755), 2004, 69(6): 066133.
[5] Blondel V D, Guillaume J l, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment (S1742-5468), 2008, (10): 10008.
[6] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear and Soft Matter Physics (S1539-3755), 2004, 69(2 Pt 2): 026113.
[7] Fortunato S, Barthélemy M.Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36.
[8] Fortunato S.Community detection in graphs[J]. Physics Reports (S0370-1573), 2010, 486(3/5): 75-174.
[9] Adamic L A, Adar E.Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230.
[10] Estevez P A, Tesmer M, Perez C A, et al.Normalized Mutual Information Feature Selection[J]. IEEE Transactions on Neural Networks, 2009, 20(2):189-201.
[11] Yu K, Yu S, Tresp V.Soft clustering on graphs[J]. Advances in Neural Information Processing Systems, 2005, 18(5): 1553.
[12] 李玉翔, 李弼程, 郭志刚. 基于非负矩阵分解的网络重叠社区发现研究[J]. 系统仿真学报, 2014, 26(3): 643-649.
(Li Yuxiang, Li Bicheng, Guo Zhigang.Research on overlapping network community discovery based on non negative matrix factorization[J]. Journal of System Simulation (S1004-731X), 2014, 26(3): 643-649.)
[13] 喻金平, 郑杰, 朱桂祥. 基于多关系网络的社区检测算法[J]. 系统仿真学报, 2015, 27(1): 147-154.
(Yu Jinping, Zheng Jie, Zhu Guixiang.A community detection algorithm based on multi relational network[J]. Journal of System Simulation (S1004-731X), 2015, 27(1): 147-154.)

[1]	许斌, 闫文卿, 韩卓凡, 何广深, 邓涛, 赵云凯, 亓晋. 基于烟花算法的基站群协作计算卸载模型研究[J]. 系统仿真学报, 2022, 34(2): 354-365.
[2]	华翔, 石成泷, 李宝华, 张杰韬, 左嘉娴. 一种自适应的无人集群中心节点选择方法[J]. 系统仿真学报, 2021, 33(11): 2636-2646.
[3]	华翔, 李宝华, 姚红娟, 王昭, 左嘉娴. 一种动态感知的连通恢复方法研究[J]. 系统仿真学报, 2021, 33(7): 1514-1525.
[4]	林硕, 安磊, 高治军, 单丹, 尚文利. 结合栈式自编码及长短时记忆的入侵检测研究[J]. 系统仿真学报, 2021, 33(6): 1288-1296.
[5]	王振东, 谢华茂, 胡中栋, 李大海, 王俊岭. 改进花朵授粉算法的无线传感器网络部署优化[J]. 系统仿真学报, 2021, 33(3): 645-656.
[6]	董书琴, 张斌. 面向不平衡数据的网络流量异常检测方法[J]. 系统仿真学报, 2021, 33(3): 679-689.
[7]	陈帅. 基于多层耦合网络的舆情传播控制研究[J]. 系统仿真学报, 2020, 32(12): 2353-2361.
[8]	刘小虎, 张恒巍, 张玉臣, 马壮, 吕文雷. 基于博弈模型与NetLogo仿真的网络攻防态势研究[J]. 系统仿真学报, 2020, 32(10): 1918-1926.
[9]	华翔, 姚红娟, 王海, 王昭, 张杰韬, 舒力力. 自适应的无线融断网络路由算法研究[J]. 系统仿真学报, 2020, 32(10): 2022-2033.
[10]	王晓锋, 陈阳, 张光杰, 陈建宇. 面向网络仿真拓扑的多目标优化映射方法[J]. 系统仿真学报, 2020, 32(8): 1436-1445.
[11]	孙子文, 张炎棋, 徐宜敏. 一种采用混合抗干扰方法的路由恢复机制[J]. 系统仿真学报, 2020, 32(5): 874-884.
[12]	刘渊, 冯兴兵, 王晓锋, 邓赵红. 面向虚实互联网络的链路采集技术研究[J]. 系统仿真学报, 2020, 32(3): 421-429.
[13]	华翔, 梁洪涛, 董兆鑫, 王昭, 姚红娟, 李宝华, 姜冰清. 复杂水系无线监测网络的智能分簇算法研究[J]. 系统仿真学报, 2019, 31(11): 2255-2263.
[14]	张会丽, 李志河. 一种基于HNN的云服务组合优化[J]. 系统仿真学报, 2019, 31(11): 2335-2343.
[15]	刘渊, 邱常伶, 王晓锋, 蒋敏. 面向多尺度融合网络仿真的拓扑映射方法研究[J]. 系统仿真学报, 2019, 31(10): 2030-2041.

基于相似性模块度的层次聚合社区发现算法

Hierarchical Agglomerative Community Detection Algorithm Based on Similarity Modularity

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价