iData_节点数固定的复杂网络模型初探_覃森

第2卷第2期??

2005年4月??复杂系统与复杂性科学??COMPLEXSYSTEMSANDCOMPLEXITYSCIENCEVo.l2No.2Apr.2005文章编号:1672-3813(

2005)02-0007-06

节点数固定的复杂网络模型初探

覃??森,戴冠中,王??林

(西北工业大学自动化学院,西安710072)

摘要:由于随机图模型、小世界模型和无标度模型的结构上存在交叉性,有必要对复杂网络进行

新的分类。本文将复杂网络分成两类:节点数固定的复杂网络和节点数变化的复杂网络,且重

点研究了前一类网络。首先对节点数固定的网络进行了细分,然后分析了在边的不同连接方式

下节点数固定的网络的度分布、平均最短路长度和聚类系数等特征,最后讨论了小世界特性与

无标度特性产生的原因。研究表明,节点数固定的网络大多具有小世界特性,小世界特性与无

标度特性是从不同的侧面来研究复杂网络的,从而很好地解释了在许多复杂网络这两种特性能

够共存的原因。

关键词:复杂网络;小世界网络,无标度网络;节点数固定

中图分类号:N94;TP11文献标识码:A

DiscussionaboutComplexNetworkswithInvariableVertexNumbers

QINSen,DAIGuan??zhong,WANGLin

(CollegeofAutomation,NorthwesternPolytechnicalUniversity,Xi??an710072,China)

Abstract:Thediscoveriesofmanynaturalandartificialcomplexnetworks,liketheInternet,WorldWideWebandtheci??tationnetworks,havearousedphysicalcommunities??greatinterest.Itisnecessarytoclassifyrationallythecomplexnet??worksbecauseoftheintercrossonthestructureamongtherandomgraphmodels,small??worldnetworkandscale??freenet??workmodels.Inthispaper,wesortthecomplexnetworksintotwodifferentkinds.Oneisthecomplexnetworkswithinvari??ablevertexnumbers,http://wendang.chazidian.comccordingtothreedifferentmodesofconnectiveedge,degreedistributions,averageshortestpathlengthsandclusteringcoefficientsofthefirstkindarecompared.Ithasbeenindicatedthatmostnetworkswithinvariablevertexnum??bershavesmall??worldcharacteristics,andsmall??worldpropertyandscale??freepropertydepictdifferentprofilesofevolvingnetworks.Itdoescommendablyexplainwhysmall??worldandscale??freephenomenacoexistinmanyrealcomplexnetworks.

Keywords:complexnetwork;small??worldmode;lscale??freemode;linvariablevertexnumbers

1??引言

复杂网络模型很好地描述了自然界与社会中的众多网络模型,如互联网、WWW、科学研究合作网、演员合作网、电站供电网、科技论文引文网、生物新陈代谢网、食物网等[1-14]。但是人们对这些网络知之甚少,如网络的构成特点与层次组织形式、全局与局部拓扑性质、进化规律、网络形成的内在机理等方面。现实社会中各种复杂网络所反映的社会现象,如美国的大面积停电的原因、SARS等生物病毒的内在传播机制、计算

[15-23]机蠕虫病毒的传播控制、科学研究团体的形成等,都为复杂网络的研究提出了新的要求。收稿日期:2005-02-14

作者简介:覃森(1978-),男,湖北枝江人,博士生,主要研究方面为复杂网络中的控制问题。

??????8??????????????????????????????????????复杂系统与复杂性科学

[1,8,15,16]2005年4月研究者大多用随机图理论、统计物理方法和微分动力系统理论等来研究复杂网络

[1,2]。有关复杂网络模型的研究主要集中在3种重要的复杂网络模型??????随机图模型(ER模型)、小世界网络模型(WS模

[8-10,16,18-20][5,17,22,23]型)和无标度网络模型(BA模型)上。ER模型是最经典的复杂网络模型之一,该模型包含有N个节点,每个节点之间连接边的概率为p。??小世界现象??是指当网络的规模增加n时,其节点之间的最短路长度成lnn比例增加。而WS模型不仅考虑节点之间的平均最短路长度,还考虑了网络的聚类系数,它是具有小的平均最短路长度和较高的聚类系数的网络。Barab??si和Albert最早观察到一些复杂网络模型的度分布服从幂律(power??law)分布[5],并分析了产生幂律分布的两个原因:网络增长性(growth)和择优连接

[24]性(preferentialattachment)。但是,BA模型中的线性择优连接假设并不符合所有的现实网络。许多学者

还对复杂网络中一些现实社会具体模型的精确解、渗流理论、和信息传播(如计算机病毒、流行病传播和流

[1,9,10]言传播等)进行了广泛的研究。

如果把复杂网络分成ER、WS和BA模型等3类模型,并不具有全面性和准确性,因此有必要对复杂网络进行新的分类。由于复杂网络拓扑结构演化的起因只可能是节点数变化或边的变化,所以可将复杂网络按节点数或者边数的变化来进行分类。在本文中,根据节点数的变化情况,将复杂网络分成两大类:一类是节点数固定的复杂网络;另一类是节点数变化的复杂网络。然后根据连接边的变化情况,将网络进行细分。

本文对节点数固定的复杂网络进行了初步探讨,把该类模型分成三类进行研究,讨论了相应的聚类系数、平均最短路长度和度分布。数值模拟结果显示本文考虑的节点数固定的复杂网络的度分布均不服从幂律分布。这表明本文分类的合理性,同时也说明复杂网络呈现小世界现象与节点数增加没有必然联系。[1,2,11]2??节点数固定的3类模型

由于节点与边是复杂网络拓扑的两个基本要素,所以在节点数固定的复杂网络演化时,改变其结构和性质的唯一原因是网络连接边的变化。虽然此类模型中节点数在演化之初就已给定,但一般都比较大。本文将对节点数固定的复杂网络根据边连接方式将该类模型细分成3类模型:1)模型A,是在规则网络(regularnetwork)中以一定的概率p把原来的边进行重新连接,以增加该网络的随机性。2)模型B,是模型中边的任意重定向。3)模型C,是以一定的概率增加m条边,同时减少n条边。

2.1??模型A

规则网络是指每个节点都与它相邻的k个节点有边相连的网络[8]。为简单起见,这里只考虑一维规则网络的情况。此时对于规则网络,其边变化情况主要有两种方式,一是任意选择一个节点和与之相连的一条边,将此边复制后与网络中随机选择的另一个节点相连,另一种是不进行复制而直接连接。WS模型的连接方式即为后者,但它可能使平均最短路长度为无穷大,前一种连接方式却可保证使平均最短路长度为一个有限的数。目前已有对此类模型的平均最短路长度、聚类系数和度分布等的研究

2.2??模型B[8]。

在模型A中边连接变化时,与该边相连接的一个节点并没有改变。在模型B中,考虑边的任意重定向这种情况,也就是说,任意选择一条边以概率p复制后重新连接它的两个端点。由于选择的边的两个端点都发生变化,可知模型B在演化过程中其随机性比模型A增加得更快。对于模型B的聚类系数和平均最短路长度,数值模拟结果见图1所示。图中C(p)/C(0)和L(p)/L(0)的定义见文献[8],数值是当N=1000,k=5时取100次模型的平均值。

将图1与图2进行比较,可知模型B的聚类系数比模型A下降得更快,而平均最短路长度下降速度却比较缓慢。同时,由于模型B仍具有较大的聚类系数和较小的平均最短路长度,所以该模型仍具备??小世界??特性。

考虑在不同概率下的模型B的度分布,在不同概率(见图中所标各个概率值)下取N=2000,k=50,平均100次模拟的结果见图3所示。由模型B的度分布可知,该分布明显不具有幂律分布特性。另一方面,当

第2卷第2期

02????覃??森,等:节点数固定的复杂网络模型初探??9??log(k)从10增加到10时,log(P(k))下降的速率趋近于中间概率。这说明如果从0到1??调节??连接概率

p,模型B的结构并不是严格从规则网络变化到随机图网络。这与模型A

的变化情况截然不同。

图1??模型B的聚类系数与平均最短路长度图2??小世界网络的特征(文献[8]中图

2)

图3??不同概率下的模型B的度分布

2.3??模型C

此类模型从规则网络演化时,每次以一定的概率增加m条边,同时减少n条边,以此来模拟一些复杂网络进化过程中边有生有灭的情况[1,2,7,13,14]。由于在模型C中边的总数在不断变化,则其度分布也会不断改变,从而由规则网络变成无序网络。由于m与n的不确实性,考虑3种情况:m>n,m<n和m=n。如果m>n,即增加的边数比减少的边数大,则各个节点的度总体是不断增加的,整个网络的聚类系数是不断减少的,且当p不断增大时,其聚类系数迅速下降。反之,当m<n时,由于整个网络中边数有减少的趋势,所以其随机性不断减小,其聚类系数变大。而当m=n,由于整个网络中的边数几乎不变,则其聚类系数也缓慢变大。图4是6种不同的m和n情况下聚类系数的变化情况,取N=1000,k=20平均100次模型的结果从图4可以看出,边增加的速度越快,模型的聚类系数下降也越快。反之,当边减小的速度变快时,其聚类系数也

??????10??????????????????????????????????????复杂系统与复杂性科学2005年4月增加得越快,而当m=n时,聚类系数的变化比较缓慢。

对于模型C的平均最短路长度,在不同的m和n下其下降的速率也不相同。虽然无论是m>n,m<n还是m=n,当概率p时其平均最短路长度L不断减小。但当m>n时,L下降的速度明显快于m<n时,而m=n时L下降比较缓慢。图5是6组m和n值下模型C的平均最短路长度的数值模拟结果。

图6是在不同的p,m和n下模型C的度分布数值模拟结果。由图6可知,模型C的度分布近似泊松(Poisson)分布。在相同概率下,对于不同的m和n值,其度分布没有明显差别;当p增加时,度分布的峰度越来越平坦而趋近于泊松分布。这说明当概率p从0增加到1时,模型C从规则变为无序状态。

另外,还有一类节点数固定的复杂网络模型,即BA模型的变异模型[20],是指网络节点数不变,每次增加边时,采用择优连接方式进行连接,

由此得到的复杂网络的度分布近似于正态分布。

图4??模型C的聚类系数图5??模型C

的平均最短路长度

图6??模型C的度分布

第2卷第2期????覃??森,等:节点数固定的复杂网络模型初探??11??3??几点讨论

对以上的数值模拟结果,可得到如下几点讨论:

1)由模型B和模型C的聚类系数和平均最短路长度的数值模拟结果可知,它们均具有小的平均最短路长度和高的聚类系数,即表现出小世界特性。而由它们的度分布可知,它们均没有出现幂律分布。这表明如果复杂网络的节点数不变,则该网络就不会出现幂律分布,因而不是无标度网络,也表明网络增长性是无标度网络产生的内在机理之一。这一结果与文献[20]的结果相符合。

2)对模型B和模型C的数值模拟可知,复杂网络出现小世界特性主要是由于网络节点及其连接边的异质性,而与网络的节点数变化没有必然联系。当然,虽然它两类模型均表现出小世界特性,但它们的聚类系数与平均最短路长度具有各自不同的特性。

3)进一步,由于小世界网络与无标度网络产生的内在机理并不相同,并且它们是从复杂网络的不同侧面来描述网络的拓扑结构的??????小世界网络主要考虑复杂网络的聚类系数和平均最短路长度的相关特性,而无标度网络主要的判断方法是网络的度分布是否是幂律分布,因此传统复杂网络的分类方法是不尽合理的,从而有必要进行新的分类。基于这一要求,本文将复杂网络按节点数变化情况分成两类。此分类方式能较好地解释了小世界特性与无标度特性在现实复杂网络中共存的原因,即它们描述了网络不同侧面的相关性质,有交叉之处但没有矛盾。

本文主要研究了复杂网络的一种分类,并对节点数固定的复杂网络进行了分析。当然,对复杂网络的分类是一个较为困难的问题,必须对网络的演化机理进行深入的研究才能得到有效的分类。目前对无标度特性产生的内在机理已经有了一些研究成果,但很少针对小世界特性产生的原因进行研究,本文得到的结果??????小世界特性产生源于节点与边的异质性,与节点数是否改变无关??????也只是其中的一个机理而已。下一步的研究应集中在对小世界的成因进行研究,进而得到复杂网络演化内在的机理,对网络进行更加合理而全面的分类。

参考文献:

[1]AlbertR,Barab??siAL.Statisticalmechanicsofcomplexnetworks[J].RevModPhys,2002,74(1):47-97.

[2]NewmanMEJ.Thestructureandfunctionofcomplexnetworks[J].SIAMReview,2003,45(2):167-256.

[3]MilgramS.Thesmallworldproblem[J].PsychToday,1967,2:60-67.

[4]WattsDJ.SmallWorlds[M].NJ:Princetonuniversitypress,1999.

[5]BarabasiAL,AlbertR.Emergenceofscalinginrandomnetworks[J].Science,1999,286:509-512.

RevE,2001,64(2):026118.

[7]DorogovtsevSN,MendesJFF.Evolutionofnetworks[J].AdvinPhys,2002,51:1079-1187.

[8]WattsDJ,StrogatzSH.Collectivedynamicsof??small??world??networks[J].Nature,1998,393(6):440-442.

[9]MasudaN,KonnoN.Transmissionofsevereacuterespiratorysyndromeindynamicalsmall??worldnetworks[J].PhysRevE,

2004,69(3):031917.

[10]ZanetteDH.Dynamicsofrumorpropagationonsmall??worldnetworks[DB/OL].arXiv:0110324,2001.

[11]WangXF,http://wendang.chazidian.complexnetworks:small??world,scale??freeandbeyond[J].IEEEcircuitsandsystemsmagazine,2003,

3(1):6-20.

[12]DorogovtsevSN,MendesJFF.EvolutionofNetwork:FromBiologicalNetstotheInternetandWWW[M].London:Oxford

UniversityPress,2003.

[13]JeongH,TomborB,AlbertR,eta.lThelarge??scaleorganizationofmetabolicnetworks[J].Nature,2000,407:651-654.

[14]KleinbergJ,LawrenceS.Thestructureoftheweb[J].Science,2001,294:1849-1850.

[15]StrogatzSH.Exploringcomplexnetworks[J].Nature,2001(8),410:268-276.[6]NewmanMEJ,StrogatzSH,WattsDJ.Randomgraphswitharbitrarydegreedistributionsandtheirapplications[J].Phys