基于零模型的社区检测基准网络构造及应用
|
摘要
社区检测对于探索挖掘复杂网络的结构特性具有重要意义,社区检测算法性能对于检测结果具有重要影响。目前用于衡量社区检测算法性能的基准测试网络较为单一,主要包括人工合成网络和真实世界网络。由于真实世界网络中通常缺乏已知社区结构信息,人工合成网络成为衡量算法性能的主要途径,但普遍存在网络微观特性不可调且与真实世界网络差异较大、对检测算法区分度不高、无法更改局部网络结构等问题。为提升人工合成网络性能,该文提出基于零模型的基准测试网络构造方法,首先设计了能够保持中尺度特性的零模型,提升网络微观特性调整灵活度,使其更逼近真实世界网络结构特性;其次设计了能够调整社区结构强弱的零模型,提升网络社区检测的评价准确性;最后设计了能够调整局部拓扑结构的零模型,有效衡量局部社区结构特性变化对于整体网络结构及检测算法性能的重要性。实验结果表明,基于零模型的构造方法能够有效提升基准测试网络的多样性和灵活性,更加逼近真实世界网络特性,因此更能满足对于社区检测算法性能的评价需求,对于提升复杂网络社区检测性能具有重要意义。
Community detection is of great significance for exploring the structural characteristics of complex networks while the performance of community detection algorithm makes important influence on the detection results. At present, the benchmark networks that are used to measure the performance of community detection algorithm mainly include artificial synthetic network and real-world network. Synthetic network has become the main method to measure the performance of the algorithm since the real-world network usually lacks information of known community structure. However, it is found that the microscopic characteristics of the network is unadjusted, which is different from the real-world network, the discrimination of the detection algorithm is not high, and it is inability to change the local network structure. In order to improve the performance of artificial synthetic network, a benchmark network construction algorithm on null-model is proposed. Firstly, an algorithm of null model that can maintain the mesoscale characteristics is built to improve the flexibility of network micro-feature adjustment and make it closer to the real-world network structural characteristics. Secondly, the null model of adjusting strengthen and weakness for community structure is designed for improving the evaluation accuracy of network community testing. Finally, a method based on null model is constructed so as to make some adjustments of the local topological structure for measuring the importance of the change with local community structure characteristics to the whole network structure and the performance on detection algorithm. Experimental results show that the algorithm in view of null model can effectively improve the diversity and flexibility of the benchmark network, thus making the network be more similar with the features of real-world network and meeting the demand for performance improvement of community detection algorithm.
Community detection is of great significance for exploring the structural characteristics of complex networks while the performance of community detection algorithm makes important influence on the detection results. At present, the benchmark networks that are used to measure the performance of community detection algorithm mainly include artificial synthetic network and real-world network. Synthetic network has become the main method to measure the performance of the algorithm since the real-world network usually lacks information of known community structure. However, it is found that the microscopic characteristics of the network is unadjusted, which is different from the real-world network, the discrimination of the detection algorithm is not high, and it is inability to change the local network structure. In order to improve the performance of artificial synthetic network, a benchmark network construction algorithm on null-model is proposed. Firstly, an algorithm of null model that can maintain the mesoscale characteristics is built to improve the flexibility of network micro-feature adjustment and make it closer to the real-world network structural characteristics. Secondly, the null model of adjusting strengthen and weakness for community structure is designed for improving the evaluation accuracy of network community testing. Finally, a method based on null model is constructed so as to make some adjustments of the local topological structure for measuring the importance of the change with local community structure characteristics to the whole network structure and the performance on detection algorithm. Experimental results show that the algorithm in view of null model can effectively improve the diversity and flexibility of the benchmark network, thus making the network be more similar with the features of real-world network and meeting the demand for performance improvement of community detection algorithm.
引文
[1]肖婧,张永建,许小可.复杂网络模糊重叠社区检测研究进展[J].复杂系统与复杂性科学,2017,14(3):8-29.XIAO Jing,ZHANG Yong-jian,XU Xiao-ke.Research progress of fuzzy overlapping community detection in complex networks[J].Complex Systems&Complexity Science,2017,14(3):8-29.
[2]乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647.QIAO Shao-jie,HAN Nan,ZHANG Kai-feng,et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software,2017,28(3):631-647.
[3]YANG J,MCAULEY J,LESKOVEC J.Community detection in networks with node attributes[C]//IEEEInternational Conference on Data Mining.Piscataway:IEEE,2014:1151-1156.
[4]汪小帆,李翔,陈关荣.网络科学导论[M].北京:高等教育出版社,2012.WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Introduction to complex networks[M].Beijing:Higher Education Press,2012.
[5]何东晓,周栩,王佐,等.复杂网络社区挖掘-基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170.HE Dong-xiao,ZHUO Xu,WANG Zuo,et al.Community mining in complex networks-Clustering combination based genetic algorithm[J].Acta Automatica Sinica,2010,36(8):1160-1170.
[6]ZHANG X,CAO G.Transient community detection and its application to data forwarding in delay tolerant networks[J].IEEE/ACM Transactions on Networking,2017,99:1-15.
[7]GERGELY P,IMRE D,ILLéS F,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435:814-818.
[8]GIRVAN M,NEWMAN M E.Community structure in social and biological networks[J].PNAS,2002,99(12):7821-7826.
[9]LEE C,REID F,MCDAID A,et al.Detecting highly overlapping community structure by greedy clique expansion[R].Dublin:University College Dublin,2010.
[10]LANCICHINETTI A,FORTUNATO S,KERTéSZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2009,11(3):19-44.
[11]JIA G,CAI Z,MUSOLESI M,et al.Community detection in social and biological networks using differential evolution[C]//International Conference on Learning and Intelligent Optimization.Berlin:Springer,2012,7219:71-85.
[12]CLAUSET A,NEWMAN M E,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(2):066111.
[13]XIAO Jing,ZHANG Yong-jian,XU Xiao-ke.Convergence improvement of differential evolution for community detection in complex networks[J].Physica A,2018,503:762-779.
[14]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(2):036106.
[15]GNVALDSSON T.Pattern discrimination using feedforward networks:A benchmark study of scaling behavior[J].Neural Computation,1993,5(3):483-491.
[16]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4 Pt 2):046110.
[17]BICKEL P J,CHEN A.A nonparametric view of network models and Newman-Girvan and other modularities[J].PNAS,2009,106(50):21068-21073.
[18]LUSSEAU D,NEWMAN M.E.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society B:Biological Sciences,2004,271(Suppl 6):S477-S481.
[19]NEWMAN M.Modularity and community structure in networks[J].PNAS,2006,103(23):8577-8582.
[20]HE S,JIA G,ZHU Z,et al.Cooperative co-evolutionary module identification with application to cancer disease module discovery[J].IEEE Transactions on Evolutionary Computation,2016,20(6):874-891.
[21]SARZYNSKA M,LEICHT E A,CHOWELL G,et al.Null models for community detection in spatially embedded,temporal networks[J].Journal of Complex Networks,2018,4(3):363-406.
[22]XIE J,KELLEY S,SZYMANSKI B K.Overlapping community detection in networks:The state-of-the-art and comparative study[J].ACM Computing Surveys,2011,45(4):1-35.
[23]SUN Peng-gang,SUN Xi-ya.Complete graph model for community detection[J].Physica A:Statistical Mechanics and Its Applications,2017,471:88-97.
[24]DANON L,DíAZGUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics,2005(9):09008.
[25]YANG J,LESKOVEC J.Defining and evaluating network communities based on ground-truth[C]//IEEE International Conference on Data Mining.Piscataway:IEEE,2012,42(1):181-213.
[26]MAHADEVAN P,KRIOUKOV D,FALL K,et al.A basis for systematic analysis of network topologies[R].San Diego:University of California San Diego,2006.
[27]COLWELL R,WINKLER D.A null model for null models in biogeography[C]//Ecological Communities:Conceptual Issues and the Evidence Ecological Communities.Princeton:Princeton University Press,1984:344-359.
[28]尚可可.在线社交网络的零模型构造和行为预测研究[D].青岛:青岛理工大学,2013.SHANG Ke-ke,The study of null model construction and user behavior prediction for online social networks[D].Qingdao:Qingdao Technological University,2013.
[29]MAHADEVAN P,KRIOUKOV D,FALL K,et al.Systematic topology analysis and generation using degree correlations[C]//ACM SIGCOMM.New York:ACM,2006:135-146.
[30]尚可可,许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报,2014,43(1):7-20.SHANG Ke-ke,XU Xiao-ke.Construction and application for null models of complex networks based on randomized algorithms[J].Journal of University of Electronic Science and Technology of China,2014,43(1):7-20.
[31]WU J,ZHAO S,HE L,et al.Neural-Network-Based switching control for dc motors system with LFR[C]//International Symposium on Neural Networks.Berlin:Springer,2007:267-274.
[2]乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647.QIAO Shao-jie,HAN Nan,ZHANG Kai-feng,et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software,2017,28(3):631-647.
[3]YANG J,MCAULEY J,LESKOVEC J.Community detection in networks with node attributes[C]//IEEEInternational Conference on Data Mining.Piscataway:IEEE,2014:1151-1156.
[4]汪小帆,李翔,陈关荣.网络科学导论[M].北京:高等教育出版社,2012.WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Introduction to complex networks[M].Beijing:Higher Education Press,2012.
[5]何东晓,周栩,王佐,等.复杂网络社区挖掘-基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170.HE Dong-xiao,ZHUO Xu,WANG Zuo,et al.Community mining in complex networks-Clustering combination based genetic algorithm[J].Acta Automatica Sinica,2010,36(8):1160-1170.
[6]ZHANG X,CAO G.Transient community detection and its application to data forwarding in delay tolerant networks[J].IEEE/ACM Transactions on Networking,2017,99:1-15.
[7]GERGELY P,IMRE D,ILLéS F,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435:814-818.
[8]GIRVAN M,NEWMAN M E.Community structure in social and biological networks[J].PNAS,2002,99(12):7821-7826.
[9]LEE C,REID F,MCDAID A,et al.Detecting highly overlapping community structure by greedy clique expansion[R].Dublin:University College Dublin,2010.
[10]LANCICHINETTI A,FORTUNATO S,KERTéSZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2009,11(3):19-44.
[11]JIA G,CAI Z,MUSOLESI M,et al.Community detection in social and biological networks using differential evolution[C]//International Conference on Learning and Intelligent Optimization.Berlin:Springer,2012,7219:71-85.
[12]CLAUSET A,NEWMAN M E,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(2):066111.
[13]XIAO Jing,ZHANG Yong-jian,XU Xiao-ke.Convergence improvement of differential evolution for community detection in complex networks[J].Physica A,2018,503:762-779.
[14]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(2):036106.
[15]GNVALDSSON T.Pattern discrimination using feedforward networks:A benchmark study of scaling behavior[J].Neural Computation,1993,5(3):483-491.
[16]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4 Pt 2):046110.
[17]BICKEL P J,CHEN A.A nonparametric view of network models and Newman-Girvan and other modularities[J].PNAS,2009,106(50):21068-21073.
[18]LUSSEAU D,NEWMAN M.E.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society B:Biological Sciences,2004,271(Suppl 6):S477-S481.
[19]NEWMAN M.Modularity and community structure in networks[J].PNAS,2006,103(23):8577-8582.
[20]HE S,JIA G,ZHU Z,et al.Cooperative co-evolutionary module identification with application to cancer disease module discovery[J].IEEE Transactions on Evolutionary Computation,2016,20(6):874-891.
[21]SARZYNSKA M,LEICHT E A,CHOWELL G,et al.Null models for community detection in spatially embedded,temporal networks[J].Journal of Complex Networks,2018,4(3):363-406.
[22]XIE J,KELLEY S,SZYMANSKI B K.Overlapping community detection in networks:The state-of-the-art and comparative study[J].ACM Computing Surveys,2011,45(4):1-35.
[23]SUN Peng-gang,SUN Xi-ya.Complete graph model for community detection[J].Physica A:Statistical Mechanics and Its Applications,2017,471:88-97.
[24]DANON L,DíAZGUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics,2005(9):09008.
[25]YANG J,LESKOVEC J.Defining and evaluating network communities based on ground-truth[C]//IEEE International Conference on Data Mining.Piscataway:IEEE,2012,42(1):181-213.
[26]MAHADEVAN P,KRIOUKOV D,FALL K,et al.A basis for systematic analysis of network topologies[R].San Diego:University of California San Diego,2006.
[27]COLWELL R,WINKLER D.A null model for null models in biogeography[C]//Ecological Communities:Conceptual Issues and the Evidence Ecological Communities.Princeton:Princeton University Press,1984:344-359.
[28]尚可可.在线社交网络的零模型构造和行为预测研究[D].青岛:青岛理工大学,2013.SHANG Ke-ke,The study of null model construction and user behavior prediction for online social networks[D].Qingdao:Qingdao Technological University,2013.
[29]MAHADEVAN P,KRIOUKOV D,FALL K,et al.Systematic topology analysis and generation using degree correlations[C]//ACM SIGCOMM.New York:ACM,2006:135-146.
[30]尚可可,许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报,2014,43(1):7-20.SHANG Ke-ke,XU Xiao-ke.Construction and application for null models of complex networks based on randomized algorithms[J].Journal of University of Electronic Science and Technology of China,2014,43(1):7-20.
[31]WU J,ZHAO S,HE L,et al.Neural-Network-Based switching control for dc motors system with LFR[C]//International Symposium on Neural Networks.Berlin:Springer,2007:267-274.