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

所属专题: 先进计算

• 先进计算 • 上一篇    下一篇

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

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

  1. 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 Ping1,2, WANG Fen1, CHEN Qidong1, SUN Jun1   

  1. 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).

摘要: 针对求解复杂网络的多目标社区发现问题,提出了一种离散化随机漂移粒子群优化(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

中图分类号: