基于共邻节点相似度的社区划分算法

doi:10.11772/j.issn.1001-9081.2019010183

计算机应用 ›› 2019, Vol. 39 ›› Issue (7): 2024-2029.DOI: 10.11772/j.issn.1001-9081.2019010183

基于共邻节点相似度的社区划分算法

付立东^1,2, 郝伟¹, 李丹¹, 李凡¹

1. 西安科技大学计算机科学与技术学院, 西安 710054;
2. 西安电子科技大学计算机科学与技术学院, 西安 710071

收稿日期:2019-01-24 修回日期:2019-03-13 发布日期:2019-04-15 出版日期:2019-07-10
通讯作者: 付立东
作者简介:付立东(1973-),男,陕西西安人,副教授,博士,CCF会员,主要研究方向:复杂网络计算;郝伟(1995-),男,陕西西安人,硕士研究生,主要研究方向:复杂网络计算;李丹(1994-),女,陕西宝鸡人,硕士研究生,主要研究方向:复杂网络计算;李凡(1995-),女,陕西商洛人,硕士研究生,主要研究方向:复杂网络计算。
基金资助:
国家自然科学基金资助项目（61432010，61502363）；西安科技大学博士后科研启动项目（2018QDJ049）。

Community dividing algorithm based on similarity of common neighbor nodes

FU Lidong1,2, HAO Wei1, LI Dan1, LI Fan1

1. College of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an Shaanxi 710054, China;
2. School of Computer Science and Technology, Xidian University, Xi'an Shaanxi 710071, China

Received:2019-01-24 Revised:2019-03-13 Online:2019-04-15 Published:2019-07-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61432010, 61502363), the Postdoctoral Research Start-up Project of Xi'an University of Science and Technology (2018QDJ049).

摘要/Abstract

摘要：

复杂网络中的社区结构能帮助人们认识网络的基本结构及其功能。针对目前多数社区划分算法准确率低、复杂度高的问题，提出了一种基于共邻节点相似度的社区划分算法。首先，为了计算节点间相似度值，提出了相似度模型，该模型通过将被测节点对的邻居节点引入一并计算，提高了相似度度量的准确性；然后，计算节点局部影响力值，能客观地表现出节点在所处网络中的重要性；其次，结合节点相似度值和节点局部影响力值对节点进行层次聚类，完成网络社区结构的初步划分；最后，通过聚合初步划分的子社区，获得复杂网络的最优模块度值。仿真结果表明，在网络的社区特征模糊时，与新的基于局部相似度的社区发现算法（CDALS）相比，所提算法的准确率提高了14%，证明了所提提法更能够准确、有效地划分复杂网络的社区结构。

关键词: 共邻节点, 相似度度量, 节点局部影响力, 模块度, 社区划分

Abstract:

The community structure in complex networks can help people recognize basic structure and functions of network. Aiming at the problems of low accuracy and high complexity of most community division algorithms, a community division algorithm based on similarity of common neighbor nodes was proposed. Firstly, a similarity model was proposed in order to calculate the similarity between nodes. In the model, the accuracy of similarity measurement was improved by calculating the tested node pairs and their neighbor nodes together. Secondly, local influence values of nodes were calculated, objectively showing the importances of nodes in the network. Thirdly, the nodes were hierarchically clustered according to the similarity and local influence values of nodes, and preliminary division of network community structure was completed. Finally, the preliminary divided sub-communities were clustered until the optimal modularity value was obtained. The simulation results show that compared with the new Community Detection Algorithm based on Local Similarity (CDALS), the proposed algorithm has the accuuracy improved by 14%, which proves that the proposed algorithm can divide the community structure of complex networks accurately and effectively.

Key words: common neighbor node, similarity measurement, local influence of node, modularity, community division

中图分类号:

TP399

付立东, 郝伟, 李丹, 李凡. 基于共邻节点相似度的社区划分算法[J]. 计算机应用, 2019, 39(7): 2024-2029.

FU Lidong, HAO Wei, LI Dan, LI Fan. Community dividing algorithm based on similarity of common neighbor nodes[J]. Journal of Computer Applications, 2019, 39(7): 2024-2029.

参考文献

[1] STROGATZ S H. Exploring complex networks[J]. Nature, 2001, 410:268-276.
[2] SCHEFFER M. Complex systems:foreseeing tipping points[J]. Nature, 2010, 467(7314):411-412.
[3] KARSAI M, KIVEL M, PAN R K, et al. Small but slow world:How network topology and burstiness slow down spreading[J]. Physical Review E, 2011, 83(2):025102.
[4] 吴泓润,覃俊,易云飞,等.基于优化理论的社区无标度网络模型[J].计算机学报,2015,38(2):337-348.(WU H R, TAN J, YI Y F, et al. A model of community-structure and scale-free network based on optimization theory[J]. Chinese Journal of Computers, 2015, 38(2):337-348.)
[5] 付立冬,马小科,聂靖靖.进化谱分算法检测动态网络社团结构[J].西安电子科技大学学报(自然科学版),2018,45(2):43-47(FU L D, MA X K, NIE J J. Evolutionary spectral approach to finding communities in dynamic networks[J]. Journal of Xidian University (Natural Science), 2018, 45(2):43-47.)
[6] 刘冰玉,王翠荣,王聪,等.基于动态主题模型融合多维数据的微博社区发现算法[J].软件学报,2017,28(2):246-261.(LIU B Y, WANG C R, WANG C, et al. Microblog community discovery algorithm based on dynamic topic model with multidimensional data fusion[J]. Journal of Software, 2017, 28(2):246-261.)
[7] 付立东,聂靖靖.基于进化谱分方法的动态社团检测[J].计算机科学,2018,45(2):171-174.(FU L D, NIE J J. Dynamic community detection based on evolutionary spectral method[J]. Computer Science, 2018,45(2):171-174.)
[8] ALBERT R, JEONG H, BARABASI A L. The diameter of the World Wide Web[J]. Nature, 1999, 401(6):130-131.
[9] 顾亦然,陈雨晴.一种新的基于局部相似度的社区发现算法[J].南京邮电大学学报(自然科学版),2017,37(5):196-203.(GU Y R, CHEN Y Q. New community detection algorithm based on local similarity[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2017, 37(5):196-203.)
[10] 梁宗文,杨帆,李建平.基于节点相似性度量的社团结构划分方法[J].计算机应用,2015,35(5):1213-1217.(LIANG Z W, YANG F, LI J P. Community structure detection based on node similarity in complex network[J]. Journal of Computer Applications, 2015,35(5):1213-1217.)
[11] 刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报,2011,37(12):1520-1529.(LIU X, YI D Y. Complex network community detection by local similarity[J]. Acta Automatica Sinica, 2011,37(12):1520-1529.)
[12] CHEN Q, WU T T, FANG M. Detecting local community structures in complex networks based on local degree central nodes[J]. Physica A:Statistical Mechanics and its Applications, 2013, 392(3):529-537.
[13] 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, 2008(10):1-12.
[14] LAMBIOTTE R, DELVENNE J C, BARAHONA M. Laplacian dynamics and multiscale modular structure in networks[J]. ArXiv Preprint, 2008, 2008:0812.1770.
[15] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6):066111.
[16] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.
[17] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of Sciences of the United States of America, 2002, 99(12):7821-7826.
[18] NEWMAN M E, GIRVAN M. Finding and evaluating community structure in networks.[J]. Physical Review E, 2004, 69(2):026113.
[19] DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics:Theory and Experiment, 2005, 2005(9):P09008.
[20] ZACHARY W W. An information flow model for conflict and fission in small groups1[J]. Journal of Anthropological Research, 1977, 33(4):452-473.

基于共邻节点相似度的社区划分算法

Community dividing algorithm based on similarity of common neighbor nodes

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[2]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[3]	滕磊, 李苑, 李智星, 胡峰. 基于知识图嵌入的跨社交网络用户对齐算法[J]. 计算机应用, 2019, 39(11): 3198-3203.
[4]	李雷, 闫光辉, 杨绍文, 张海韬. 基于孤立节点分离策略的改进鲁汶算法[J]. 计算机应用, 2017, 37(4): 970-974.
[5]	薛云, 李国和, 吴卫江, 洪云峰, 周晓明. 基于忠诚度的社交网络用户发现方法[J]. 计算机应用, 2017, 37(11): 3095-3100.
[6]	黄泳航, 汤庸, 李春英, 汤志康, 刘继伟. 基于社区划分的学术论文推荐模型[J]. 计算机应用, 2016, 36(5): 1279-1283.
[7]	王天宏, 武星, 兰旺森. 改进的基于局部模块度的社团划分算法[J]. 计算机应用, 2016, 36(5): 1296-1301.
[8]	夏一丹, 王彬, 董迎朝, 刘辉, 熊新. 加权Fast Newman模块化算法在人脑结构网络中的应用[J]. 计算机应用, 2016, 36(12): 3347-3352.
[9]	张嫱嫱, 黄廷磊, 张银明. 基于聚类分析的二分网络社区挖掘[J]. 计算机应用, 2015, 35(12): 3511-3514.
[10]	伍杰华. 基于树状朴素贝叶斯模型的社会网络关系预测[J]. 计算机应用, 2013, 33(11): 3134-3137.
[11]	水超李慧. 基于“次中心”的社区结构探寻算法[J]. 计算机应用, 2012, 32(08): 2154-2158.
[12]	王艳群李海芳郭浩陈俊杰. 静息态脑功能网络的社团结构研究[J]. 计算机应用, 2012, 32(07): 2044-2048.
[13]	张明李娟. 改进的三维模型形状分布检索算法[J]. 计算机应用, 2012, 32(05): 1276-1279.
[14]	于海群刘万军邱云飞. 基于用户话题偏好的社会网络二级人脉推荐[J]. 计算机应用, 2012, 32(05): 1366-1270.
[15]	罗锦坤元昌安杨文胡卉颖袁晖. 基于基因表达式编程算法的复杂网络社区结构划分[J]. 计算机应用, 2012, 32(02): 317-321.