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

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

doi:10.12263/DZXB.20201094

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection
- ACTA ELECTRONICA SINICA Vol. 49, Issue 11, Pages: 2101-2107(2021)
- 作者机构：
  
  安徽大学计算机科学与技术学院计算智能与信号处理教育部重点实验室，安徽合肥 230601
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20201094
  CLC： TP18
- Received：05 October 2020，
  
  Revised：2021-06-06，
  
  Published：25 November 2021
- 稿件说明：
移动端阅览
张磊,刘庆,杨尚尚等.基于双编码的重叠社团检测多目标优化方法[J].电子学报,2021,49(11):2101-2107.

ZHANG Lei,LIU Qing,YANG Shang-shang,et al.A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection[J].ACTA ELECTRONICA SINICA,2021,49(11):2101-2107.
张磊,刘庆,杨尚尚等.基于双编码的重叠社团检测多目标优化方法[J].电子学报,2021,49(11):2101-2107. DOI： 10.12263/DZXB.20201094.

ZHANG Lei,LIU Qing,YANG Shang-shang,et al.A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection[J].ACTA ELECTRONICA SINICA,2021,49(11):2101-2107. DOI： 10.12263/DZXB.20201094.

摘要

近年来，多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此，本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码，能够有效解码得到重叠社团结构.在双编码表示的基础上，本文提出了一种基于双编码的重叠社团检测多目标优化方法(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.

关键词

Keywords

references

Pizzuti C , Rombo S E . Algorithms and tools for protein-protein interaction networks clustering, with a special focus on population-based stochastic methods [J]. Bioinformatics , 2014 , 30 ( 10 ): 1343 - 1352 .

Harakawa R , Ogawa T , Haseyama M . Accurate and efficient extraction of hierarchical structure of web communities for web video retrieval [J]. ITE Transactions on Media Technology & Applications , 2016 , 4 ( 1 ): 49 - 59 .

Jie Y , Zhishuai L , Qiu X . Community detection in complex networks: Algorithms and analysis [A]. International Conference on Trustworthy Computing and Services [C]. Berlin, Heidelberg : Springer , 2014 . 238 - 244 .

Ahn Y Y , Bagrow J P , Lehmann S . Link communities reveal multiscale complexity in networks [J]. Nature , 2010 , 466 ( 7307 ): 761 - 764 .

Palla G , Derényi Imre , Farkas Illés , et al . Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature , 2005 , 435 ( 7043 ): 814 - 818 .

於志勇 , 陈基杰 , 郭昆 , 等 . 基于影响力与种子扩展的重叠社区发现 [J]. 电子学报 , 2019 , 47 ( 1 ): 153 - 160 .

Yu Z Y , Chen J J , Guo K , et al . Overlapping community detection based on influence and seeds extension [J]. Acta Electronica Sinica , 2019 , 47 ( 1 ): 153 - 160 . (in Chinese)

Sun H , Liu J , Huang J , et al . CenLP: A centrality-based label propagation algorithm for community detection in networks [J]. Physica A: Statistical Mechanics and Its Applications , 2015 , 436 : 767 - 780 .

Sun P G , Gao L , Han S S . Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks [J]. Information Sciences , 2011 , 181 ( 6 ): 1060 - 1071 .

公茂果 , 焦李成 , 杨咚咚 , 等 . 进化多目标优化算法研究 [J]. 软件学报 , 2009 , 20 ( 2 ): 271 - 289 .

巩敦卫 , 季新芳 , 孙晓燕 . 基于集合的高维多目标优化问题的进化算法 [J]. 电子学报 , 2014 , 42 ( 1 ): 77 - 83 .

GONG Dun-wei , JI Xin-fang , SUN Xiao-yan . Solving many-objective optimization problems using set-based evolutionary algorithms [J]. Acta Electronica Sinica , 2014 , 42 ( 1 ): 77 - 83 . (in Chinese)

Liu J , Zhong W , Abbass H A , et al . Separated and overlapping community detection in complex networks using multiobjective evolutionary algorithms [A]. IEEE Congress on Evolutionary Computation [C]. IEEE , 2010 . 1 - 7 .

Liu C , Liu J , Jiang Z . A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks [J]. IEEE Transactions on Cybernetics , 2014 , 44 ( 12 ): 2274 - 2287 .

Li Y , Wang Y , Chen J , et al . Overlapping community detection through an improved multi-objective quantum-behaved particle swarm optimization [J]. Journal of Heuristics , 2015 , 21 ( 4 ): 549 - 575 .

Wen X , Chen W N , Lin Y , et al . A maximal clique based multiobjective evolutionary algorithm for overlapping community detection [J]. IEEE Transactions on Evolutionary Computation , 2017 , 21 ( 3 ): 363 - 377 .

Zhang L , Pan H , Su Y , et al . A mixed representation-based multiobjective evolutionary algorithm for overlapping community detection [J]. IEEE Transactions on Cybernetics , 2017 , 47 ( 9 ): 2703 - 2716 .

Gema B O , Sancho S S , David C . A multi-objective genetic algorithm for overlapping community detection based on edge encoding [J]. Information Sciences , 2018 , 462 : 290 - 314 .

Tian Y , Yang S , Zhang X . An evolutionary multiobjective optimization based fuzzy method for overlapping community detection [J]. IEEE Transactions on Fuzzy Systems , 2020 , 28 ( 11 ): 2841 - 2855 .

Gong M , Ma L , Zhang Q , et al . Community detection in networks by using multiobjective evolutionary algorithm with decomposition [J]. Physica A: Statistical Mechanics and Its Applications , 2012 , 391 ( 15 ): 4050 - 4060 .

Wei Y C , Cheng C K . Ratio cut partitioning for hierarchical designs [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 1991 , 10 ( 7 ): 911 - 921 .

Gong M , Fu B , Jiao L , et al . Memetic algorithm for community detection in networks [J]. Physical Review E , 2011 , 84 ( 5 ): 056101 .

Nicosia V , Mangioni G , Carchiolo V , et al . Extending the definition of modularity to directed graphs with overlapping communities [J]. Journal of Statistical Mechanics Theory & Experiment , 2009 , 2009( 03 ): 3166 - 3168 .

Lancichinetti A , Fortunato S , Kertész J . Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics , 2009 , 11 ( 3 ): 033015 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Comprehensive Causality Multi-Objective Counterfactual Explanation with Feature Selection

Yaw Stability Control of Distributed Drive Electric Vehicle Based on Multi-Objective Parallel Chaos Optimization

A Review of Visibility Graph Methods Research in Time Series Complex Network Analysis

Multi-Objective Path Planning Algorithm for WRSN with Time Window

Research on Recombination Operator and Multi-Objective Optimization Based on Fitness Guided Mating Restriction Strategy

Related Author

LIU Jin-ping

TANG Hao-nan

LI Xing-wang

XU Peng-fei

YUAN Sheng-wei

XIAO Xiang-hui

SONG Yun-hao

SHI Ke

Related Institution

College of Information Science and Engineering, Hunan Normal University

College of Electrical and Information Engineering, Hunan University

Guangdong Provincial Key Laboratory of Industrial Intelligent Inspection Technology

School of Mechatronic Engineering and Automation, Foshan University

College of Business， Quanzhou Normal University

⁰