结合基因遗传和贪婪搜索的布谷鸟社区检测算法
|
摘要
为了提高复杂网络社区结构挖掘的精度,结合基因遗传和贪婪搜索提出一种面向模块度优化的布谷鸟社区检测算法(GGCSCA)。布谷鸟种群在有序邻居表上逐维随机游走,并采用优质基因遗传策略,使得种群高效优化,同时应用局部模块度增量最大化的贪婪偏好搜索算法快速提升种群质量,以取得好的社区划分结果。GGCSCA在基准网络和经典网络上进行了实验,并与一些典型算法进行对比,结果说明了本社区发现算法的有效性、准确性和快速收敛性,具有较强的社区识别能力,能够精细地检测出网络社区结构。
In order to improve the accuracy of community detection for complex networks,this paper proposed an algorithm based on cuckoo search algorithm combining gene inheritance and greedy search(GGCSCA) to optimize modularity for community detection. Cuckoos walked randomly on ordered adjacent table and employed gene inheritance strategy,which aimed to optimize population efficiently. The algorithm improved population quality quickly by greedy preference search of local modularity increment maximum for the purpose of getting good result of community partition. GGCSCA had been tested on both benchmark networks and some typical complex networks,and compared with some typical community detection algorithms. Experimental results show the effectiveness,accuracy and fast convergence of this algorithm for discovering community structure.It has strong capability of community identification and can detect the structure of community finely.
In order to improve the accuracy of community detection for complex networks,this paper proposed an algorithm based on cuckoo search algorithm combining gene inheritance and greedy search(GGCSCA) to optimize modularity for community detection. Cuckoos walked randomly on ordered adjacent table and employed gene inheritance strategy,which aimed to optimize population efficiently. The algorithm improved population quality quickly by greedy preference search of local modularity increment maximum for the purpose of getting good result of community partition. GGCSCA had been tested on both benchmark networks and some typical complex networks,and compared with some typical community detection algorithms. Experimental results show the effectiveness,accuracy and fast convergence of this algorithm for discovering community structure.It has strong capability of community identification and can detect the structure of community finely.
引文
[1] Girvan M,Newman M E J. Community structure in social and biological networks[J]. Proceedings of National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[2] Fortunato S. Community detection in graphs[J]. Physics Reports,2010,486(3-5):75-174.
[3]杨博,刘大有,Liu Jiming,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66.(Yang Bo,Liu Dayou,Liu Jiming,et al.Complex network clustering algorithms[J]. Journal of Software,2009,20(1):54-66.)
[4] White S,Smyth P. A spectral clustering approach to finding communities in graphs[C]//Proc of the SIAM International Conference on Data Mining. Philadelphia,PA:SIAM,2005:76-84.
[5] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,69(6):066133.
[6] Clauset A,Newman M E J,Moore C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,70(2):066111.
[7] Pons P,Latapy M. Computing communities in large networks using random walks[J]. Journal of Graph Algorithms and Applications,2006,10(2):191-218.
[8] 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.
[9] Guimera R,Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature,2005,433(7028):895-900.
[10]Blondel V D,Guillaume J L,Lambiotte R,et al. Fast unfolding of community in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment,2008(10):155-168.
[11]Duch J,Arenas A. Community detection in complex networks using extremal optimization[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2005,72(2):027104.
[12]黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法[J].软件学报,2013,24(9):2062-2077.(Huang Faliang,Zhang Shichao,Zhu Xiaofeng. Discovering network community based on multi-objective optimization[J]. Journal of Software,2013,24(9):2062-2077.)
[13]Zhou Xu,Liu Yanheng,Li Bin. A multi-objective discrete cuckoo search algorithm with local search for community detection in complex networks[J]. Modern Physics Letters B,2016,30(7):1-20.
[14]黄发良,肖南峰.网络社区发现的粒子群优化算法[J].控制理论与应用,2011,28(9):1135-1140.(Huang Faliang,Xiao Nanfeng. Particle-swarm-optimization algorithm to discover network community[J]. Control Theory&Applications,2011,28(9):1135-1140.)
[15]邱晓辉,陈羽中.一种面向社会网络社区发现的改进粒子群优化算法[J].小型微型计算机系统,2014,35(6):1422-1425.(Qiu Xiaohui,Chen Yuzhong. An improved particle-swarm-optimization algorithm for community discovery in social networks[J]. Journal of Chinese Computer Systems,2014,35(6):1422-1425.)
[16]Tasgin M,Herdagdelen A,Bingol H. Community detection in complex networks using genetic algorithms[EB/OL].(2007)[2017-05-20]. https://arxiv. org/pdf/0711. 0491. pdf.
[17]邓琨,张健沛,杨静.利用改进遗传算法进行复杂网络社团发现[J].哈尔滨工程大学学报,2013,34(11):1438-1444.(Deng Kun,Zhang Jianpei,Yang Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University,2013,34(11):1438-1444.)
[18]金弟,刘杰,杨博,等.局部搜索与遗传算法结合的大规模复杂网络社区探测[J].自动化学报,2011,37(7):873-879.(Jin Di,Liu Jie,Yang Bo,et al. Genetic algorithm with local search for community detection in large-scale complex networks[J]. Acta Automatica Sinica,2011,37(7):873-879.)
[19]Gach O,Hao Jinkao. A memetic algorithm for community detection in complex networks[C]//Proc of International Conference on Parallel Problem Solving From Nature. Berlin:Springer-Verlag,2012:327-336.
[20]金弟,杨博,刘杰,等.复杂网络簇结构探测——基于随机游走的蚁群算法[J].软件学报,2012,23(3):451-464.(Jin Di,Yang Bo,Liu Jie,et al. Ant colony optimization based on random walk for community detection in complex networks[J]. Journal of Software,2012,23(3):451-464.)
[21] Chopade P,Zhan J. A framework for community detection in large networks using game-theoretic modeling[J]. IEEE Trans on Big Data,2017,3(3):276-287.
[22]段震,闵星,王倩倩,等.基于商空间的多层粒化社区发现方法[J].南京大学学报:自然科学版,2017,53(4):764-774.(Duan Zhen,Min Xin,Wang Qianqian,et al. Multilayer granulation community detection method based on quotient space[J]. Journal of Nanjing University:Natural Science,2017,53(4):764-774.)
[23]金志刚,徐珮轩.密度峰值聚类的自适应社区发现算法[J].哈尔滨工业大学学报,2018,50(5):44-51.(Jin Zhigang,Xu Peixuan. An adaptive community detection algorithm of density peak clustering[J]. Journal of Harbin Institute of Technology,2018,50(5):44-51.
[24] Yang Xinshe. Nature inspired meta heuristic algorithms[M]. 2nd ed. Cambridge:Luniver Press,2010:82-89.
[25]Fortunato S,Barthelemy M. Resolution limit in community detection[J]. Proceedings of National Academy of Sciences of the United States of America,2007,104(1):36-41.
[26]Lancichinetti A,Fortunato S,Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2008,78(4):046110.
[27] Danon L,Diaz-Guilera A,Duch J,et al. Comparing community structure identication[J]. Journal of Statistical Mechanics:Theory and Experiment,2005,78(9):09008.
[28]何东晓,周栩,王佐,等.复杂网络社区挖掘:基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170.(He Dongxiao,Zhou Xu,Wang Zuo,et al. Community mining in complex networks:clustering combination based genetic algorithm[J]. Acta Automatica Sinica,2010,36(8):1160-1170.)
[2] Fortunato S. Community detection in graphs[J]. Physics Reports,2010,486(3-5):75-174.
[3]杨博,刘大有,Liu Jiming,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66.(Yang Bo,Liu Dayou,Liu Jiming,et al.Complex network clustering algorithms[J]. Journal of Software,2009,20(1):54-66.)
[4] White S,Smyth P. A spectral clustering approach to finding communities in graphs[C]//Proc of the SIAM International Conference on Data Mining. Philadelphia,PA:SIAM,2005:76-84.
[5] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,69(6):066133.
[6] Clauset A,Newman M E J,Moore C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,70(2):066111.
[7] Pons P,Latapy M. Computing communities in large networks using random walks[J]. Journal of Graph Algorithms and Applications,2006,10(2):191-218.
[8] 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.
[9] Guimera R,Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature,2005,433(7028):895-900.
[10]Blondel V D,Guillaume J L,Lambiotte R,et al. Fast unfolding of community in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment,2008(10):155-168.
[11]Duch J,Arenas A. Community detection in complex networks using extremal optimization[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2005,72(2):027104.
[12]黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法[J].软件学报,2013,24(9):2062-2077.(Huang Faliang,Zhang Shichao,Zhu Xiaofeng. Discovering network community based on multi-objective optimization[J]. Journal of Software,2013,24(9):2062-2077.)
[13]Zhou Xu,Liu Yanheng,Li Bin. A multi-objective discrete cuckoo search algorithm with local search for community detection in complex networks[J]. Modern Physics Letters B,2016,30(7):1-20.
[14]黄发良,肖南峰.网络社区发现的粒子群优化算法[J].控制理论与应用,2011,28(9):1135-1140.(Huang Faliang,Xiao Nanfeng. Particle-swarm-optimization algorithm to discover network community[J]. Control Theory&Applications,2011,28(9):1135-1140.)
[15]邱晓辉,陈羽中.一种面向社会网络社区发现的改进粒子群优化算法[J].小型微型计算机系统,2014,35(6):1422-1425.(Qiu Xiaohui,Chen Yuzhong. An improved particle-swarm-optimization algorithm for community discovery in social networks[J]. Journal of Chinese Computer Systems,2014,35(6):1422-1425.)
[16]Tasgin M,Herdagdelen A,Bingol H. Community detection in complex networks using genetic algorithms[EB/OL].(2007)[2017-05-20]. https://arxiv. org/pdf/0711. 0491. pdf.
[17]邓琨,张健沛,杨静.利用改进遗传算法进行复杂网络社团发现[J].哈尔滨工程大学学报,2013,34(11):1438-1444.(Deng Kun,Zhang Jianpei,Yang Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University,2013,34(11):1438-1444.)
[18]金弟,刘杰,杨博,等.局部搜索与遗传算法结合的大规模复杂网络社区探测[J].自动化学报,2011,37(7):873-879.(Jin Di,Liu Jie,Yang Bo,et al. Genetic algorithm with local search for community detection in large-scale complex networks[J]. Acta Automatica Sinica,2011,37(7):873-879.)
[19]Gach O,Hao Jinkao. A memetic algorithm for community detection in complex networks[C]//Proc of International Conference on Parallel Problem Solving From Nature. Berlin:Springer-Verlag,2012:327-336.
[20]金弟,杨博,刘杰,等.复杂网络簇结构探测——基于随机游走的蚁群算法[J].软件学报,2012,23(3):451-464.(Jin Di,Yang Bo,Liu Jie,et al. Ant colony optimization based on random walk for community detection in complex networks[J]. Journal of Software,2012,23(3):451-464.)
[21] Chopade P,Zhan J. A framework for community detection in large networks using game-theoretic modeling[J]. IEEE Trans on Big Data,2017,3(3):276-287.
[22]段震,闵星,王倩倩,等.基于商空间的多层粒化社区发现方法[J].南京大学学报:自然科学版,2017,53(4):764-774.(Duan Zhen,Min Xin,Wang Qianqian,et al. Multilayer granulation community detection method based on quotient space[J]. Journal of Nanjing University:Natural Science,2017,53(4):764-774.)
[23]金志刚,徐珮轩.密度峰值聚类的自适应社区发现算法[J].哈尔滨工业大学学报,2018,50(5):44-51.(Jin Zhigang,Xu Peixuan. An adaptive community detection algorithm of density peak clustering[J]. Journal of Harbin Institute of Technology,2018,50(5):44-51.
[24] Yang Xinshe. Nature inspired meta heuristic algorithms[M]. 2nd ed. Cambridge:Luniver Press,2010:82-89.
[25]Fortunato S,Barthelemy M. Resolution limit in community detection[J]. Proceedings of National Academy of Sciences of the United States of America,2007,104(1):36-41.
[26]Lancichinetti A,Fortunato S,Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear&Soft Matter Physics,2008,78(4):046110.
[27] Danon L,Diaz-Guilera A,Duch J,et al. Comparing community structure identication[J]. Journal of Statistical Mechanics:Theory and Experiment,2005,78(9):09008.
[28]何东晓,周栩,王佐,等.复杂网络社区挖掘:基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170.(He Dongxiao,Zhou Xu,Wang Zuo,et al. Community mining in complex networks:clustering combination based genetic algorithm[J]. Acta Automatica Sinica,2010,36(8):1160-1170.)