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

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] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[2] YANG Bo, LI Yuan-biao. Complex Network Analysis on Curriculum System of Data Science and Big Data Technology [J]. Computer Science, 2022, 49(6A): 680-685.
[3] HE Yi-chen, MAO Yi-jun, XIE Xian-fen, GU Wan-rong. Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation [J]. Computer Science, 2022, 49(6A): 272-279.
[4] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[5] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[6] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[7] LI Hao-dong, HU Jie, FAN Qin-qin. Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application [J]. Computer Science, 2022, 49(5): 212-220.
[8] PENG Dong-yang, WANG Rui, HU Gu-yu, ZU Jia-chen, WANG Tian-feng. Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos [J]. Computer Science, 2022, 49(4): 312-320.
[9] TANG Chun-yang, XIAO Yu-zhi, ZHAO Hai-xing, YE Zhong-lin, ZHANG Na. EWCC Community Discovery Algorithm for Two-Layer Network [J]. Computer Science, 2022, 49(4): 49-55.
[10] CHEN Shi-cong, YUAN De-yu, HUANG Shu-hua, YANG Ming. Node Label Classification Algorithm Based on Structural Depth Network Embedding Model [J]. Computer Science, 2022, 49(3): 105-112.
[11] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[12] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[13] GUAN Zheng, DENG Yang-lin, NIE Ren-can. Non-negative Matrix Factorization Based on Spectral Reconstruction Constraint for Hyperspectral and Panchromatic Image Fusion [J]. Computer Science, 2021, 48(9): 153-159.
[14] MU Jun-fang, ZHENG Wen-ping, WANG Jie, LIANG Ji-ye. Robustness Analysis of Complex Network Based on Rewiring Mechanism [J]. Computer Science, 2021, 48(7): 130-136.
[15] HU Jun, WANG Yu-tong, HE Xin-wei, WU Hui-dong, LI Hui-jia. Analysis and Application of Global Aviation Network Structure Based on Complex Network [J]. Computer Science, 2021, 48(6A): 321-325.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!