局部扩展的遗传优化重叠社区发现方法
|
摘要
提出了一种局部扩展的遗传优化重叠社区发现(LEGAOCD)方法。借鉴局部扩展的重叠社区发现方法的思想,首先将少数的核心节点构成模体;同时,利用三角形模体来判断社区的稳定性度量问题,从而量化社区结构稳定性;然后通过改进的遗传优化算法策略分配它们应归属的社区;最后通过两个评价目标函数得到高质量的重叠社区结构。该算法在数据集上与经典的CPM、COPRA作比较,实验结果表明,LEGAOCD方法在检测重叠社区结构和重叠节点方面具有较优的性能。
This paper proposed a local extended genetic algorithm for optimizing overlapping community detection( LEGAOCD). Referring to the main idea of local extended overlapping community detection,it made a few core nodes be constructed as die body. At the same time,this paper used the triangular model to judge the stability measure of the community,so as to quantify the stability of community structure. Then,it used the improved strategy of genetic algorithm to allocate the communities where they belonged. Finally,it obtained the high-quality overlapping community structure by two discriminant objective functions. After that,it compared the LEGAOCD with classical CPM and COPRA on the data sets. The results show that LEGAOCD possesses excellent comparatively in the aspects of detecting overlapping community structure and overlapping nodes.
This paper proposed a local extended genetic algorithm for optimizing overlapping community detection( LEGAOCD). Referring to the main idea of local extended overlapping community detection,it made a few core nodes be constructed as die body. At the same time,this paper used the triangular model to judge the stability measure of the community,so as to quantify the stability of community structure. Then,it used the improved strategy of genetic algorithm to allocate the communities where they belonged. Finally,it obtained the high-quality overlapping community structure by two discriminant objective functions. After that,it compared the LEGAOCD with classical CPM and COPRA on the data sets. The results show that LEGAOCD possesses excellent comparatively in the aspects of detecting overlapping community structure and overlapping nodes.
引文
[1]周旭.复杂网络中社区发现算法研究[D].长春:吉林大学,2016.(Zhou Xu.Research on community detection algorithms in complex networks[D].Changchun:Jilin University,2016.)
[2]Mahmoud H,Masulli F,Rovetta S,et al.Community detection in protein-protein interaction networks using spectral and graph approaches[C]//Proc of International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics.Cham:Springer,2013:62-75.
[3]Palla G,Derényi I,Farkas I.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[4]Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2009,12(10):2011-2024.
[5]Xie Jierui,Szymanski B K,Liu Xiaoming.SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proc of the 11th IEEE International Conference on Data Mining Workshops.Washington DC:IEEE Computer Society,2011:344-349.
[6]乔少杰,郭俊,韩楠,等.大规模复杂网络社区并行发现算法[J].计算机学报,2017,40(3):687-700.(Qiao Shaojie,Guo Jun,Han Nan,et al.Parallel algorithm for discovering communities in largescale complex networks[J].Chinese Journal of Computers,2017,40(3):687-700.)
[7]Prat-Pérez A,Dominguez-Sal D,Brunat J M.Shaping communities out of triangles[EB/OL].(2012-07-26).https://arxiv.org/abs/1207.6269.
[8]张海燕,梁循,周小平.针对有向图的局部扩展的重叠社区发现算法[J].数据采集与处理,2015,30(3):683-693.(Zhang Haiyan,Liang Xun,Zhou Xiaoping.Overlapping community detection from local extension in directed graphs[J].Journal of Data Acquisition and Processing,2015,30(3):683-693.)
[9]Atay Y,Kodaz H.A new adaptive genetic algorithm for community structure detection[M]//Intelligent and Evolutionary Systems.Cham:Springer,2016:43-55.
[10]王琦,温志平.一种基于多维遗传算法的重叠社区发现方法[J].计算机应用研究,2016,33(12):3543-3546,3553.(Wang Qi,Wen Zhiping.Multimensional genetic algorithm for overlapping community detection[J].Application Research of Computers,2016,33(12):3543-3546,3553.)
[11]牛新征,司伟钰,佘堃.基于进化聚类的动态网络社团发现[J].软件学报,2017,28(7):1773-1789.(Niu Xinzheng,Si Weiyu,She Kun.Evolutionary community detection in dynamic networks[J].Journal of Software,2017,28(7):1773-1789.)
[12]Shen Bo,Wang Ningwei,Qiu Huihuai.A new genetic algorithm for overlapping community detection[C]//Proc of the 10th International Conference on Intelligent Information Hiding and Multimedia Signal Processing.Washington DC:IEEE Computer Society,2014:766-769.
[13]韩忠明,谭旭升,陈炎,等.NCSS:一种快速有效的复杂网络社团划分算法[J].中国科学:信息科学,2016,46(4):431-444.(Han Zhongming,Tan Xusheng,Chen Yan,et al.NCSS:an effective and efficient complex network community detection algorithm[J].Scientia Sinica Informationis,2016,46(4):431-444.)
[14]Li Zhangtao,Liu Jing.A multi-agent genetic algorithm for community detection in complex networks[J].Physica A:Statistical Mechanics&Its Applications,2016,449(5):336-347.
[15]Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E:Statistical Nonlinear&Soft Matter Physics,2008,78(2):046110.
[16]Xie Jierui,Kelley S,Szymanski,B.Overlapping community detection in networks:the state of the art and comparative study[J].ACMComputing Surveys,2013,45(4):article No.43.
[17]乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647.(Qiao Shaojie,Han Nan,Zhang Kaifeng,et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software,2017,28(3):631-647.)
[18]Zhou Xu,Liu Yanheng,Zhang Jindong,et al.An ant colony based algorithm for overlapping community detection in complex networks[J].Physica A:Statistical Mechanics&Its Applications,2015,427(6):289-301.
[2]Mahmoud H,Masulli F,Rovetta S,et al.Community detection in protein-protein interaction networks using spectral and graph approaches[C]//Proc of International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics.Cham:Springer,2013:62-75.
[3]Palla G,Derényi I,Farkas I.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[4]Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2009,12(10):2011-2024.
[5]Xie Jierui,Szymanski B K,Liu Xiaoming.SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proc of the 11th IEEE International Conference on Data Mining Workshops.Washington DC:IEEE Computer Society,2011:344-349.
[6]乔少杰,郭俊,韩楠,等.大规模复杂网络社区并行发现算法[J].计算机学报,2017,40(3):687-700.(Qiao Shaojie,Guo Jun,Han Nan,et al.Parallel algorithm for discovering communities in largescale complex networks[J].Chinese Journal of Computers,2017,40(3):687-700.)
[7]Prat-Pérez A,Dominguez-Sal D,Brunat J M.Shaping communities out of triangles[EB/OL].(2012-07-26).https://arxiv.org/abs/1207.6269.
[8]张海燕,梁循,周小平.针对有向图的局部扩展的重叠社区发现算法[J].数据采集与处理,2015,30(3):683-693.(Zhang Haiyan,Liang Xun,Zhou Xiaoping.Overlapping community detection from local extension in directed graphs[J].Journal of Data Acquisition and Processing,2015,30(3):683-693.)
[9]Atay Y,Kodaz H.A new adaptive genetic algorithm for community structure detection[M]//Intelligent and Evolutionary Systems.Cham:Springer,2016:43-55.
[10]王琦,温志平.一种基于多维遗传算法的重叠社区发现方法[J].计算机应用研究,2016,33(12):3543-3546,3553.(Wang Qi,Wen Zhiping.Multimensional genetic algorithm for overlapping community detection[J].Application Research of Computers,2016,33(12):3543-3546,3553.)
[11]牛新征,司伟钰,佘堃.基于进化聚类的动态网络社团发现[J].软件学报,2017,28(7):1773-1789.(Niu Xinzheng,Si Weiyu,She Kun.Evolutionary community detection in dynamic networks[J].Journal of Software,2017,28(7):1773-1789.)
[12]Shen Bo,Wang Ningwei,Qiu Huihuai.A new genetic algorithm for overlapping community detection[C]//Proc of the 10th International Conference on Intelligent Information Hiding and Multimedia Signal Processing.Washington DC:IEEE Computer Society,2014:766-769.
[13]韩忠明,谭旭升,陈炎,等.NCSS:一种快速有效的复杂网络社团划分算法[J].中国科学:信息科学,2016,46(4):431-444.(Han Zhongming,Tan Xusheng,Chen Yan,et al.NCSS:an effective and efficient complex network community detection algorithm[J].Scientia Sinica Informationis,2016,46(4):431-444.)
[14]Li Zhangtao,Liu Jing.A multi-agent genetic algorithm for community detection in complex networks[J].Physica A:Statistical Mechanics&Its Applications,2016,449(5):336-347.
[15]Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E:Statistical Nonlinear&Soft Matter Physics,2008,78(2):046110.
[16]Xie Jierui,Kelley S,Szymanski,B.Overlapping community detection in networks:the state of the art and comparative study[J].ACMComputing Surveys,2013,45(4):article No.43.
[17]乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647.(Qiao Shaojie,Han Nan,Zhang Kaifeng,et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software,2017,28(3):631-647.)
[18]Zhou Xu,Liu Yanheng,Zhang Jindong,et al.An ant colony based algorithm for overlapping community detection in complex networks[J].Physica A:Statistical Mechanics&Its Applications,2015,427(6):289-301.