一种基于差分进化的社团检测算法
|
摘要
复杂网络的社团结构分析可抽象为一个优化问题,用进化算法求解。进化类算法的一个基本问题是如何把问题的候选解编码到进化个体中。本文将索引局部邻接表示法用于社团检测进化算法的个体表示,把社团结构分析转化为一个整数优化问题。在该个体表示方法的基础上,提出了一种基于差分进化的社团检测算法。在一组合成网络和真实网络上验证了算法性能,并与两种基于遗传算法的典型社团检测进化算法进行了对比。实验结果表明,当网络社团结构较为清晰时,基于差分进化的算法检测到的社团结构具有更好的质量。
Community structure analysis of complex networks can be modeled as an optimizing problem,and then be solved by Evolution Algorithm(EA).One fundamental issue of EA is how to encode a candidate solution into an evolution individual.In this paper,the Indexed Locus-based Adjacency Representation(ILAR) of evolution individual encoding for the community detection problem is proposed.Therefore,a community detection problem can be converted to a discrete integer optimization problem.Based on the ILAR,a community detection algorithm that uses Differential Evolution(DE) as the search engine is developed.A number of experiments are conducted on synthesized and real-world networks to verify the performance of the proposed algorithm,and the results are compared against those of two typical community detection algorithms based on Genetic Algorithm(GA).The experiment results show that the community structure discovered by the proposed DE-based algorithm generally has better quality than those of the two compared algorithms as the community structure of the analyzed network is sound.
Community structure analysis of complex networks can be modeled as an optimizing problem,and then be solved by Evolution Algorithm(EA).One fundamental issue of EA is how to encode a candidate solution into an evolution individual.In this paper,the Indexed Locus-based Adjacency Representation(ILAR) of evolution individual encoding for the community detection problem is proposed.Therefore,a community detection problem can be converted to a discrete integer optimization problem.Based on the ILAR,a community detection algorithm that uses Differential Evolution(DE) as the search engine is developed.A number of experiments are conducted on synthesized and real-world networks to verify the performance of the proposed algorithm,and the results are compared against those of two typical community detection algorithms based on Genetic Algorithm(GA).The experiment results show that the community structure discovered by the proposed DE-based algorithm generally has better quality than those of the two compared algorithms as the community structure of the analyzed network is sound.
引文
[1]Han Liu,Fan Yang,Ding Liu.Genetic algorithm optimizing modularity for community detection in complex networks[C].Proceedings of the 35th Chinese Control Conference,2016:1252-1256.
[2]Clara Pizzuti.A multiobjective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutionary Computation,2012,16(3):418-430.
[3]Zhang Xiaohong,Zhang Bin,Zhang Changsheng,et al.A multiobjective hybrid genetic algorithm for detecting communities in complex networks[C].2016 12th International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery,2016:691-695.
[4]Mursel Tasgin,Haluk Bingol.Community detection in complex networks using genetic algorithm[EB/OL].https://arxiv.org/abs/1509.00556,2017-11-02.
[5]Clara Pizzuti.Boosting the detection of modular community structure with genetic algorithms and local search[C].The 27th Annual ACM Symposium on Applied Computing,2012:226-231.
[6]G.Jia,Z.Cai,M.Musolesi,et al.Community detection in social and biological networks using differential evolution[C].The6th International Conference on Learning and Intelligent Optimization,2012:71-85.
[7]Wang Guoshun,Zhang Xuan,Jia Guanbo,et al.Application of Algorithm used in Community Detection of Complex Network[J].International Journal of Future Generation Communication and Networking,2013,6(4):219-229.
[8]Leal Thiago P,Gon alves Amanda C A,Vieira Vinícius Da F,et al.Decode—differential evolution algorithm for community detection[C].2013 IEEE International Conference on Systems,Man,and Cybernetics(SMC),2013,13-16:4635-4640.
[9]Das Swagatam,Suganthan Ponnuthurai Nagaratnam.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.
[10]Y J Park,M S Song.A genetic algorithm for clustering problems[C].Proceeding of the 3rd Annual Conference Genetic Algorithms,1989:2-9.
[11]Newman M.E.J.,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(22):1-15.
[12]Leon Danon,Jordi Duch,Albert Diaz-Guilera,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(9):P09008.
[13]Lancichinetti Andrea,Fortunato Santo,adicchi Filippo.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[14]David Lusseau,Karsten Schneider,Oliver J.Boisseau,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[15]Tim S Evans.Cliquegraphs and overlapping communities[J].Journal of Statistical Mechanics Theory&Experiment,2010(12):257-265.
[16]Duch Jordi,Arenas Alex.Community detection in complex networks using extremal optimization[J].Physical Review E,2005,72(2):027104.
[2]Clara Pizzuti.A multiobjective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutionary Computation,2012,16(3):418-430.
[3]Zhang Xiaohong,Zhang Bin,Zhang Changsheng,et al.A multiobjective hybrid genetic algorithm for detecting communities in complex networks[C].2016 12th International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery,2016:691-695.
[4]Mursel Tasgin,Haluk Bingol.Community detection in complex networks using genetic algorithm[EB/OL].https://arxiv.org/abs/1509.00556,2017-11-02.
[5]Clara Pizzuti.Boosting the detection of modular community structure with genetic algorithms and local search[C].The 27th Annual ACM Symposium on Applied Computing,2012:226-231.
[6]G.Jia,Z.Cai,M.Musolesi,et al.Community detection in social and biological networks using differential evolution[C].The6th International Conference on Learning and Intelligent Optimization,2012:71-85.
[7]Wang Guoshun,Zhang Xuan,Jia Guanbo,et al.Application of Algorithm used in Community Detection of Complex Network[J].International Journal of Future Generation Communication and Networking,2013,6(4):219-229.
[8]Leal Thiago P,Gon alves Amanda C A,Vieira Vinícius Da F,et al.Decode—differential evolution algorithm for community detection[C].2013 IEEE International Conference on Systems,Man,and Cybernetics(SMC),2013,13-16:4635-4640.
[9]Das Swagatam,Suganthan Ponnuthurai Nagaratnam.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.
[10]Y J Park,M S Song.A genetic algorithm for clustering problems[C].Proceeding of the 3rd Annual Conference Genetic Algorithms,1989:2-9.
[11]Newman M.E.J.,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(22):1-15.
[12]Leon Danon,Jordi Duch,Albert Diaz-Guilera,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(9):P09008.
[13]Lancichinetti Andrea,Fortunato Santo,adicchi Filippo.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[14]David Lusseau,Karsten Schneider,Oliver J.Boisseau,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[15]Tim S Evans.Cliquegraphs and overlapping communities[J].Journal of Statistical Mechanics Theory&Experiment,2010(12):257-265.
[16]Duch Jordi,Arenas Alex.Community detection in complex networks using extremal optimization[J].Physical Review E,2005,72(2):027104.