Computer Science ›› 2020, Vol. 47 ›› Issue (8): 284-290.doi: 10.11896/jsjkx.190700082

Previous Articles     Next Articles

Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery

ZHANG Qing-qi, LIU Man-dan   

  1. School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:ZHANG Qing-qi, born in 1996, postgraduate.Her main research interests include data mining in networks and intelligent optimization algorithm.
    LIU Man-dan, born in 1973, Ph.D, professor, Ph.D supervisor.Her research interests include control and optimization, application of intelligent methods, such as neural network and evolutio-nary computing, in control process.

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: Complex network, Multi-objective optimization, Community discovery, Five-elements cycle optimization, Evolutionary algorithm

CLC Number: 

  • TP391
[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.
[1] YANG Chao, LIU Zhi. Study on Complex Network Cascading Failure Based on Totally Asymmetric Simple Exclusion Process Model [J]. Computer Science, 2020, 47(9): 265-269.
[2] ZHANG Meng-yue, HU Jun, YAN Guan, LI Hui-jia. Analysis of China’s Patent Application Concern Based on Visibility Graph Network [J]. Computer Science, 2020, 47(8): 189-194.
[3] WANG Hui, LE Zi-chun, GONG Xuan, WU Yu-kun, ZUO Hao. Review of Link Prediction Methods Based on Feature Classification [J]. Computer Science, 2020, 47(8): 302-312.
[4] ZHENG You-lian, LEI De-ming, ZHENG Qiao-xian. Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling [J]. Computer Science, 2020, 47(7): 186-191.
[5] CHEN Meng-hui, CAO Qian-feng and LAN Yan-qi. Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem [J]. Computer Science, 2020, 47(6A): 108-113.
[6] DONG Ming-gang, GONG Jia-ming and JING Chao. Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering [J]. Computer Science, 2020, 47(6A): 461-466.
[7] ZHAO Song-hui, REN Zhi-lei, JIANG He. Multi-objective Optimization Methods for Software Upgradeability Problem [J]. Computer Science, 2020, 47(6): 16-23.
[8] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[9] SUN Min, CHEN Zhong-xiong, YE Qiao-nan. Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment [J]. Computer Science, 2020, 47(6): 252-259.
[10] YUAN Rong, SONG Yu-rong, MENG Fan-rong. Link Prediction Method Based on Weighted Network Topology Weight [J]. Computer Science, 2020, 47(5): 265-270.
[11] MA Yang, CHENG Guang-quan, LIANG Xing-xing, LI Yan, YANG Yu-ling, LIU Zhong. Improved SDNE in Weighted Directed Network [J]. Computer Science, 2020, 47(4): 233-237.
[12] ZHANG Hu, ZHOU Jing-jing, GAO Hai-hui, WANG Xin. Network Representation Learning Method on Fusing Node Structure and Content [J]. Computer Science, 2020, 47(12): 119-124.
[13] YANG Hao, CHEN HONG-mei. Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm [J]. Computer Science, 2020, 47(11): 88-94.
[14] WANG Xu-liang, NIE Tie-zheng, TANG Xin-ran, HUANG Ju, LI Di, YAN Ming-sen, LIU Chang. Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing [J]. Computer Science, 2020, 47(11): 122-127.
[15] XIE Teng-yu,ZHOU Xiao-gen,HU Jun,ZHANG Gui-jun. Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm [J]. Computer Science, 2020, 47(1): 59-65.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .