《复杂网络简介》PPT课件.ppt

复杂网络简介,复杂网络简介,第一部分：引言第二部分：几种经典的网络模型第三部分：网络研究中常见的统计量,第一部分 引言,1.1 网络的概念以及相关研究1.2 与交通相关的网络研究,1.1 网络的概念以及相关研究,复杂网络研究的是介于确定和随机之间的现实中的系统。一个典型的网络由节点和连接两个节点的边组成。很长时间以来，网络被考虑成点和边的随意集合，在数学上用随机图表示。近几年，由于计算机数据处理和运算能力的飞速发展，这种状况发生了根本性的改变。人们开始研究大规模复杂网络的拓扑结构，研究发现，尽管很多网络具有明显的复杂性和随机性，但也会出现可以用数学和统计语言来描述的清晰的模式和规律，其中最重要的是小世界效应（small-world effect），(Watts&Strogatz,1998)和无标度特性（scale-free property），(Barabsi&Albert,1999)。,第一部分 引言,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)提出了一种交通拥堵的演化模型。但是城市交通网络的相关研究结果并不十分深入，其理论也并不完善。如何深入理解城市交通网络的演化机制，是合理设计网络的基础。,第一部分 引言,第二部分 几种经典的网络模型,2.1 网络的生成过程2.2 网络图,2.1 网络的生成过程,在这一部分，我们将主要讨论以下几种网络模型：规则网络（Lattice network）、随机网络（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。,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.,第二部分 几种经典的网络模型,Fig.2 An example of scale-free network.,第三部分 网络研究中常见的统计量,3.1 各种常见统计量的求解过程3.2 部分统计量的关系图,3.1 各种常见统计量的求解过程,在复杂网络的研究中，人们经常用到的统计量有：度分布（degree distribution）、平均最短距离（average shortest path length）、群聚系数（clustering coefficient）、度相关系数（assortativity coefficient）、介中性（betweenness centrality）等，下面将详述它们的求解过程。,第三部分 网络研究中常见的统计量,（i）度分布：，其中 表示网络中度为 k 的节点个数，为网络中的总节点数。（ii）平均最短距离：，其中 表示节点 与节点 之间的最短距离，求两点之间的最短距离的算法很多，这里不再赘述。（iii）群聚系数：，其中，表示节点的度，即它的邻居个数，表示 个邻居中相互连接的对数。这种只是其中一个比较常用的定义方式，还有一些其它的关于群聚系数的定义，这里不再赘述。,（iv）度相关系数：关于度相关系数 的定义也很多，这里只叙述其中一个，如下：先提出节点的超出度 为节点度减1，超出度分布，其中 是度分布，再定义一个概率 表示超出度为 j 的节点与超出度为 k 的节点之间有边连接的联合概率。则，其中。（v）介中性：有节点介中性和边介中性之分，表示网络中任何两个节点之间的最短路经过某一节点或边的总次数，如果两节点之间的最短路 条，则均匀分配在每条最短路上，即经过每条最短路的次数为，这样所有节点或边的介中性就可以统计出来。介中性在交通运输方面有一定的意义。,3.2 部分统计量的关系图,就上面四种网络，关于这些统计量的研究如下表：,第三部分 网络研究中常见的统计量,其中度分布是目前最具有代表性的统计量，对于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.,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.,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.,THE END,Thanks！,