复杂网络简介.ppt

复杂网络简介,复杂网络简介,第一部分：引言第二部分：几种经典的网络模型第三部分：网络研究中常见的统计量,第一部分引言,1.1网络的概念以及相关研究1.2与交通相关的网络研究,1.1网络的概念以及相关研究,复杂网络研究的是介于确定和随机之间的现实中的系统。一个典型的网络由节点和连接两个节点的边组成。很长时间以来，网络被考虑成点和边的随意集合，在数学上用随机图表示。近几年，由于计算机数据处理和运算能力的飞速发展，这种状况发生了根本性的改变。人们开始研究大规模复杂网络的拓扑结构，研究发现，尽管很多网络具有明显的复杂性和随机性，但也会出现可以用数学和统计语言来描述的清晰的模式和规律，其中最重要的是小世界效应（small-worldeffect），(Wattsaspincreasesthenetworkbecomesincreasinglydisordereduntilforp=1alledgesarerewiredrandomly.,第二部分几种经典的网络模型,Fig.2Anexampleofscale-freenetwork.,第三部分网络研究中常见的统计量,3.1各种常见统计量的求解过程3.2部分统计量的关系图,3.1各种常见统计量的求解过程,在复杂网络的研究中，人们经常用到的统计量有：度分布（degreedistribution）、平均最短距离（averageshortestpathlength）、群聚系数（clusteringcoefficient）、度相关系数（assortativitycoefficient）、介中性（betweennesscentrality）等，下面将详述它们的求解过程。,第三部分网络研究中常见的统计量,（i）度分布：，其中表示网络中度为k的节点个数，为网络中的总节点数。（ii）平均最短距离：，其中表示节点与节点之间的最短距离，求两点之间的最短距离的算法很多，这里不再赘述。（iii）群聚系数：，其中，表示节点的度，即它的邻居个数，表示个邻居中相互连接的对数。这种只是其中一个比较常用的定义方式，还有一些其它的关于群聚系数的定义，这里不再赘述。,（iv）度相关系数：关于度相关系数的定义也很多，这里只叙述其中一个，如下：先提出节点的超出度为节点度减1，超出度分布，其中是度分布，再定义一个概率表示超出度为j的节点与超出度为k的节点之间有边连接的联合概率。则，其中。（v）介中性：有节点介中性和边介中性之分，表示网络中任何两个节点之间的最短路经过某一节点或边的总次数，如果两节点之间的最短路条，则均匀分配在每条最短路上，即经过每条最短路的次数为，这样所有节点或边的介中性就可以统计出来。介中性在交通运输方面有一定的意义。,3.2部分统计量的关系图,就上面四种网络，关于这些统计量的研究如下表：,第三部分网络研究中常见的统计量,其中度分布是目前最具有代表性的统计量，对于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.,Fig.5CharacteristicaverageshortestpathlengthL(p)andclusteringcoefficientC(p)fortheWatts-Strogatzmodel.ThedataarenormalizedbythevaluesL(0)andC(0)foraregularlattice.AlogarithmichorizontalscaleresolvestherapiddropinL(p),correspondingtotheonsetofthesmall-worldphenomenon.DuringthisdropC(p)remainsalmostc