Computer Science ›› 2020, Vol. 47 ›› Issue (6A): 461-466.doi: 10.11896/JsJkx.191100215

• Database & Big Data & Data Science • Previous Articles     Next Articles

Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering

DONG Ming-gang, GONG Jia-ming and JING Chao   

  1. School of Information Science and Engineering,Guilin University of Technology,Guilin,Guangxi 541004,China
    Guangxi Key Laboratory of Embedded Technology and Intelligent System,Guilin,Guangxi 541004,China
  • Published:2020-07-07
  • About author:DONG Ming-gang, born in 1977, Ph.D.His main research interests include intelligent computing, multi-obJective optimization and machine learning.
    JING Chao, born in 1983, Ph.D.His main research interests include intelligent computing, optimization and deep reinforcement learning.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61563012,61802085),Natural Science Foundation of Guangxi,China (2014GXNSFAA118371,2015GXNSFBA139260), Guangxi Key Laboratory of Embedded Technology and Intelligent System Foundation(2018A-04) and Guangxi Graduate Program(YCSW201962).

Abstract: The multi-obJective optimization algorithm is competitive in the discovery of complex network communities.However,it is difficult to obtain the satisfied results while dealing with the problem of fuzzy community structure and large scale of network data.To overcome the shortcomings of existing multi-obJective methods,a multi-obJective complex network community discovery algorithm based on spectral clustering is proposed.The proposed algorithm uses spectral clustering to perform initial po-pulation partitioning on the encoded complex network,and exploits its subgraph clustering characteristics to obtain a better initial population.A data reduction method based on grid reduction is applied to reduce the population in the process of evolution,which effectively reduces the complexity of the algorithm.The experimental results on the simulation network and the real network show that the proposed algorithm outperforms than that of the other three representative multi-target based community discovery algorithms in terms of community discovery performance and computational complexity.

Key words: Multi-obJective evolutionary, Community discovery, Complex network, Large-scale network

CLC Number: 

  • TP391
[1] PALLA G.CFinder:locating cliques and overlapping modules in biological networks.Bioinformatics,2006,22(8):1021-1023.
[2] PIZZUTI C,ROMBO S E.Algorithms and tools for protein-protein interaction networks clustering,with a special focus on population-based stochastic methods.Bioinformatics,2014,30(10):1343-1352.
[3] PASTOR-SATORRAS R,VESPIGNANI A.Evolution andStructure of the Internet:A Statistical Physics Approach//Evolution and Structure of the Internet.2004.
[4] WASSERMAN S.Social network analysis:Methods and applica-tions//Cambridge University Press,1994:181-190.
[5] YANG B,LIU D Y,JIN D,et al.Complex network clustering method .Journal of Software,2009,20(1):54-66.
[6] PIZZUTI C.A Multi-obJective Genetic Algorithm for Community Detection in Networks//IEEE International Conference on Tools with Artificial Intelligence.2009.
[7] RAHIMI S,ABDOLLAHPOURI A,MORADI P.A multi-obJective particle swarm optimization algorithm for community detection in complex networks.Swarm and Evolutionary Computation,2018,4(39):297-309.
[8] LIU C,LIU J,JIANG Z.A MultiobJective Evolutionary Algorithm Based on Similarity for Community Detection From Signed Social Networks.IEEE Transactions on Cybernetics,2017,44(12):2274-2287.
[9] ZHANG L,PAN H,SU Y,et al.A Mixed Representation-Based MultiobJective Evolutionary Algorithm for Overlapping Community Detection.IEEE Trans Cybern,2017,PP(99):1-14.
[10] WEN X,CHEN W N,LINY,et al.A Maximal Clique Based MultiobJective Evolutionary Algorithm for Overlapping Community Detection.IEEE Transactions on Evolutionary Computation,2016,PP(99):1-1.
[11] ZHANG X,ZHOU K,PAN H,et al.A Network Reduction-Based MultiobJective Evolutionary Algorithm for Community Detection in Large-Scale Complex Networks.IEEE Transactions on Cybernetics,2018,PP(99):1-14.
[12] CORNE D W,JERRAM N R,KNOWLES J D,et al.PESA-II:region-based selection in evolutionary multiobJective optimization// Conference on Genetic & Evolutionary Computation.2001.
[13] ZHANG S,LIU W Q,ZHAO N.Research of Consensus inMulti-agent Systems on Complex Network .Journal of Frontiers of Computer Science,2019,46(4):101-105.
[14] ANGELINI L,BOCCALETTI S,MARINAZZO D,et al.Identification of network modules by optimization of ratio association.Chaos,2007,17(2):175.
[15] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmultiobJective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[16] ZHOU A,QU B Y,LI H,et al.MultiobJective evolutionary algorithms:A survey of the state of the art.Swarm & Evolutionary Computation,2011,1(1):32-49.
[17] LI J Y,ZHOU J G,GUAN J H,et al.Research progress of spectral clustering algorithm .Journal of Intelligent Systems,2011,6(5):405-414.
[18] NEWMAN M E J.Modularity and community structure in networks.Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[19] LANCICHINETTI A,FORTUNATO S,KERTSZ J.Detec-ting the overlapping and hierarchical community structure in complex networks.New Journal of Physics,2009,11(3):19-44.
[20] ZHANG L,PAN H,SU Y,et al.A Mixed Representation-Based MultiobJective Evolutionary Algorithm for Overlapping Community Detection.IEEE Transactions on Cybernetics,2017,47(9):2703-2716.
[21] ZHANG X,ZHOU K,PAN H,et al.A Network Reduction-Based MultiobJective Evolutionary Algorithm for Community Detection in Large-Scale Complex Networks.IEEE Transactions on Cybernetics,2018,50(2):703-716.
[22] LANCICHINETTI A,FORTUNATO S,RADICCHIF.Benchmark graphs for testing community detection algorithms.Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,78(4 Pt 2):046110.
[23] DANON L,DAZGUILERA A,DUCH J,et al.Comparing community structure identification//Research and Innovation.Policies and Strategies in the Age of Globalization.2005.
[24] LUSSEAU D.The emergent properties of a dolphin social network.Proceedings Biological Sciences,2003,270(2):S186.
[25] ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups.Journal of Anthropological Research,1976,33(4):452-473.
[26] GLEISER P M,DANON L.Community Structure in Jazz.Advances in Complex Systems,2003,6(4):565-573.
[27] GONG M,CAI Q,CHEN X,et al.Complex Network Clustering by MultiobJective Discrete Particle Swarm Optimization Based on Decomposition.IEEE Transactions on Evolutionary Computation,2014,18(1):82-97.
[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] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] RUAN Zi-rui,RUAN Zhong-yuan,SHEN Guo-jiang. Study of TASEP Model Based on Road Networks [J]. Computer Science, 2020, 47(1): 265-269.
[9] ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
[10] CHEN Hang-yu, LI Hui-jia. Analysis of Characteristics and Applications of Chinese Aviation Complex Network Structure [J]. Computer Science, 2019, 46(6A): 300-304.
[11] LIU Xiao-dong, WEI Hai-ping, CAO Yu. Modeling and Stability Analysis for SIRS Model with Network Topology Changes [J]. Computer Science, 2019, 46(6A): 375-379.
[12] ZHANG Sen, LIU Wen-qi, ZHAO Ning. Research of Consensus in Multi-agent Systems on Complex Network [J]. Computer Science, 2019, 46(4): 95-99.
[13] SHAN Na, LI Long-jie, LIU Yu-yang, CHEN Xiao-yun. Link Prediction Based on Correlation of Nodes’ Connecting Patterns [J]. Computer Science, 2019, 46(12): 20-25.
[14] BIN Sheng, SUN Geng-xin. Collaborative Filtering Recommendation Algorithm Based on Multi-relationship Social Network [J]. Computer Science, 2019, 46(12): 56-62.
[15] FU Li-dong, LI Dan, LI Zhan-li. Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks [J]. Computer Science, 2019, 46(12): 322-326.
Full text



[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 .