复杂网络社区发现的多目标五行环优化算法

doi:10.11896/jsjkx.190700082

摘要/Abstract

摘要： 社区结构作为复杂网络的重要特性, 对理解网络的功能和结构具有重要意义。为了解决复杂网络的社区发现问题, 提出了一种多目标五行环优化算法(Multi-Objective Five-Elements Cycle Optimization, MOFECO)。首先, 将社区发现问题建模为多目标优化问题, 选取反比率关联(Inverse Ratio Association, IRA)和比例缩减(Ratio Cut, RC)这两个互相对立的目标作为目标函数;然后, 基于五行环模型(Five-Elements Cycle Model, FECM), 通过局部最优解和全局最优解实现元素的更新, 并引入交叉和变异算子对更新策略进行改进;最后, 使用快速非支配排序的方法获得Pareto最优社区划分集合, 有助于揭示复杂网络的层次结构。在人工合成网络和真实社会网络上进行实验, 与单目标算法(GA-Net, Meme-Net)以及多目标算法(MOGA-Net, MOCD, MOEA/D-Net, DMOPSO, DIM-MOEA/D, MOCD-ACO)进行对比得出, MOFECO算法弥补了传统单目标优化社区结构划分单一的缺陷, 在社区发现的准确度上有所提高。

关键词: 多目标优化, 复杂网络, 进化算法, 社区发现, 五行环优化算法

Abstract: As an important property of complex networks, community structure is of great significance for understanding the function and organization of networks.In order to solve the community discovery problem of complex networks, a multi-objective five-elements cycle optimization algorithm (MOFECO) is proposed.Firstly, the task of the community discovery is modelled as a multi-objective optimization problem, and two opposite targets, inverse ratio vssociation (IRA) and ratio cut (RC) are selected as the objective function.Then, based on five-elements cycle model (FECM), individual updating is implemented through local optimal individuals and global optimal individuals, and crossover and mutation operators are introduced to improve the update strategy.Finally, the fast non-dominated sorting method is used to obtain the Pareto optimal community partitioning set, which is helpful to reveal the hierarchical structure of complex networks.Experiments are conducted on LFR benchmark networks and real social networks, compared with single-objective algorithms(GA-Net, Meme-Net) and multi-objective algorithms, such as MOGA-Net, MOCD, MOEA/D-Net, DMOPSO, DIM-MOEA/D and MOCD-ACO, MOFECO overcomes the shortcomings of traditional single-objective optimization of community structure division, and improves the accuracy of community discovery.

Key words: Community discovery, Complex network, Evolutionary algorithm, Five-elements cycle optimization, Multi-objective optimization

中图分类号:

TP391

张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082

ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery[J]. Computer Science, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082

参考文献

[1]FORTUNATO S.Community Detection in Grap-hs[J].Physics Reports, 2009, 486(3/4/5):75-174.
[2]GIRVAN M, NEWMAN M E J.Community Structure in Social and Biological Networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2001, 99(12):7821-7826.
[3]RADICCHI F, CASTELLANO C, CECCONI F, et al.Definingand Identifying Communities in Networks[J].Proceedings of the National Academy of Sciences of the United States of Ame-rica, 2003, 101(9):2658-2663.
[4]PIZZUTI C.GA-Net:A Genetic Algorithm for Community Detection in Social Networks[C]∥Parallel Problem Solving from Nature-PPSN X, 10th International Conference Dortmund.Heidelberg:Springer-Verlag, 2008:1081-1090.
[5]GONG M, FU B, JIAO L, et al.Memetic Algorithm for Community Detection in Networks[J].Physical Review E, 2011, 84(5):056101.
[6]PIZZUTI C.A Multiobjective Genetic Algorithm to Find Communities in Complex Networks[J].IEEE Transactions on Evolutionary Computation, 2012, 16(3):418-430.
[7]DEB K, PRATAP A, AGARWAL S, et al.A fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[8]SHI C, YAN Z, CAI Y, et al.Multi-objective Community Detection in Complex Networks[J].Applied Soft Computing, 2012, 12(2):850-859.
[9]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.
[10]LI L, JIAO L, ZHAO J, et al.Quantum-behaved Discrete Multi-objective Particle Swarm Optimizati-on for Complex Network Clustering[J].Pattern Recognition, 2016, 63:1-14.
[11]ZOU F, CHEN D B, HUANG D S, et al.Inverse Modelling-based Multi-objective Evolutionary Algorithm with Decomposition for Community Detection in Complex Networks[J].Physica A:Statistical Mechanics and its Applications, 2019, 513:662-674.
[12]JI P, ZHANG S, ZHOU Z P.A Decomposition-based Ant Colony Optimization Algorithm for the Multi-objective Community Detection[J].Journal of Ambient Intelligence and Humanized Computing, 2019:1-16.
[13]MA X L, LIU F, QI X D, et al.A Multiobjective Evolutionary Algorithm Based on Decision Variable Analyses for Multiobjective Optimization Problems With Large-Scale Variables[J].IEEE Transactions on Evolutionary Computation, 2016, 20(2):275-298.
[14]LIU M D.Research and Analysis of a Novel Heuristic Algo-rithm:Five-elements Cycle Optimization Algorithm[J].Acta Automatica Sinica, 2019:1-15.
[15]LIU M D.Five-elements Cycle Optimization Algorithm for the Travelling Salesman Problem[C]∥2017 18th International Conference on Advanced Robotics (ICAR).Hong Kong:IEEE Press 2017:595-601.
[16]HANGL J, KNOWLES J D.An Evolutionary Approach to Multiobjective Clustering[J].IEEE Transactions on Evolutionary Computation, 2007, 11(1):56-76.
[17]LI Z, ZHANG S, WANG R S, et al.Quantitative Function for Community Detection[J].Physical Review E, 2008, 77(3 Pt 2):036109.
[18]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):023114.
[19]LANCICHINETTI A, FORTUNATO S, RADICCHI F.Benchmark Graphs for Testing Community Detection Algorithms[J].Physical Review E, 2008, 78(4 Pt 2):046110.
[20]ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups1[J].Journal of anthropological research, 1976, 33(4):452-473.
[21]LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al.The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-lasting Associations[J].Behavioral Ecolo-gy & Sociobiology, 2003, 54(4):396-405.
[22]GUIMERA R, DANON L, DIAZ-GUILERA A, et al.Self-similar Community Structure in a Network of Human Interactions[J].Physical Review E, 2004, 68(6 Pt 2):065103.
[23]DUCH J, ARENAS A.Community Detection in Complex Networks Using Extremal Optimization[J].Physical Review E, 2005, 72(2 Pt 2):027104.
[24]DANON L, DUCH J, DIAZ-GUILERA A, et al.ComparingCommunity Structure Identification[J].Journal of Statistical Mechanics, 2005, 2005(9):09008.
[25]NEWMAN M E J, GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2):026113.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	刘宝宝, 杨菁菁, 陶露, 王贺应. 基于DE-LSTM模型的教育统计数据预测研究 Study on Prediction of Educational Statistical Data Based on DE-LSTM Model 计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[3]	何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159
[4]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[5]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[6]	孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法 Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[7]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[8]	李浩东, 胡洁, 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用 Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application 计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[9]	唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275
[10]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[11]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[12]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[13]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[14]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[15]	陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed