复杂网络及其在无标度网络中的瞬时同步现象(共35页).doc

精选优质文档-倾情为你奉上毕业论文(设计) 题 目 复杂网络及其在无标度网络中的瞬时同步现象 学生姓名 学 号 院 系 专 业 指导教师 二一一年五月二十五日专心-专注-专业目 录复杂网络及其在无标度网络中的瞬时同步现象潘玉剑南京信息工程大学电子与信息工程学院，南京，摘 要：网络在自然界和人类社会中无处不在，常见的网络有生态网、万维网、人际关系网和交通网络等等。对真实网络特性的解释使得复杂网络成为了近年来的研究热点之一。自从发现瞬时过渡转变现象以来，集体性的瞬变现象得到了极大的关注。过渡一词是用来表述网络或网格在连接度上的急剧变化。实验证明，不同的网络增长过程会带来网络的一阶突变，即不连续的变化。本文着重探索当在网络拓扑结构k和动态特性w之间存在关系时无标度网络的一些特性。本文首先介绍了复杂网络的发展过程，接着定义了描述网络的各种参数及网络的经典模型，第三部分介绍了网络的同步现象和该现象的基本分析，最后，根据已有的网络模型，进而验明了本文第四部分提出的设想，即无标度网络中的瞬时同步变化。关键词：同步；复杂网络；无标度网络；过渡；度分布1绪论复杂性科学研究兴起于20世纪七八十年代，是用来研究复杂系统和复杂性的一门交叉学科。它研究的复杂系统涉及的范围很广，包括自然、工程、生物、经济、管理、政治与社会等各个方面。它探索的复杂现象小至一个细胞呈现出来的生命现象，大至股票市场的涨落、城市交通的管理、自然灾害的预测，乃至社会的兴衰。复杂网络广泛存在于自然界和人类社会，是复杂性科学中复杂系统的抽象，网络中的节点是复杂系统中的个体，节点之间的边则是系统中个体之间按照某种规则而自然形成或人为构造的一种关系或相互作用。复杂网络可以用来描述从技术到生物直至社会各类开放复杂系统的骨架，而且是研究它们拓扑结构和动力学性质的有力工具。复杂网络简而言之即呈现高度复杂性的网络。其复杂性主要表现在以下几个方面：1)结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。2)网络进化：表现在节点或连接的产生与消失。例如万维网，网页或链接随时可能出现或断开，导致网络结构不断发生变化。3)连接多样性：节点之间的连接权重存在差异，且有可能存在方向性。4)动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。5)节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。 6)多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如设计一个城市的公交线路网络需要考虑此城市公交线路的演化过程，此演化过程决定网络的拓扑结构。当两个站点之间的人流量越大时，它们之间的连接权重也越大，这时需要调整两个站点间的公交车数量来逐步改善网络性能。1.1复杂网络的发展及研究概况复杂网络研究传统上属于图论范畴，复杂网络虽然刚刚起步，但受实际网络例如计算机网、社会网的实证研究的激励，复杂网络成为了一个活跃的研究领域。近年来，在高档杂志发表(或者被SCI收录)的复杂网络方向的论文数量呈逐年递增的趋势，有关复杂网络的专题会议也越来越多。1.1.1复杂网络的发展追溯图论的发展轨迹，图论的发展主要经历了三个阶段，提出了三类经典的理论模型，包括Euler经典图论、ER随机图以及小世界网络模型和无标度网络模型。1736年，瑞士数学家Euler考虑了著名的哥尼斯堡七桥问题。他用抽象分析的方法将这个问题转化为图论问题，即把每一块陆地用一个点来表示，将每一座桥用连接相应的两个点的一条线来代替，从而得到一个图。Euler的研究开创了图论这门新的数学分支，成为图论发展的第一个里程碑。此后的两百多年里，现实系统都是用一些规则的网络结构，如一维链、二维平面欧几里得格网、近邻环网等来表示。20世纪五六十年代，匈牙利两个著名的数学家Erdos和Renyi又一次对图论作出了第二个里程碑式的贡献。他们建立了著名的随机图理论，用相对简单且无明确设计原理的大规模随机图来描述网络，使得边的出现成为概率事件，简称为ER随机图理论3。随机图和经典图论之间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数学性质也发生了巨大的变化。由于随机图理论简单而且易于接受，随机图的思想主宰了网络研究长达四十年之久。由于许多实际网络具有相同的定性性质，且随机图理论不能描述和解释现实的复杂现象。20世纪末，随着计算机技术的高度发展，人们拥有各种网络的数据库，因此对大规模的网络进行实证研究成为了可能。网络科学又一次取得突破性进展，出现了第三个里程碑。美国的Watts和Strogatz发表了题为“小世界网络的群体动力行为”的论文4，他们推广了“六度分离”的科学假设，提出了介于规则网络和随机网络之间的小世界网络模型，此模型具有较大的群集系数和较短的平均路径。小世界特征提出之后，1999年美国的Barabasi和Albert通过实证模拟，发现万维网节点的度分布具有幂指数函数的规律6。度用来描述与节点相连的边的数目。在不同的网络中，度所代表的含义也不尽相同。例如，在社会网络中，度可表示个体的作用力和影响程度，一个节点的度越大，表示在整个网络系统组织中的作用和影响就越大，反之亦然。在城市公交网络中，度分布表示城市站点之间的公交线路的多少和重要程度，度越大的站点，其重要性就越大。因为幂指数函数在双对数坐标中是一条直线，这个分布与系统特征长度无关，所以这个特性被称为无标度性质。它反映网络中度分布的不均匀性，只有很少数的节点与其它节点有很多的连接，成为“中心节点”，而大多数节点度很小。针对万维网的动态变化过程，Barabasi等6抽象出了一类以均匀增长和线性择优为机制的无标度网络模型(BA模型)，复杂网络的研究由此掀开了新的篇章。1.1.2复杂网络的研究概况自小世界性质和无标度特征提出之后，复杂网络的研究取得了许多重要进展。一方面为了发现和刻画实际系统的网络结构，接近现实网络的新的网络模型被不断提出，网络的统计特征逐渐明确，分析方法越来越多，越来越严格。另一方面，为了更深刻的理解复杂系统内部的工作方式和机理，复杂网络上的动力学得到广泛研究，包括网络同步、疾病传播等。现实网络的统计特征主要包括小世界性质(网络中节点之间的平均距离很短)、无标度性质(网络中节点的度分布向右偏斜，具备幂函数形式)以及群集性或网络传递性等。无标度性质是现实网络的一个重要特征。BA模型是产生无标度网络的最简单模型。在BA模型中，旧节点得到连线的概率(k)被假设为与节点的度数k成正比。对于某些实际网络，例如因特网、引文网、美国国立医学图书馆MEDLINE数据库及Los Alamos档案文件库等，(k)与度数k确实有近似线性关系。但对其它网络如科研合作网络、演员合作网络， 该相互关系是亚线性的。基于此，Krapivsky等8提出了非线性择优的网络模型，通过对亚线性、近似线性和超线性择优机制的研究发现，只有近似线性择优能产生无标度网络。同时，由于BA模型初始状态节点的度数均为零，导致择优无法进行，而实际网络中孤立节点被连线的概率是非零的。Dorogovtsev等9将线性择优规则修改为带有吸引度的择优，这样，即使初始时刻度数为零的节点也有机会得到连线。然而，新节点选择旧节点连线时，既有择优的可能，又有随机性。基于择优加随机的混合机制，学者们又提出了能在随机网络和无标度网络之间变化的网络模型。由于BA模型对网络增长只包含一种机制，即增加新的节点并连接到系统中己有节点。而现实网络中，网络是不断演化的。为了更好的吻合现实网络，除了通过改变择优规则，人们还通过节点的重新连线或者增加和删除原有连线来推广BA模型。Bollobas等10考虑了允许节点自连线和重复连线的网络模型。Albert和Barabasi5,6研究了包含旧节点间新增连线以及旧边重连的网络模型。Cooper等将BA模型一般化，既考虑增加新节点，又考虑旧节点之间增加新连线的情形。Dorogovtsev和Mendes9分析了一类在旧节点间增加连线，同时又以一定概率删除旧边的无向图模型。针对现实网络节点的有限寿命(如：社会网、引文网)或边的有限容量(如：因特网的路由器或电力网络的节点)，部分学者提出了影响度分布的限制条件。他们指出旧节点得到连线的概率不仅与其度数成正比，而且与其年龄有关，模型假设旧节点逐渐停止连线的过程遵循幂函数规律。然而，大量事实表明，实际网络中，节点的度及其增长速度并非只取决于年龄Bianconi和Barabasi15指出每个节点都有依靠消耗其它节点而竞争获得连线的本能，他们给每个节点定义一个适应能力参数，旧节点得到连线的概率与节点的度数和适应能力成正比。除了按节点择优连线，Dorogovtsev等9提出了一个按边选择节点的简略模型。模型初始为三节点完全图，每个时间步，增加一个新节点并连接到随机选择的一条边的两个端点。按此方式得到的网络模型与BA模型具有相似的结构。现实网络模型几乎都具有幂率度分布和较大的群集系数，较短的平均路径，而由BA模型演化来的网络模型大都只具有幂率分布，群集系数较小。Holme和Kim，Szabo等在一般的无标度网络模型中引入一个形成三元组的步骤。新节点与某一旧节点连线后，再以一定的概率与被选旧节点的邻居连线，从而达到较大群集系数。考虑到对诸如世界贸易网之类的网络，人们往往不需要知道全局信息，而只需要了解与自己相关联的信息，李翔和陈关荣提出了局域世界网络模型。新节点加入时，在网络中随机选择M (M为常数)个节点作为新节点的局域世界，新节点与局域世界中的节点择优连线。选取不同的M值，可使得模型的度分布在指数分布和幂率分布之间变化。由于随机选取一部分节点作为新节点的局域世界不符合现实情况，GomezGardenes和Moreno(GM)25赋予每个新节点一个参数，此参数用来衡量节点与其它给定节点之间的亲密程度或者几何距离。规定与节点的距离在某范围之内的所有节点作为此节点的邻域世界。通过邻域世界内部的择优连接，生成无标度网络。与局域世界类似的一个概念是团体11,15。团体是由一系列节点组成的，团体内部连线非常密集而团体之间连线稀疏。团体结构广泛存在于社会网络和生物网络中。团体结构网络除了团体内部的择优连线还有团体之间的择优连线或者新团体的增加。寻找网络中的团体结构也是非常重要的一个内容。在演员合作网和科学家合作网中，如果把一部电影或者一个著作看成任意节点间都相互连接的集团，那么整个合作网的演化过程就是一个个集团的增加过程。集团与集团之间可能通过一些简单的关系相互连接，也可能相互融合。现实网络中很多网络嵌有集团结构。除了团体、集团结构，网络还具有层次性、二分性和非对称性等，例如层次网络，二分网络，非对称性网络。描述和刻画网络的统计特征逐渐的被发现，求解复杂网络特征参数的方法也越来越多，越来越严格。对于度分布，Barabasi等6首先提出了平均场方法，它假设节点的度数为连续变量，通过某一随机选取的节点度数的变化率来求解度分布。Krapivsky等8分析度数为k的节点个数的变化率，从而得到率方程，利用大数定理推导模型的度分布。Dorogovtsev等9通过讨论节点在某时刻具有度数无的概率，列出主方程，并用Z变换进行求解。史定华等将复杂网络与马氏链相结合，利用数值模拟的方法得到度分布的数值解。第一个严格求解度分布的方法是Bollobas等提出的。他们利用n划分求解网络中入度为k的节点总数，再利用鞅方法得到网络度分布。一般情况下，网络中各节点的度是相互关联的，因此节点度的相关性和群集系数也是刻画网络的一个重要统计特征。Newman21定义匹配系数来衡量节点度相关性，发现社会网络一般是同类匹配，而技术和生物网络倾向于非同类匹配。Dorogovtsev等9定义瞬时联合度分布来衡量相邻节点对的度相关性。瞬时联合度分布的极限存在时，即可得到稳态联合度分布。Krapivsky材和Render8,15利用率方程方法分析了BA模型的度相关性，得到解析表达式。对BA模型以外的其它模型，则很少有解析结果。复杂网络在多个科学领域，包括自然、社会、工程、生物、经济、政治与管理等各个方面都有广泛应用。常见的网络有社会网络、技术网络、信息网络、生物网络和交通运输网络。社会网络包括朋友关系网、科学引文网、科研合作网、演员网、性关系网, Email网、达尔文和爱因斯坦通信网络、语言网、疾病传播、艾滋病网,世界贸易网等。技术网络包括因特网、万维网、电力网、移动电话网等。信息网络包括文献索引网络、计算机网络等。生物网络包括氨基酸网络、生态网、蛋白质相互作用网络、神经网络,基因网络、新陈代谢网络、食物链网络等。交通运输网络包括航空网、城市公共交通网、道路交通网、铁路网、公路网、自然河流网等。2复杂网络概述复杂网络近年来已成为科学研究的一个热点问题，其研究遍及多个科学领域，包括物理学、数学、生物学、计算机科学、经济学、管理学等、各学科研究人员从不同的角度，用不同的方法讨论复杂网络的性质，提出了多个刻画复杂网络结构特征的重要参数，建立了描述各种不同现实网络的基本模型，并提供了适合实证研究和理论分析等不同侧重点的求解方法。本章将对复杂网络的几个重要统计参数、基本模型、求解方法做简要介绍，为后续章节做理论铺垫。2.1描述复杂网络的参数为了刻画复杂网络拓扑结构和动力学性质，学者们提出了很多描述复杂网络特征的统计参量和度量方法。最主要的特征参数包括度分布、度相关性、群集系数及平均路径长度等，其它的还有介数、最大连通图和相称性系数等。为了更好的理解这些参数，本节将对一些重要的概念做扼要的介绍。2.1.1网络(图)的定义及描述粗略的说，图是由一些小圆点(称为节点或顶点)和连结这些圆点的直线或曲线(称为边或弧)组成的，是节点与连线的集合，是用来表示物件与物件之间的关系的方法，是图论的基本研究对象。定义2.1网络(图)G是一个二元组(V,E)，其中V为节点(Vertex或Node)的有穷集合，E为边(Edge或Node)的集合，它们亦可写成V(G)和E(G)。 E中每条边ei都有V中的一对节点(u, v)与之对应。V和E中元素个数分别称为网络的阶(Order)和规模(Size) 。定义2.2对于网络(V,E)，如果任意(u, v)和(v, u)对应于同一条边，则称网络为无向网络(Undirected network)，否则称为有向网络(Directed network)。定义2.3对于网络(V, E)，如果任意的边ei=1，则称网络为无权网络 (Unweighed network)，否则称为加权网络(Weighted network)。定义2.4网络中边所连接的节点称为端点，两端点相同的边称为环(Loop)。有公共起点且有公共终点的两条边称为平行边(Parallel edges)或重边(Multiple edges)。无环且无重边的图称为简单图(Simple graph)，有环或者重边的图称为多重图(Multigraph)。定义2.5每对节点之间都恰好连有一条边的简单图称为完全图(Complete graph)。 N个节点的完全图有N (N1)/2条边，所有完全图都是它本身的集团(Clique)。定义2.6设G=(V,E)是一个无向图，若节点集V可以分割成两个互不相交的子集(VA,VB )，且图中的每条边(i,j)所关联的两个节点vi和vj分别属于这两个不同的节点集，则称图G为一个二分图(Bipartition graph)。网络通常用邻接矩阵来表示。它用两个数组分别存储数据元素(节点)的信息和数据元素之间的关系(边)的信息。定义2.7阶为N的图G邻接矩阵表示为A=（aij）NxN。将G的节点标记为V1, V2, VN。对无权网络，若(Vi, Vj) E(G)，则aij=1，否则aij= 0。无向网络的邻接矩阵是对称矩阵。2.1.2度和度分布定义2.8一个节点的度(Degree)是指与该节点相关联的总边数，节点v的度记作d(v)。度和边有如下关系： =2E （）有向图的节点的度可分出度(Outdegree)和入度(Indegree)。一个节点的出度为d0，是指d0条边以该节点为起点，或者说与该点关联的出边共有d0条。一个节点的入度为di，是指di条边以该节点为终点，或者说与该点关联的入边共有di条。度分布(Degree distribution)是用来表示网络中节点度的分布函数，一般用P(k)表示。下面列出文献中经常用到的几个度分布的定义。定义2.9在时刻t从网络中随机选择一个节点，记此节点度数恰好为k的概率是P(k, t)，称为t时刻网络的瞬时度分布。当网络规模足够大时，若极限存在，则P(k)称为网络的稳态度分布。定义2.10令Nk(t)表示在t时刻网络中度数为k的节点个数，即网络中出现具有度数为k的节点的频数，称Nk(t)t为t时刻网络的瞬时频率。当网络规模足够大时，若极限存在，则P(k)称为网络的稳态度分布。定义2.11设P(k,i, t)表示i时刻加入网络的节点vi在时刻t具有度数k的概率，称平均概率为时刻t网络的平均度分布。当网络规模足够大时，若极限存在，则P(k)称为网络的稳态度分布。常见的网络度分布有单点分布、泊松分布和幂率分布。完全规则网络的所有节点具有相同的度数k，所以其度分布为单点分布，可看作连续Delta分布。对于完全随机网络和小世界网络，大多数节点的度大致相同，度分布近似为泊松(Poisson)分布。在平均度数处，曲线有一个峰值，偏离峰值的两边衰减都很快。由于大多数节点的度都集中在平均度数附近，这两类网络又称为均匀网络或同质网络(Homogeneous network)。无标度网络的度分布不是像随机网络和小世界网络那样对称的泊松分布，而是偏倚的幂率分布(Power law)。度分布曲线没有峰值，且P(k)随度数k衰减。大多数节点仅有少量连线，而少数节点拥有大量连线，具有无标度(Scalefree)特征。由于节点的异质性，此类网络又称为非均匀网络或异质网络(Inhomogeneous network)。图1两种不同类型的度分布图。左图是Poisson分布，右图幂律分布。2.1.3节点度的相关性由于复杂网络的演化依赖于前一步各节点的度数，网络中新旧节点之间的度数存在着明显的相互关系，因此引入度的相关性来描述不同节点之间的连接关系。如果度数大的节点倾向于连接度数大的节点，称网络为正相关或同类匹配(Assortative)的，反之，称网络为负相关或非同类匹配(Dissortative)的。定义2.12为了衡量网络中相邻节点对的相关性，Dorogovtsev和Mendes定义瞬时联合度分布为：（）如果极限则P (k, l)称为网络稳态联合度分布。两节点度的相关性还可以通过条件概率P(kk)来表述，P(kk)指的是度数为k的节点连接到度数为k的节点概率。对于不相关网络，。一般情况下，P(kk)的估计比较困难，PastorSatorras等引入邻居节点的平均度来计算两节点的度相关性。他们定义度为k的节点的邻居平均度为：（）明确描述了网络中两个节点度的相关性，当为k的增函数时，网络是同类匹配的，反之，则是非同类匹配的。定义为时刻t节点的邻居度数之和，记为，则（）类似的，三节点度的相关性可以用P(k, kk)描述，表示度数为k的节点同时连接到度数为k和k的节点的概率。由于度为k的节点的平均群集系数均可以看成是度数为k的节点同时连接到度数为k和k的两个节点，且两个节点之间存在连线的概率，即（）通过计算邻居节点之间的连线数，便可得到三节点度的相关性。2.1.4群集系数在网络的理论和实证研究中都备受关注的另一个参数是群集系数。它描述的是节点之间聚集(Cluster)的程度。在现实网络，尤其是在人际关系网络中，节点倾向于通过节点间的较大的相互作用聚集成一个个的小团体。例如，在同一个单位工作的人，住同一个小区的人，都表现出很高的群集性。社会学中流行的“三倍传递比”(Fraction of transitive triples)正式用来反映一个人的朋友中彼此之间很可能也是朋友的事实。定义2.13考虑节点的群集系数，若其度数为k，则它的邻域，即与节点有连线的相邻节点全体，最多有k(k1)/2条连线。如果它的邻域中实际存在的连线数为E(i)，则节点的群集系数(Clustering coefficient)定义为：（）其中N为网络的阶。网络的群集系数定义为所有节点群集系数的算术平均值，即 （）2.1.5平均路径长度平均路径长度是用来描述网络信息或物质传递效率的度量，指的是网络中所有节点对之间的平均最短距离。它与度分布、聚集系数是网络拓扑结构的三个最有力的测度。社会心理学家Milgram曾经做过一个实验：“追踪美国社交网络中的最短路径”。他要求每个参与者设法寄信给一个住在波士顿附近的目标任务，规定每个参与者只能转发给一个他们认识的人。Milgram发现完整的链平均长度为6个人。也就是说生活在这个世界上的每个人只需要很少的中间人(平均6个)就可以和全世界的任何一个人建立起联系。这就是著名的“六度分离”，它实际上反映了尽管社会系统网络人际关系及其庞大而复杂，但平均路径长度是相对短的。 定义2.14网络中连接两个节点和之间的最短路径上的边数，称为两个节点和之间的距离(Distance)，记为。定义2.15网络中任意两个节点之间距离的最大值，称为网络的直径(Diameter)，记为D，即（）定义2.16网络中任意两个节点之间的距离的平均值，称为平均路径长度(Average path length)，记为L。假设当i =j时，则它可以表示为 （）2.1.6其它参数除了前述的几个重要特征之外，网络还有很多其它的特征参数，如介数、最大连通子图、簇度相关性、模块性等。介数(Betweenness)包括节点介数和边介数，指的是网络中通过某个节点或者某条边的最短路径的数目，反映了节点或者边的重要程度。最大连通子图(Giant component)就是图的所有结点用最少的边将其连接起来的子图。它是网络在受到持续攻击时，测量网络功能的一个重要的量。簇度相关性( Clusteringdegree correlations)用来描述群集系数C(k)和度数k之间的关系。许多现实网络的群集系数C(k)和度数k之间为倒数关系，这种倒数关系的簇度相关性称为层次性(Hierarchy)。模块性(Modularity)指的是许多现实网络中存在的模块结构。这些模块常用局域世界(Local world)、团体(Community)等描述。模块内部的节点之间连线非常多，模块与模块之间却只有少量的连接。2.2复杂网络的基本模型网络的发展有三大里程碑，分别提出了三个经典的理论模型：欧拉图论、ER随机图、小世界模型和无标度模型。下面分别对具有不同拓扑特征的有代表性的网络模型作简单介绍。 2.2.1规则网络模型节点按确定的规则连线的网络称为规则网络(Regular networks)。例如一维链、二维平面的欧几里德格网、近邻环网。将节点排成一条直线，每个节点都与它最近邻的K个节点连线，就构成一维无限规则网。将节点排列在二维平面的欧几里德网格上，每个节点只与它近邻的节点连线，就得到二维无限规则网。将节点排成一个圈，让它们首尾相连，且每个节点都与它近邻的有限个节点连线，构成近邻环网。规则网络是确定性的，每个节点都有相同的度，为单点分布。每个节点的群集系数也相同，而且较高，平均路径长度较大，与网络规模呈线性比例关系。2.2.2随机网络模型在20世纪五六十年代，两个著名的匈牙利数学家Erdos和Renyi建立了随机图理论(Random graph theory)，用相对简单的随机图来描述网络。随机网络模型有下面两种描述方式。随机网络SR模型：给定固定不变的网络节点总数N，网络中任意两个节点以概率p连线，生成的网络记为。网络中边的数目是一个随机变量，可以在0到N (N1)/2之间变化，其期望值为pN (N1)/2。有n条连线的网络数目为，得到某一个特定网络的概率是。因此，可生成的不同网络数服从二项分布，为。随机网络ER模型：给定固定不变的网络节点总数N，随机连接节点之间的n条边形成的网络，记为。这样由N个节点和n条边生成的不同网络总数为)，构成一个概率空间，且每种网络以相同的概率出现，服从均匀分布。当n=pN(N1)2时，上面两个模型和是等价的。随机网络模型的连线不像规则网络一样确定，使得它的度分布不再是单点分布。事实上，当网络节点总数N较大时，随机网络的度分布可以近似为泊松分布。此外，随机网络由于随机连线，使得平均路径短，但群集系数较小。2.2.3小世界网络模型分析了规则网络和随机网络的拓扑特征后，Watts和Strogatz4发现现实网络不可能是这两种极端之一，于是提出了能在规则网络和随机网络之间任意变化的小世界网络模型。小世界网络WS模型的描述如下： (1)初始：给定一个具有N个节点的环，环上每个节点都与它最近邻的K个节点相连线，构成近邻环网。 (2)重连：以概率p对每条边进行随机重连，方法是将选择的连线的一个端点随机的连接到另一个节点上，不允许自连和重连。小世界网络模型是规则网络和随机网络之间的过渡。当p=0时，网络仍为初始规则网，当p=1时，网络变为完全随机网络。由于随机重连，被改写的连线会使得相距较远的节点相互连接，形成捷径。因此，小世界网络的平均路径长度短，而群集系数仍然较大。图2小世界网络拓扑结构示意图WS模型由于边的重连，可能引起孤立团体的出现，因此Newman和Watts提出了改进的小世界网络模型，称为小世界网络NW模型，描述如下： (1)初始：给定一个具有N个节点的环，环上每个节点都与它最近邻的K个节点相连线，构成近邻环网。 (2)增加：不改变规则网的原有连线，以概率pK2在任意两个节点之间新增连线，不允许自连和重连。NW模型实际上是WS模型的一种变体，对于足够小的p和较大的N，两个模型是基本等价的。和WS模型一样，NW模型也具有较大的群集系数和较短的平均路径，它们表现出来的这种现象就是小世界现象，研究表明，许多现实网络都具有这种小世界效应。小世界网络模型由于改写或增加规则网络的连线，使得每个节点的度数不再是常数。但其度分布与随机图度分布形态类似，仍可看成泊松分布，在平均度数处，有一个峰值，偏离峰值的两边都很快衰减。图3WS小世界模型的聚类系数和平均路径长度随重连概率p的变化关系(两组数据均作了归一化处理)2.2.4无标度网络模型小世界网络WS模型和NW模型是按随机方式改写和增加连线的，而且网络的节点总数是固定不变的。Albert等通过研究万维网发现，万维网的度分布不是钟型的泊松分布，而是长尾幂率分布。而且对现实网络的分析表明，网络节点总数是不断变化的，是一个动态的演化的过程。节点之间连线也不是完全无规则或随机的，而是依赖于节点已有的连线数。为此，他们提出了著名的BA模型，描述如下： (1)增长：开始时给定个节点，每个时间步增加一个带有m(m<)条边的新节点。 (2)择优：新节点按照择优概率，选择旧节点认与之连线，不允许自连和重连，其中是旧节点的度数。此模型具有度指数为3的幂率分布。因为节点的异质性，特征标度消失，因此BA模型又叫无标度网络模型(Scalefree network)。BA模型指出了现实网络的两个重要演化机理：增长和择优。他们通过构造两个模型：模型A节点数不断增长改为固定不变，模型B择优连线改为随机连线，指出了增长和择优是生成无标度网络的不可或缺的条件。BA模型平均路径长度很小，群集系数也很小，但比同规模的随机图的群集系数大。当网络规模较大时，随机图和BA模型的群集系数都近似趋于0。2.2.5其它网络模型继BA模型提出之后，掀起了研究复杂网络的热潮。学者们纷纷对BA模型进行研究，并对其进行扩展，提出了很多基于BA模型的演化网络模型。Krapivsky等将BA模型的线性择优扩展为非线性情形，节点被选择的概率改写为)，=1便退化成BA模型。Dorogovtsev等引入吸引度的概念，将BA模型的择优改写为 。BA模型即吸引度模型a=0的特殊情形。Bollobas认为BA模型的初始状态和m>1的择优规则表达不明确，给出了一个严格的修正模型。该模型改变了已有的BA模型，把自连和重连也考虑在内，主要算法如下：首先考虑每步增加边数m= 1的情况。对于固定的节点序列, ,定义一个随机图过程，使得为上的有向图。(1)增长：网络初始为没有任何节点的图或者具有一个节点及一个自连环的图。每个时间步，给定图以，为了生成图，增加一个新节点及一条从到的有向边。(2)择优：a被选择的概率为P，其中为图中旧节点的度数。此概率说明了新节点选择旧节点连线时是根据度数择优的，而且允许自连和重连。当m> 1时，则每次从引出一条连线，直至m条连线都成功连接。类似的，可以通过序列,上的过程来定义过程。将的节点,合成为,合成为，依此类推，则生成图。此外，Biancom和Barabasi提出了适应度模型, Cooper和Frieze讨论了一个包含加点加边、旧节点间连线、删除旧连线等多种情况的综合模型。考虑现实网络的局域世界特征，李翔和陈关荣研究了基于局域世界择优的网络模型。此外，还有集团网络模型，阿波罗网络和二分网络等。3复杂网络的同步复杂非线性动态网络的特点之一就是，不仅网络中节点具有非线性和复杂性，而且网络的连接结构和时空演化更是错综复杂，其中，复杂动态网络系统在时空演化过程中出现的同步行为及其控制方法研究是近年来受到关注的一类课题。早期大多数对于大型动态网络同步工作的研究是假设网络具有完全规则的连接结构。尽管已有研究结果表明，当网络耦合强度足够大时，网络的节点之间会产生同步化行为，但这并不能解释为什么即使在耦合强度相当弱时，一些实际的复杂网络仍会产生同步。随着复杂网络的小世界效应和无标度特性的发现，探索具有复杂拓扑结构的动态网络同步化行为成为当前研究复杂网络同步化特性的一个重点课题，下面简单介绍有关复杂网络同步问题的研究概况，以及经典网络模型的同步分析。3.1复杂网络同步研究进展概述网络节点间的同步化行为是复杂动态网络一个非常重要的性质。物理学家惠更斯早在1665年就惊讶地发现，悬挂在同一横梁上的两个钟摆经过一段时间以后会出现同步摆动的现象。在现实生活中，同步现象随处可见。比如，停在同一棵树上的萤火虫同时闪光又同时不闪光;当精彩演出结束后，观众的掌声起初是凌乱的，但经过几秒之后，大家会用共同的节奏鼓掌;近期发表在Nature杂志上的文章指出，纳米耦合振子之间也会发生同步行为，这有可能用于研制新的无线通信元件。当然，同步现象有时也可能是有害的，例如成千上万的人们同时过桥引起桥体振动；Internet上路由器周期性发送路由信息引发网络通信堵塞。假定一个网络中所有个体的状态都是周期变化的，例如从发光到不发光，那么看似巧合的同步现象可以用数学语言来描述。其中，每个个体是一个动力学系统，而诸多的动力学个体之间存在着某种特定的耦合关系。实际上，在物理学、数学和理论生物学等领域，耦合动力学系统中的同步现象已经研究了很多年。控制论的奠基者Wiener就曾分析过同步化现象，而生物学家Winfree则是被公认为同步问题研究的一位开拓者. Winfree15假设每个节点只与它周围有限个节点之间存在强力作用，这样振子的幅值变化可以忽略，从而将同步问题简化成研究相位变化的问题。在此基础上，日本学者Kuramoto13，15，23做了重要的简化:一个具有有限个恒等振子的耦合系统，无论系统内部各个振子之间的耦合强度多么微弱，它的动力学特性都可以由一个简单的相位方程来表示。此后，Kuramoto模型成为了研究网络系统相位同步的经典标准模型。但20世纪的工作大多集中在具有规则拓扑形状的网络结构上，其中的两个典型例子是耦合映象格子(CML)和细胞神经网络(CNN)。研究这些结构比较简单的网络，可以使得人们将研究重点放在网络节点的非线性动力学所产生的复杂行为上，而暂时不去考虑网络结构复杂性对网络行为的影响。进入21世纪以来，人们开始关注具有小世界和无标度等网络拓扑特性的复杂网络相位同步问题。网络中形成的同步簇中节点个数占整个网络节点数的比例反映了网络相位同步的程度。人们通过对小世界模型的相位同步研究发现，随着网络中长程边的增多，开始出现同步簇，并且簇中的节点逐渐增多，最终所有节点形成一个同步簇，相位同步出现饱和态，整个网络达到相位同步。无标度网络模型发生相位同步时，首先是度大的节点与周围相邻节点发生相位锁定，如果度大的节点受到干扰不同步后，它的相邻节点会“帮助”它返回到同步状态。随耦合强度的不断增大，最终网络形成一个同步簇。此外，网络模体以及离散时间、非对称耦合网络的相位同步也受到了人们的关注。相位同步是一种同步化程度比较弱的同步现象，主要研究具有不同固有频率的振子之间相位锁定的问题。发生相位同步时，各节点的相位可能已经锁定，但幅值完全不同。还有一类被广泛研究的同步问题:完全同步。发生完全同步时，网络中各个节点的状态达到完全一致。目前研究完全同步问题一般假设网络中所有节点的动力学系统完全相同。人们在已有针对小规模规则网络同步研究的基础上，分析研究了具有复杂拓扑结构网络的同步化行为，发现诸多相同节点构成的连续时间耗散耦合动态网络的同步性能由节点的动力学函数以及节点之间的内部耦合函数决定。如果内部耦合函数是线性函数，则网络同步的稳定性由节点动力学函数、内部耦合矩阵、耦合强度以及网络的耦合矩阵决定。在此基础上，人们进一步研究了具有时变、时滞的一般复杂网络的同步。大量研究结果表明，复杂网络的拓扑结构与网络的同步特性之间有着密切的联系。人们在研究已有网络模型同步化性能的同时也开始分析网络拓扑结构特性对同步的影响，寻求有效的控制策略和演化机制来提高网络的同步化性能。3.2经典网络模型的同步分析3.