求解多目标社区发现问题的离散化随机漂移粒子群优化算法

doi:10.11772/j.issn.1001-9081.2020060800

计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 803-811.DOI: 10.11772/j.issn.1001-9081.2020060800

所属专题：先进计算

求解多目标社区发现问题的离散化随机漂移粒子群优化算法

李萍^1,2, 汪芬¹, 陈祺东¹, 孙俊¹

1. 人工智能与模式识别国际联合实验室(江南大学), 江苏无锡 214122;
2. 无锡职业技术学院物联网技术学院, 江苏无锡 214121

收稿日期:2020-06-12 修回日期:2020-11-12 出版日期:2021-03-10 发布日期:2020-12-22
通讯作者: 汪芬
作者简介:李萍(1977-),女,江苏高邮人,副教授,硕士,CCF会员,主要研究方向:数据挖掘、模式识别;汪芬(1995-),女,安徽安庆人,硕士,主要研究方向:数据挖掘;陈祺东(1992-),男,浙江湖州人,博士,主要研究方向:群体智能、机器学习;孙俊(1971-),男,江苏无锡人,教授,博士生导师,博士,主要研究方向:人工智能、模式识别。
基金资助:
国家自然科学基金资助项目（61672263）；江苏省“青蓝工程”优秀教学团队项目（苏教师函[2020]10号）。

Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem

LI Ping^1,2, WANG Fen¹, CHEN Qidong¹, SUN Jun¹

1. International Joint Laboratory of Pattern Recognition and Artificial Intelligence(Jiangnan University), Wuxi Jiangsu 214122, China;
2. School of Internet of Things, Wuxi Institute of Technology, Wuxi Jiangsu 214121, China

Received:2020-06-12 Revised:2020-11-12 Online:2021-03-10 Published:2020-12-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61672263), the Project of "Qing Lan Program" Excellent Teaching Team (No.10 of Official Document from Jangsu Eduction Department in 2020).

摘要/Abstract

摘要： 针对求解复杂网络的多目标社区发现问题，提出了一种离散化随机漂移粒子群优化（DRDPSO）算法。首先，通过对社区进行随机化编码操作和针对随机漂移算法的离散化操作，来改善局部网络结构并逐渐增强全局模块度值；其次，根据核K均值（KKM）和比例割（RC）两个目标函数来控制网络中的社区规模、缓解模块度分辨率限制；最后，根据多目标求解策略逐步更新Pareto非劣解集，从Pareto非劣解集选取满足需求的目标社区结构。为了验证所提算法的有效性，将DRDPSO算法与其他社区发现算法在三种具有10个不同参数设置的生成网络及三种真实网络上进行对比实验，并采用两个最佳社区评价指标对各算法获得的社区发现结果进行对比分析。实验结果表明，使用DRDPSO算法求解复杂网络的多目标社区发现问题时，获得的社区发现评价指标（归一化互信息和模块度）最高的概率达到95%以上。可见DRDPSO算法在真实网络进行应用能进一步地提高网络社区划分的精确度和鲁棒性。

关键词: 社区发现, 多目标复杂网络, 离散化, 随机漂移粒子群优化, 模块度, Pareto非劣解集

Abstract: For solving the problem of multi-objective community detection in complex network, a Discrete Random Drift Particle Swarm Optimization (DRDPSO) algorithm was proposed. Firstly, by performing random coding operation on communities and using discretization operation for random drift optimization algorithm, the local network structure was improved and the global modularity value was gradually enhanced. Secondly, two objective functions, Kernel K-Means (KKM) and Ratio Cut (RC), were used to control the community size in the network and ameliorate the modularity resolution ratio. Finally, the Pareto non-inferior solution sets were updated step by step according to the multi-objective solving strategy, and the objective community structures satisfying the requirements were selected from the Pareto non-inferior solution sets. To verify the effectiveness of proposed algorithm, the comparison experiments of DRDPSO algorithm with other community detection algorithms were carried out on three generation networks with 10 different parameter configurations and three real networks. And the community detection results obtained by different algorithms were compared and analyzed by using two evaluation indicators of best community. Experimental results show that using DRDPSO algorithm for solving the multi-objective community detection problem in complex network, the probability of obtaining the highest community detection evaluation indexes (normalized mutual information and modularity) is more than 95%. The application of DRDPSO algorithm in real network can further improve the accuracy and robustness of network community division.

Key words: community detection, multi-objective complex network, discretization, Random Drift Particle Swam Optimization (RDPSO), modularity, Pareto non-inferior solution set

中图分类号:

TP301.6
TP18

李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.

LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem[J]. Journal of Computer Applications, 2021, 41(3): 803-811.

参考文献

[1] VILLANDRE L,STEPHENS D A,LABBE A,et al. Assessment of overlap of phylogenetic transmission clusters and communities in simple sexual contact networks:applications to HIV-1[J]. PLoS One, 2016, 11(2):No. e0148459.
[2] AI J,LIU Y,SU Z,et al. Link prediction in recommender systems based on multi-factor network modeling and community detection[J]. EPL(Europhysics Letters),2019,126(3):No. 38003.
[3] BIOGLIO L,PENSA R G. Impact of neighbors on the privacy of individuals in online social networks[J]. Procedia Computer Science,2017,108:28-37.
[4] 李金华. 广义创新网络的演化结构及其现实意义[J]. 科学学与科学技术管理,2008,29(2):101-107. (LI J H. Evolving structure of generalized innovation networks and its practical implications[J]. Science of Science and Management of S. & T., 2008, 29(2):101-107.)
[5] 赵卫绩, 张凤斌, 刘井莲. 复杂网络社区发现研究进展[J]. 计算机科学,2020,47(2):10-20.(ZHAO W J,ZHANG F B,LIU J L. Review on community detection in complex networks[J]. Compute Science,2020,47(2):10-20.)
[6] GIRVAN M,NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Science of the United States of America,2002,99(12):7821-7826.
[7] ROSVALL M,BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008,105(4):1118-1123.
[8] RAGHAVAN U N,ALBERT R,KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E,Statistical,Nonlinear,and Soft Matter Physics,2007,76(3 Pt 2):No. 036106.
[9] DONG S. Improved label propagation algorithm for overlapping community detection[J]. Computing,2020,102(10):2185-2198.
[10] NEWMAN M E J. Fast algorithm for detecting community structure in network[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004:69(6 Pt 2):No. 066133.
[11] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[12] CLAUSET A,NEWMAN M E J,MOORE C. Finding community structure in very large networks[J]. Physical Review E, Statistical,Nonlinear,and Soft Matter Physics,2004,70(6 Pt 2):No. 066111.
[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,2008:No. P10008.
[14] SMITH K,JANIKOW C,CLIMER S. Evolving to recognize highdimensional relationships in data:GA operators and representation designed expressly for community detection[C]//Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion. New York:ACM,2019:308-309.
[15] 陈永建, 周艳, 刘超英. 基于遗传算法的大规模社交网络社区发现算法[J]. 计算机工程与设计,2018,39(8):2452-2459. (CHEN Y J, ZHOU Y, LIU C Y. Community discovering algorithm of large scale social networks based on genetic algorithm[J]. Computer Engineering and Design,2018,39(8):2452-2459.)
[16] 张英杰, 龚中汉, 陈乾坤. 基于免疫离散差分进化算法的复杂网络社区发现[J]. 自动化学报,2015,41(4):749-757. (ZHANG Y J,GONG Z H,CHEN Q K. Community detection in complex networks using immune discrete differential evolution algorithm[J]. Acta Automatica Sinica,2015,41(4):749-757.)
[17] BELKHIRI Y, KAMELN, DIRAS H, et al. Bee swarm optimization for community detection in complex network[C]//Proceedings of the 2017 World Conference on Information System and Technologies,AISC 570. Cham:Springer,2017:73-85.
[18] CAI Q,GONG M,MA L,et al. Greedy discrete particle swarm optimization for large-scale social network clustering[J]. Information Sciences,2015,316:503-516.
[19] CAI X,SHI Y,ZHU Y,et al. An algorithm Q-PSO for community detection in complex networks[C]//Proceedings of the 16th International Symposium on Distributed Computing and Applications to Business,Engineering and Science. Piscataway:IEEE,2017:76-79.
[20] 孙延维, 彭智明, 李健波. 基于粒子群优化与模糊聚类的社区发现算法[J]. 重庆邮电大学学报(自然科学版),2015,27(5):660-666.(SUN Y W,PENG Z M,LI J B. Community detection algorithm based on particle swarm optimization and fuzzy clustering[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2015,27(5):660-666.)
[21] CAI Q,GONG M,SHEN B,et al. Discrete particle swarm optimization for identifying community structures in signed social networks[J]. Neural Networks,2014,58:4-13.
[22] CAO C,NI Q,ZHAI Y. A novel community detection method based on discrete particle swarm optimization algorithms in complex networks[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2015:171-178.
[23] CHAITANYA K,SOMAYAJULU D,KRISHNA P R. A PSO based community detection in social networks with node attributes[C]//Proceedings of the 2018 IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2018:1-6.
[24] SUN J,WU X,PALADE V,et al. Random drift particle swarm optimization algorithm:convergence analysis and parameter selection[J]. Machine Learning,2015,101(1/2/3):345-376.
[25] RADICCHI F,CASTELLANO C,CECCONI F,et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004,101(9):2658-2663.
[26] FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010,486(3/4/5):75-174.
[27] ANGELINI L, BOCCALETTI S, MARINAZZO D, et al. Identification of network modules by optimization of ratio association[J]. Chaos:An Interdisciplinary Journal of Nonlinear Science,2007,17(2):No. 023114.
[28] 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-41.
[29] CLERC M, KENNEDY J. The particle swarm:explosion, stability,and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.
[30] 邱晓辉, 陈羽中. 一种面向社会网络社区发现的改进粒子群优化算法[J]. 小型微型计算机系统,2014,35(6):1422-1426. (QIU X H,CHEN Y Z. An improved particle-swarm-optimization algorithm for community discovery in social networks[J]. Journal of Chinese Computer Systems,2014,35(6):1422-1426.)
[31] GONG M,CAI Q,LI Y,et al. An improved memetic algorithm for community detection in complex networks[C]//Proceedings of the 2012 IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2012:1-8.
[32] SHANG R,LUO S,LI Y,et al. Large-scale community detection based on node membership grade and sub-communities integration[J]. Physica A:Statistical Mechanics and its Applications, 2015,428:279-294.
[33] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E,Statistical, Nonlinear, and Soft Matter Physics,2008,78(4 Pt 2):No. 046110.

求解多目标社区发现问题的离散化随机漂移粒子群优化算法

Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	秦丽, 郝志刚, 李国亮. 国家食品安全标准图谱的构建及关联性分析[J]. 计算机应用, 2021, 41(4): 1005-1011.
[2]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[3]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[4]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[5]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[6]	李莎莎, 梁冬阳, 余杰, 纪斌, 马俊, 谭郁松, 吴庆波. 基于师门关系的研究团队挖掘算法[J]. 计算机应用, 2020, 40(11): 3198-3202.
[7]	付立东, 郝伟, 李丹, 李凡. 基于共邻节点相似度的社区划分算法[J]. 计算机应用, 2019, 39(7): 2024-2029.
[8]	张琪, 纪淑娟, 傅强, 张纯金. 基于带权评论图的水军群组检测及特征分析[J]. 计算机应用, 2019, 39(6): 1595-1600.
[9]	陈婉杰, 盛益强. 基于网络表示学习的非单一维度的社区发现算法[J]. 计算机应用, 2019, 39(12): 3467-3475.
[10]	杜航原, 裴希亚, 王文剑. 面向属性网络的重叠社区发现算法[J]. 计算机应用, 2019, 39(11): 3151-3157.
[11]	顾军华, 霍士杰, 王守彬, 田喆. 基于节点中心性和社区相似性的快速标签传播算法[J]. 计算机应用, 2018, 38(5): 1320-1326.
[12]	杨张龙, 陈明. 大规模网格模型间的快速视觉布尔运算[J]. 计算机应用, 2017, 37(7): 2050-2056.
[13]	江洋, 李成海. 基于改进变精度粗糙集的漏洞威胁评估[J]. 计算机应用, 2017, 37(5): 1353-1356.
[14]	李雷, 闫光辉, 杨绍文, 张海韬. 基于孤立节点分离策略的改进鲁汶算法[J]. 计算机应用, 2017, 37(4): 970-974.
[15]	霍纬纲, 程震, 程文莉. 面向不等长多维时间序列的聚类改进算法[J]. 计算机应用, 2017, 37(12): 3477-3481.