电子学报 ›› 2021, Vol. 49 ›› Issue (11): 2101-2107.DOI: 10.12263/DZXB.20201094

所属专题: 多目标优化

• 学术论文 • 上一篇    下一篇

基于双编码的重叠社团检测多目标优化方法

张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平   

  1. 安徽大学计算机科学与技术学院计算智能与信号处理教育部重点实验室,安徽 合肥 230601
  • 收稿日期:2020-10-05 修回日期:2021-06-06 出版日期:2021-11-25 发布日期:2021-11-25
  • 作者简介:张 磊 男,1986年5月生于安徽安庆,现为安徽大学计算机科学与技术学院副教授、博士生导师.主要研究方向为多目标优化及其应用、社交网络分析、约束模式挖掘、推荐系统等.E-mail:zl@ahu.edu.cn
    马海平(通讯作者) 女,1986年5月生于安徽合肥,现为安徽大学计算机科学与技术学院讲师.主要研究方向为推荐系统、个性化教育、机器学习等.E-mail:hpma@ahu.edu.cn
  • 基金资助:
    国家自然科学基金(61976001);安徽省自然科学基金(2008085QF309);安徽高校自然科学研究项目(KJ2020A0036)

A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection

Lei ZHANG, Qing LIU, Shang-shang YANG, Hai-peng YANG, Fan CHENG, Hai-ping MA   

  1. Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education,School of Computer Science and Technology,Anhui University,Hefei,Anhui 230601,China
  • Received:2020-10-05 Revised:2021-06-06 Online:2021-11-25 Published:2021-11-25

摘要:

近年来,多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此,本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码,能够有效解码得到重叠社团结构.在双编码表示的基础上,本文提出了一种基于双编码的重叠社团检测多目标优化方法(DRMOEA).在DRMOEA中,为了获得好的初始个体并提高算法检测性能,本文提出了一种基于社团边界点的初始化策略.除此之外,针对双编码中的重叠点编码部分,本文提出了基于精英个体边界点的交叉策略,该策略利用社团边界信息引导种群向好的方向进化,从而有效提高了算法的检测性能.最后,在9个真实世界网络上的实验结果表明DRMOEA算法优于其他5个代表性重叠社团检测算法.

关键词: 复杂网络, 重叠社团检测, 双编码, 多目标优化

Abstract:

In recent years, the multi-objective evolutionary methods have been widely used for solving overlapping community detection problem and have achieved good community division performance. To design appropriate individual encoding and evolution strategies is important to improve the performance of multi-objective overlapping community detection evolutionary algorithm. To this end, a dual representation method is designed to encode the non-overlapping community structures and overlapping nodes respectively, which can effectively obtain the overlapping community structures. On the basis of the dual representation, this paper proposes a dual representation-based multi-objective evolutionary algorithm for overlapping community detection (DRMOEA). In DRMOEA, an initialization strategy based on community boundary nodes is suggested to obtain good initial individuals,with the aim to improve the detection performance of the algorithm. In addition, for the overlapping part of the dual-representation, this paper proposes a crossover strategy according to the boundary nodes of elite individuals, which uses community boundary information to guide the evolution of the population towards a better direction. Finally, the experimental results on nine real-world networks show that the proposed DRMOEA is better than five representative baseline overlapping community detection algorithms.

Key words: complex network, overlapping community detection, dual representation, multi-objective optimization

中图分类号: