基于复杂网络空间的网络演化模型#刘刚，李永树**（西南交通大学地球科学与环境工程学院，成都610031）510152025303540摘要：为进一步研究复杂网络演化的过程，引入复杂网络空间的概念，诠释了网络结构在复杂网络空间中演化的基本原理，进而提出一种基于复杂网络空间的网络演化模型，给出了具体的网络构造算法。数值模拟显示，该网络演化模型具有较为稳定的度分布函数，其网络规模随时间呈指数增长趋势，且网络的平均路径长度正比于网络规模对数值。研究表明，本文给出的网络演化模型具有无标度、小世界特性。关键词：复杂网络；度分布；网络模型；无标度；小世界中图分类号：U491NetworkEvolutionModelbasedonComplexNetworkSpaceLIUGang,LIYongshu(FacultyofGeosciencesandEnvironmentalEngineering,SouthwestJiaotongUniversity,ChengDu610031)Abstract:Tofurtherstudytheevolutionofcomplexnetwork,weintroducetheconceptofcomplexnetworkspace,explainedtheprincipleoftheevolutionofnetworkstructureincomplexnetworkspace.Anetworkevolutionmodelbasedoncomplexnetworkspaceisproposedandcorrespondingspecificnetworkconstructionalgorithmispresented.Numericalsimulationshowsthatthenetworkevolutionmodelhasarelativelystabledegreedistributionfunction,thenetworksizeexponentiallywithtimetrend,theaveragepathlengthisproportionaltologarithmofnetworksize.Studiesshowthatthenetworkevolutionmodeliswiththescale-freeandsmall-worldfeatures.Keywords:complexnetwork;degreedistribution;networkmodel;scale-free;small-world0引言近年来，利用复杂网络理论研究现实世界中各种复杂系统的基本结构及动力学特性已经成为众多领域研究的新热点，吸引了来自物理学、数学、计算机科学、生物学等不同领域科学工作者的关注[1-6]。在复杂网络的研究过程中，建立合适的网络生长模型是关键，以小世界网络模型(WS模型)[7]和无标度网络模型(BA模型)[8]为代表。WS模型构造的网络结构具有较短的平均距离长度和较大的簇系数，形象地表达了网络的小世界特性；BA模型构造的网络其节点度服从幂律分布，揭示了网络的无标度特性。大量实证研究表明，真实网络几乎都同时具有小世界效应和无标度特性[9-11]。但是，由于这两种模型的生长过程忽略了影响实际网络生长的一些因素，导致在某些统计特性上与实际网络相比存在较大偏差，例如，BA模型的簇系数太小，而WS模型的度分布与实际网络不一致，且不生长。在BA模型和WS模型提出之后，学者们又提出了许多网络演化模型，但大多数模型在生长过程中，每一时间步都是加入一个新节点，即网络规模随时间成线性增长，这与实际网络的增长模式存在差异，例如，文献[12]统计得出Internet的节点数随时间的变化及美国人口的增长都可用指数函数进行拟合。针对上述模型在模拟实际网络增长过程中的不足，Dorogovtsev和Mendes提出了加速增长的网络生长模型[13]，使得每个新节点与老节点的连基金项目：高等学校博士学科点专项科研基金(20100184110019)作者简介：刘刚，（1986-），男，博士生，主要从事复杂网络理论、GIS理论及其应用方面的研究。通信联系人：李永树，（1957-），男，教授，博士生导师，主要从事复杂网络理论、GIS理论及其应用方面的研究。yshli@home.swjtu.edu.cn-1-边数持续增加，但其生长过程仍然是每一时间步加入一个新节点；李季和汪秉宏等[14]提出了节点数加速增长的网络生长模型，在该模型中每一时步加入rn(t)个新节点，其中n(t)为t时刻网络的节点数，r为增长率，且每一个新节点与m个老节点相连。该模型构造了一4550556065个网络规模成几何级数增长的无标度网络，但是该模型中边的增长与节点的增长几乎相同，没有考虑新节点与老节点之间关系的变化，而实际网络的生长过程中，新节点与老节点之间的关系存在不确定性，例如，疾病传染给网络中，每一个感染体在同一时刻可能传染给不同数量的新个体；社会网络中，每一个新个体的加入可能与网络中不同数量的老个体发生关系。为此，本文主要考虑如下两个问题：(1)网络演化过程中网络规模...