复杂网络简介

复杂网络简介•第一部分：引言•第二部分：几种经典的网络模型•第三部分：网络研究中常见的统计量第一部分引言•1.1网络的概念以及相关研究•1.2与交通相关的网络研究1.1网络的概念以及相关研究复杂网络研究的是介于确定和随机之间的现实中的系统。一个典型的网络由节点和连接两个节点的边组成。很长时间以来，网络被考虑成点和边的随意集合，在数学上用随机图表示。近几年，由于计算机数据处理和运算能力的飞速发展，这种状况发生了根本性的改变。人们开始研究大规模复杂网络的拓扑结构，研究发现，尽管很多网络具有明显的复杂性和随机性，但也会出现可以用数学和统计语言来描述的清晰的模式和规律，其中最重要的是小世界效应（small-worldeffect），(Watts&Strogatz,1998)和无标度特性（scale-freeproperty），(Barabási&Albert,1999)。第一部分引言1.2与交通相关的网络研究迄今为止，对交通系统及相关网络复杂性的研究成果还十分有限，较少的研究也主要集中在航空、地铁和铁路网络上。Amaralet.al.（2000）研究了世界航空网络的拓扑结构；Latora和Marchiori（2002）对波士顿地铁的网络特性进行了初步研究；Senet.al.（2002）研究了印度铁路网络的小世界特性；Jiang和Claramunt（2004）对城市道路网络进行了研究，以实例说明了此网络具有小世界特性；Wuet.al.(2004a)以北京市为例，说明了城市公交网络为无标度网络；借助于SIR传播模型，Wuet.al.(2004b)提出了一种交通拥堵的演化模型。但是城市交通网络的相关研究结果并不十分深入，其理论也并不完善。如何深入理解城市交通网络的演化机制，是合理设计网络的基础。第一部分引言第二部分几种经典的网络模型•2.1网络的生成过程•2.2网络图2.1网络的生成过程•在这一部分，我们将主要讨论以下几种网络模型：规则网络（Latticenetwork）、随机网络（ER模型）、小世界网络（WS模型）、无标度网络（BA模型）。•在复杂网络的研究过程中，人们将网络中的节点用1，2，…，N表出（注意：网络中的节点个数N可以是动态变化的，也就是说网络可以而且应该是一个不断演化的过程），网络建模主要考虑的是点与点之间的连边机制，下面详细说明一下这四种网络的生成过程。第二部分几种经典的网络模型•（i）规则网络（Lattice）：节点个数N为不变的参数，将这N个编号的节点通过以下的连边机制：每个节点连接到它的K临近的节点，这里K是一个偶整数。•（ii）随机网络（ER）：节点个数N为不变的参数，将这N个编号的节点通过以下的连边机制：节点和节点连接的概率为。•（iii）小世界网络（WS）：节点个数N为不变的参数，将这N个编号的节点通过以下两个过程的连边机制：（1）初始化：构造一个Lattice网络；（2）随机化：将网络中的每一条边以概率进行重连（即遍历选取每一条边，固定边的一个节点，以概率选择另一个节点进行连接）。显然WS网络是规则网络当，是随机网络当。•（iv）无标度网络（BA）：节点个数N不断增加的演化网络，点边机制是通过以下两个过程生成的：（1）增长性：初始网络为个节点，在每一个时间步增加一个新的节点，同时这个新节点与网络中个已经存在的节点相连；（2）偏好连接：新节点选择节点进行连接是有偏好的，连接概率正比与节点的度，即选择节点进行连接的概率。程序的终止条件是事先给定的时间步或者网络的规模N。1,2,...,2Kiiiijpp0p1p0m0()mmmipiiijjkpk2.2网络图•对应的网络如图1（规则网络、随机网络和小世界网络）和图2（无标度网络）：•Fig.1TherandomrewiringprocedureoftheWatts-Strogatzmodel,whichinterpolatesbetweenaregularringlatticeandarandomnetworkwithoutalteringthenumberofnodesoredges.WestartwithN=20nodes,eachconnectedtoitsfournearestneighbors.Forp=0theoriginalringisunchanged;aspincreasesthenetworkbecomesincreasinglydisordereduntilforp=1alledgesarerewiredrandomly.第二部分几种经典的网络模型•Fig.2Anexampleofscale-freenetwork.第三部分网络研究中常见的统计量•3.1各种常见统计量的求解过程•3.2部分统计量的关系图3.1各种常见统计量的求解过程•在复杂网络的研究中，人们经常用到的统计量有：度分布（degreedistribution）、平均最短距离（averageshortestpathlength）、群聚系数（clusteringcoefficient）、度相关系数（assortativitycoefficient）、介中性（betweennesscentrality）等，下面将详述它们的求解过程。第三部分网络研究中常见的统计量•（i）度分布：，其中表示网络中度为k的节点个数，为网络中的总节点数。•（ii）平均最短距离：，其中表示节点与节点之间的最短距离，求两点之间的最短距离的算法很多，这里不再赘述。•（iii）群聚系数：，其中，表示节点的度，即它的邻居个数，表示个邻居中相互连接的对数。这种只是其中一个比较常用的定义方式，还有一些其它的关于群聚系数的定义，这里不再赘述。()knPknknn1(1)/2ijijldnnijdij1iiCCnid(1)/2iiiieCddieid•（iv）度相关系数：关于度相关系数的定义也很多，这里只叙述其中一个，如下：先提出节点的超出度为节点度减1，超出度分布，其中是度分布，再定义一个概率表示超出度为j的节点与超出度为k的节点之间有边连接的联合概率。则，其中。•（v）介中性：有节点介中性和边介中性之分，表示网络中任何两个节点之间的最短路经过某一节点或边的总次数，如果两节点之间的最短路条，则均匀分配在每条最短路上，即经过每条最短路的次数为，这样所有节点或边的介中性就可以统计出来。介中性在交通运输方面有一定的意义。rq(1)(1)()()kkPkqkkPk()Pjke21(()())jkjkqrjkeqjqk222()[()]qkkkqkkqkijT1ijT3.2部分统计量的关系图•就上面四种网络，关于这些统计量的研究如下表：第三部分网络研究中常见的统计量LatticeER模型WS模型BA模型度分布泊松分布泊松分布幂率分布平均最短距离大小小小群聚系数大小大大度相关不相关介中性幂率分布•其中度分布是目前最具有代表性的统计量，对于ER模型、WS模型和BA模型的度分布如图3-4。另外，对于WS模型，网络的最短平均距离L和群聚系数C与重连概率p的变化关系如图5所示•Fig.3DegreedistributionoftheWatts-StrogatzmodelforK=3,N=1000andvariousp.•Fig.4Numericalsimulationsofnetworkevolution:DegreedistributionoftheBarabasi-Albertmodel,with,and○,;□,;◊,;∆,.Theslopeofthedashedlineis,providingthebestfittothedata.Theinsetshowstherescaleddistribution(seetext)forthesamevaluesofm,theslopeofthedashedlinebeing.0300000Nmt01mm03mm05mm07mm2.92()/2Pkm3•Fig.5CharacteristicaverageshortestpathlengthL(p)andclusteringcoefficientC(p)fortheWatts-Strogatzmodel.ThedataarenormalizedbythevaluesL(0)andC(0)foraregularlattice.AlogarithmichorizontalscaleresolvestherapiddropinL(p),correspondingtotheonsetofthesmall-worldphenomenon.DuringthisdropC(p)remainsalmostconstant,indicatingthatthetransitiontoasmallworldisalmostundetectableatthelocallevel.