基于双编码的重叠社团检测多目标优化方法
A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection
- 电子学报 2021年49卷第11期 页码：2101-2107
- 作者机构：
安徽大学计算机科学与技术学院计算智能与信号处理教育部重点实验室，安徽合肥 230601
- 作者简介：
[ "张 磊 男，1986年5月生于安徽安庆，现为安徽大学计算机科学与技术学院副教授、博士生导师.主要研究方向为多目标优化及其应用、社交网络分析、约束模式挖掘、推荐系统等.E-mail:zl@ahu.edu.cn" ]
[ "马海平(通讯作者) 女，1986年5月生于安徽合肥，现为安徽大学计算机科学与技术学院讲师.主要研究方向为推荐系统、个性化教育、机器学习等.E-mail：hpma@ahu.edu.cn" ]
- 基金信息：国家自然科学基金(61976001;61876184;62076001);安徽省自然科学基金(2008085QF309);安徽高校自然科学研究项目(KJ2020A0036)
DOI：10.12263/DZXB.20201094
中图分类号： TP18收稿：2020-10-05，
修回：2021-06-06，
纸质出版：2021-11-25
- 稿件说明：
移动端阅览
张磊,刘庆,杨尚尚等.基于双编码的重叠社团检测多目标优化方法[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 .
0
浏览量
24
下载量
1
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies