复杂网络简介优秀PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,复杂网络简介,1,复杂网络简介,第一部分：,引言,第二部分：,几种经典的网络模型,第三部分：,网络研究中常见的统计量,2,第一部分 引言,1.1,网络的概念以及相关研究,1.2,与交通相关的网络研究,3,1.1,网络的概念以及相关研究,复杂网络研究的是介于,确定,和,随机,之间的现实中的系统。一个典型的网络由节点和连接两个节点的边组成。,很长时间以来，网络被考虑成点和边的随意集合，在数学上用随机图表示。近几年，由于计算机数据处理和运算能力的飞速发展，这种状况发生了根本性的改变。人们开始研究大规模复杂网络的拓扑结构，研究发现，尽管很多网络具有明显的复杂性和随机性，但也会出现可以用数学和统计语言来描述的清晰的模式和规律，其中最重要的是,小世界效应,（,small-world effect,），,(,Watts&Strogatz,1998,),和,无标度特性,（,scale-free property,），,(,Barabsi&Albert,1999,),。,第一部分 引言,4,1.2,与交通相关的网络研究,迄今为止，对交通系统及相关网络复杂性的研究成果还十分有限，较少的研究也主要集中在航空、地铁和铁路网络上。,Amaral,et.al.,（,2000,）研究了世界航空网络的拓扑结构；,Latora,和,Marchiori,（,2002,）对波士顿地铁的网络特性进行了初步研究；,Sen,et.al.,（,2002,）研究了印度铁路网络的小世界特性；,Jiang,和,Claramunt,（,2004,）对城市道路网络进行了研究，以实例说明了此网络具有小世界特性；,Wu,et.al.,(2004a),以北京市为例，说明了城市公交网络为无标度网络；借助于,SIR,传播模型，,Wu,et.al.,(2004b),提出了一种交通拥堵的演化模型。但是城市交通网络的相关研究结果并不十分深入，其理论也并不完善。如何深入理解城市交通网络的演化机制，是合理设计网络的基础。,第一部分 引言,5,第二部分 几种经典的网络模型,2.1,网络的生成过程,2.2,网络图,6,2.1,网络的生成过程,在这一部分，我们将主要讨论以下几种网络模型：规则网络（,Lattice network,）、随机网络（,ER,模型）、小世界网络（,WS,模型）、无标度网络（,BA,模型）。,在复杂网络的研究过程中，人们将网络中的节点用,1,，,2,，,，,N,表出（注意：网络中的节点个数,N,可以是动态变化的，也就是说网络可以而且应该是一个不断演化的过程），网络建模主要考虑的是点与点之间的连边机制，下面详细说明一下这四种网络的生成过程。,第二部分 几种经典的网络模型,7,（,i,）,规则网络,（,Lattice,）：节点个数,N,为不变的参数，将这,N,个编号的节点通过以下的连边机制：每个节点连接到它的,K,临近的节点 ，这里,K,是一个偶整数。,（,ii,）,随机网络,（,ER,）：节点个数,N,为不变的参数，将这,N,个编号的节点通过以下的连边机制：节点 和节点 连接的概率为 。,（,iii,）,小世界网络,（,WS,）：节点个数,N,为不变的参数，将这,N,个编号的节点通过以下两个过程的连边机制：（,1,）,初始化,：构造一个,Lattice,网络；（,2,）,随机化,：将网络中的每一条边以概率 进行重连（即遍历选取每一条边，固定边的一个节点，以概率选择另一个节点进行连接）。显然,WS,网络是规则网络当 ，是随机网络当 。,（,iv,）,无标度网络,（,BA,）：节点个数,N,不断增加的演化网络，点边机制是通过以下两个过程生成的：（,1,）,增长性,：初始网络为 个节点，在每一个时间步增加一个新的节点，同时这个新节点与网络中 个已经存在的节点相连；（,2,）,偏好连接,：新节点选择节点进行连接是有偏好的，连接概率 正比与节点的度，即选择节点 进行连接的概率 。程序的终止条件是事先给定的时间步或者网络的规模,N,。,8,2.2,网络图,对应的网络如图,1,（规则网络、随机网络和小世界网络）和图,2,（无标度网络）：,Fig.1,The random rewiring procedure of the Watts-Strogatz model,which interpolates between a regular ring lattice and a random network without altering the number of nodes or edges.We start with,N,=20 nodes,each connected to its four nearest neighbors.For,p,=0 the original ring is unchanged;as,p,increases the network becomes increasingly disordered until for,p,=1 all edges are rewired randomly.,第二部分 几种经典的网络模型,9,Fig.2 An example of scale-free network.,10,第三部分 网络研究中常见的统计量,3.1,各种常见统计量的求解过程,3.2,部分统计量的关系图,11,3.1,各种常见统计量的求解过程,在复杂网络的研究中，人们经常用到的统计量有：度分布（,degree distribution,）、平均最短距离（,average shortest path length,）、群聚系数（,clustering coefficient度相关系数（,assortativity coefficient,）、介中性（,betweenness centrality,）等，下面将详述它们的求解过程。,第三部分 网络研究中常见的统计量,12,（,i,）度分布：，其中 表示网络中度为,k,的节点个数，为网络中的总节点数。,（,ii,）平均最短距离：，其中 表示节点 与节点 之间的最短距离，求两点之间的最短距离的算法很多，这里不再赘述。,（,iii,）群聚系数：，其中 ，表示节点的度，即它的邻居个数，表示 个邻居中相互连接的对数。这种只是其中一个比较常用的定义方式，还有一些其它的关于群聚系数的定义，这里不再赘述,。,13,（,iv,度相关系数：关于度相关系数 的定义也很多，这里只叙述其中一个，如下：先提出节点的超出度 为节点度减,1,，超出度分布 ，其中 是度分布，再定义一个概率 表示超出度为,j,的节点与超出度为,k,的节点之间有边连接的联合概率。则 ，其中 。,（,v,）介中性：有节点介中性和边介中性之分，表示网络中任何两个节点之间的最短路经过某一节点或边的总次数，如果两节点之间的最短路 条，则均匀分配在每条最短路上，即经过每条最短路的次数为 ，这样所有节点或边的介中性就可以统计出来。介中性在交通运输方面有一定的意义。,14,3.2,部分统计量的关系图,就上面四种网络，关于这些统计量的研究如下表：,第三部分 网络研究中常见的统计量,Lattice,ER,模型,WS,模型,BA,模型,度分布,泊松分布,泊松分布,幂率分布,平均最短距离,大,小,小,小,群聚,系数,大,小,大,大,度相关,不相关,介中性,幂率分布,15,其中度分布是目前最具有代表性的统计量，对于,ER,模型、,WS,模型和,BA,模型的度分布如图,3-4,。另外，对于,WS,模型，网络的最短平均距离,L,和群聚系数,C,与重连概率,p,的变化关系如图,5,所示,Fig.3,Degree distribution of the Watts-Strogatz model for,K,=3,N,=1000 and various,p,.,16,Fig.4,Numerical simulations of network evolution:Degree distribution of the Barabasi-Albert model,with ,and,;,;,;,.The slope of the dashed line is ,providing the best fit to the data.The inset shows the rescaled distribution(see text),for the same values of,m,the slope of the dashed line being .,17,Fig.5 Characteristic average shortest path length,L,(,p,)and clustering coefficient,C,(,p,)for the Watts-Strogatz model.The data are normalized by the values,L,(0)and,C,(0)for a regular lattice.A logarithmic horizontal scale resolves the rapid drop in,L,(,p,),corresponding to the onset of the small-world phenomenon.During this drop,C,(,p,)remains almost constant,indicating that the transition to a small world is almost undetectable at the local level.,18,THE END,Thanks,！,19,