2.25阶/2.5阶网络零模型模拟退火优化算法
|
摘要
2.25阶和2.5阶网络零模型在与原始网络具有相同的联合度分布的基础上分别具有相同的平均聚类系数和聚类谱。针对如何快速有效地生成2.25阶和2.5阶零模型,基于随机置乱生成零模型的方法,提出一种生成2.25阶、2.5阶零模型的优化算法-d K-目标保持重连算法。该算法改进了Hamiltonian函数,结合模拟退火算法和Metropolis准则,以2阶零模型为起始网络,通过优化迭代,生成2.25阶和2.5阶网络零模型。通过仿真实验,精确计算了真实网络及其对应的2.25阶和2.5阶零模型的聚类系数和聚类谱,从而验证了提出的算法生成零模型的有效性和准确性。同时,仿真实验分析了算法参数的设置对迭代次数的影响,将提出的算法与现有算法就复杂度进行了比较。分析结果表明,所提出的算法在生成2.25阶和2.5阶零模型时迭代次数明显少于其他算法,表明该算法有效降低了计算复杂度。
The 2.25 K and 2.5 K network null models have respectively the same average clustering coefficient and clustering spectrum as the original network with the same joint degree distribution.To quickly and effectively generate the 2.25 K and 2.5 K network null models,based on randomized scrambling method, an optimization algorithm of generating 2.25 K and 2.5 K null models,named dK-target keeping rewiring algorithm, is proposed.Improving the Hamiltonian function, combining with the simulated annealing process and Metropolis criterion,and setting 2 K null model as the original network, it generates 2.25 K and 2.5 K network null models.The clustering coefficient and clustering spectrum of the real networks and their corresponding 2.25 K and 2.5 K null models are calculated by simulation,which verifies the effectiveness and accuracy of generated 2.25 K and 2.5 K null models.Simultaneously, the impact of parameter settings of the proposed algorithm on the number of iterations is analyzed with simulation.After comparison of the proposed algorithm with the others on complexity,the simulation shows that the proposed algorithm is significantly less than the others on iteration numbers when generating 2.25 K and2.5 K null models,which means that it can effectively reduce the computational complexity.
The 2.25 K and 2.5 K network null models have respectively the same average clustering coefficient and clustering spectrum as the original network with the same joint degree distribution.To quickly and effectively generate the 2.25 K and 2.5 K network null models,based on randomized scrambling method, an optimization algorithm of generating 2.25 K and 2.5 K null models,named dK-target keeping rewiring algorithm, is proposed.Improving the Hamiltonian function, combining with the simulated annealing process and Metropolis criterion,and setting 2 K null model as the original network, it generates 2.25 K and 2.5 K network null models.The clustering coefficient and clustering spectrum of the real networks and their corresponding 2.25 K and 2.5 K null models are calculated by simulation,which verifies the effectiveness and accuracy of generated 2.25 K and 2.5 K null models.Simultaneously, the impact of parameter settings of the proposed algorithm on the number of iterations is analyzed with simulation.After comparison of the proposed algorithm with the others on complexity,the simulation shows that the proposed algorithm is significantly less than the others on iteration numbers when generating 2.25 K and2.5 K null models,which means that it can effectively reduce the computational complexity.
引文
[1]MAHADEVAN P,HUBBLE C,KRIOUKOV D,et al.Orbis:rescaling degree correlations to generate annotated internet topologies[J].ACM SIGCOMM Computer Communication Review,2007,37(4):325-336.
[2]NEWMAN M E.Properties of highly clustered networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2003,68(2):026121.
[3]GUILLAUME J L,LATAPY M.Bipartite graphs as models of complex networks[J].Physica A Statistical Mechanics&Its Applications,2006,371(2):795-813.
[4]SALA A,CAO L,WILSON C,et al.Measurement-calibrated graph models for social network experiments[C]//Proceedings of the 19th international conference on world wide web.[s.l.]:ACM,2010:861-870.
[5]ERDS P,RNYI A.On the evolution of random graphs[J].Publication of the Mathematical Institute of the Hungarian Academy Ofences,1960,38(1):17-61.
[6]WATTS D J,STROGATZ S H.Collective dynamics of“smallworld”networks[J].Nature,1998,393(6684):440-442.
[7]ALBERT-LSZLB.Scale-free networks:a decade and beyond[J].Science,2009,325(5939):412-413.
[8]MOLLOY M,REED B.A critical point for random graphs with a given degree sequence[J].Random Structures&Algorithms,1995,6(2-3):161-180.
[9]NEWMAN M E,STROGATZ S H,WATTS D J.Random graphs with arbitrary degree distributions and their applications[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2001,64:026118.
[10]SERGEI M,KIM S.Specificity and stability in topology of protein networks[J].Science,2002,296(5569):910-913.
[11]MASLOV S,SNEPPEN K,ZALIZNYAK A.Detection of topological patterns in complex networks:correlation profile of the internet[J].Physica A:Statistical Mechanics and Its Applications,2004,333:529-540.
[12]GJOKA M,KURANT M,MARKOPOULOU A.2.5K-Graphs:from sampling to generation[C]//Proceedings of IEEE INFOCOM.[s.l.]:IEEE,2012:1968-1976.
[13]PETERMANN T,RIOS P D L.The role of clustering and gridlike ordering in epidemic spreading[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,69(6):066166.
[14]SOFFER S N,VZQUEZ A.Network clustering coefficient without degree-correlation biases[J].Physical Review E,2005,71(2):057101.
[15]SERRANO M,BOGUM.Clustering in complex networks.I.General formalism[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2006,74(5):056114.
[16]NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters,2009,103:058701.
[17]GLEESON J P,MELNIK S,HACKETT A.How clustering affects the bond percolation threshold in complex networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2010,81:066114.
[18]BOLLOBS B.Random graphs[M].Cambridge:Cambridge University Press,2001.
[19]ANGELES S M,BOGUM.Tuning clustering in random networks with arbitrary degree distributions[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2005,72:036133.
[20]BANSAL S,KHANDELWAL S,MEYERS L A.Exploring biological network structure with clustered random networks[J].Bmc Bioinformatics,2009,10:405.
[21]MAHADEVAN P,KRIOUKOV D,FALL K,et al.Systematic topology analysis and generation using degree correlations[J].ACM SIGCOMM Computer Communication Review,2006,36(4):135-146.
[22]GJOKA M,TILLMAN B,MARKOPOULOU A.Construction of simple graphs with a target joint degree matrix and beyond[C]//IEEE conference on computer communications.[s.l.]:IEEE,2015.
[23]尚可可,许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报,2014,43(1):7-20.
[24]陈泉,杨建梅,曾进群.零模型及其在复杂网络研究中的应用[J].复杂系统与复杂性科学,2013,10(1):8-17.
[25]李欢,卢罡,郭俊霞.基于GPU的大尺度网络零模型分组生成并行算法[J].计算机工程与设计,2016,37(1):93-99.
[26]PARK J,NEWMAN M E J.Statistical mechanics of networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,70(2):066117.
[27]GOFFE W L,FERRIER G D,ROGERS J.Global optimization of statistical functions with simulated annealing[J].Journal of Econometrics,1994,60(1-2):65-99.
[2]NEWMAN M E.Properties of highly clustered networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2003,68(2):026121.
[3]GUILLAUME J L,LATAPY M.Bipartite graphs as models of complex networks[J].Physica A Statistical Mechanics&Its Applications,2006,371(2):795-813.
[4]SALA A,CAO L,WILSON C,et al.Measurement-calibrated graph models for social network experiments[C]//Proceedings of the 19th international conference on world wide web.[s.l.]:ACM,2010:861-870.
[5]ERDS P,RNYI A.On the evolution of random graphs[J].Publication of the Mathematical Institute of the Hungarian Academy Ofences,1960,38(1):17-61.
[6]WATTS D J,STROGATZ S H.Collective dynamics of“smallworld”networks[J].Nature,1998,393(6684):440-442.
[7]ALBERT-LSZLB.Scale-free networks:a decade and beyond[J].Science,2009,325(5939):412-413.
[8]MOLLOY M,REED B.A critical point for random graphs with a given degree sequence[J].Random Structures&Algorithms,1995,6(2-3):161-180.
[9]NEWMAN M E,STROGATZ S H,WATTS D J.Random graphs with arbitrary degree distributions and their applications[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2001,64:026118.
[10]SERGEI M,KIM S.Specificity and stability in topology of protein networks[J].Science,2002,296(5569):910-913.
[11]MASLOV S,SNEPPEN K,ZALIZNYAK A.Detection of topological patterns in complex networks:correlation profile of the internet[J].Physica A:Statistical Mechanics and Its Applications,2004,333:529-540.
[12]GJOKA M,KURANT M,MARKOPOULOU A.2.5K-Graphs:from sampling to generation[C]//Proceedings of IEEE INFOCOM.[s.l.]:IEEE,2012:1968-1976.
[13]PETERMANN T,RIOS P D L.The role of clustering and gridlike ordering in epidemic spreading[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,69(6):066166.
[14]SOFFER S N,VZQUEZ A.Network clustering coefficient without degree-correlation biases[J].Physical Review E,2005,71(2):057101.
[15]SERRANO M,BOGUM.Clustering in complex networks.I.General formalism[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2006,74(5):056114.
[16]NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters,2009,103:058701.
[17]GLEESON J P,MELNIK S,HACKETT A.How clustering affects the bond percolation threshold in complex networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2010,81:066114.
[18]BOLLOBS B.Random graphs[M].Cambridge:Cambridge University Press,2001.
[19]ANGELES S M,BOGUM.Tuning clustering in random networks with arbitrary degree distributions[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2005,72:036133.
[20]BANSAL S,KHANDELWAL S,MEYERS L A.Exploring biological network structure with clustered random networks[J].Bmc Bioinformatics,2009,10:405.
[21]MAHADEVAN P,KRIOUKOV D,FALL K,et al.Systematic topology analysis and generation using degree correlations[J].ACM SIGCOMM Computer Communication Review,2006,36(4):135-146.
[22]GJOKA M,TILLMAN B,MARKOPOULOU A.Construction of simple graphs with a target joint degree matrix and beyond[C]//IEEE conference on computer communications.[s.l.]:IEEE,2015.
[23]尚可可,许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报,2014,43(1):7-20.
[24]陈泉,杨建梅,曾进群.零模型及其在复杂网络研究中的应用[J].复杂系统与复杂性科学,2013,10(1):8-17.
[25]李欢,卢罡,郭俊霞.基于GPU的大尺度网络零模型分组生成并行算法[J].计算机工程与设计,2016,37(1):93-99.
[26]PARK J,NEWMAN M E J.Statistical mechanics of networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,70(2):066117.
[27]GOFFE W L,FERRIER G D,ROGERS J.Global optimization of statistical functions with simulated annealing[J].Journal of Econometrics,1994,60(1-2):65-99.