复杂网络的同步1210课件

复杂网络的同步2010-12-11一、同步现象举例1665年，物理学家惠更斯发现：并排挂在墙上的两个钟摆不管从什么不同的初始位置出发，经过一段时间以后会出现同步摆动的现象。1680年，荷兰旅行家肯普弗在泰国旅行时观察到了一个奇特的现象：停在同一棵树上的萤火虫有时候同时闪光又同时不闪光，很有规律而且在时间上很准确。

这两个例子表现的就是现实世界中的同步现象。

当一场精彩的戏剧演出结束时，人们的掌声从三三两两，到大家都按着共同的节奏鼓掌。

在我们的心脏中，无数的心脏细胞同步震荡着，他们同时做着一个动作，使心瓣膜舒张开，然后又一下子同时停下来，心瓣膜就收缩了。

同步在激光系统、超导材料和通信系统等领域中起着重要的作用。有些同步时有害的。如：2000年伦敦千年桥落成，当成千上万的人们开始通过大桥时，共振使大桥开始振动。桥体的S形振动所引起的偏差甚至达到了20cm，使得桥上的人们开始恐慌，大桥不得不临时关闭。

Internet上也有一些对网络性能不利的同步想象。如：Internet网上的每个路由器都要周期性地发布路由消息。尽管每个路由器都是自己决定它什么时候发布路由信息，但是研究人员发现不同的路由器最终会以同步的方式发送路由消息，从而引发网络交通阻塞。

然而网络的拓扑结构在决定网络动态特征方面起到很重要的作用。例如，WuCW的结果表明：在一定条件下，足够强的耦合可以导致网络中节点间的同步现象。缺点：无法解释弱耦合情况下，许多复杂网络仍出现较强的同步现象。各种复杂网络共有的小世界和无标度特性的发现，使得人们开始关注网络的拓扑结构与网络同步化行为之间的关系。二、同步的基本概念(精确)同步：两个或多个动力学系统，除了自身的演化外，其间还有相互作用（耦合），这种作用既可以是单向的，也可以是双向的。当满足一定条件时，在耦合的影响下，这些系统的状态输出就会逐渐趋同进而完全相等，称为同步（精确同步）。广义的同步还包括相同步和频率同步等等。复杂系统中的同步主要有两大类：完全同步和广义同步，前者两个相同单元研究得比较多，两个不同单元研究得比较少；后者包括部分同步，如相同步、滞后同步、频率同步等。两个不同单元的同步研究更具挑战性，是今后一个重要研究方向。7三、复杂网络的完全同步判据1.数学描述

首先介绍一般连续时间耦合网络的完全同步问题。设连续时间耗散耦合动态网络中有个相同的节点，其中第个节点的状态变量为：单个节点满足的状态方程是：多个节点的耦合动态网络中，的状态方程是：

（1）其中：是定义好的函数（通常是非线性的）常数为网络的耦合强度；

2.同步的判定

对状态方程（1），关于同步状态做线性化，令为第个节点状态向量的变分，则可以得到变分方程：

（4）这里，和分别是和关于的Jacobi矩阵，通常要求为无界。令：则上式可以写成矩阵方程：

（5）做分解,其中，而是矩阵的特征根且。令，则有：(6)判断同步流形稳定的一个常用判据是要求方程（6）的横截lyapunov指数全为负值。在方程（6）中，只有和与相关，并考虑到外耦合矩阵A为非对称阵时，其特征值可能为复数，故定义主稳定方程为：其最大lyapunov指数是变量和的函数，称为动力网络的主稳定函数。给定一个耦合强度对于每一个固定的在复平面上可以对应地找到固定的一点，该点所对应的正负号反应了该特征模态的稳定性（负时稳定，正时不稳定）。如果与对应的所有特征模态都稳定，那么就认为在该耦合强度下整个网络的同步流形是渐进稳定的。3.网络分类根据同步化区域可以把连续时间复杂动态网络（1）分为以下几种类型：1）类型Ⅰ网络对应的同步化区域为，其中。若网络耦合强度和外耦合矩阵的特征值满足，即满足同步判据Ⅰ：那么类型Ⅰ网络的同步流形是渐进稳定的。因此，类型Ⅰ网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵的第二大特征值来刻画：值越小，其同步化能力越强。2）类型Ⅱ网络

对应的同步化网络区域，其中

。若网络耦合强度和耦合矩阵的特征值满足和，即满足同步判据条件Ⅱ：

或者

那么，类型Ⅱ网络的同步流形是渐进稳定的。因此，类型Ⅱ网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵

的特征值的比率

来刻画：

值越小，其同步化能力越强。3）类型Ⅲ网络

对应的同步化区域为。对于任意的耦合强度和外耦合矩阵，这类网络都无法实现同步。注意：一个给定的复杂动态网络(1)属于上述三种类型中的哪一种是由该网络的孤立节点的动力学函数和网络的内外耦合函数和确定的。尽管同步判据Ⅰ和Ⅱ之间的精确关系目前还不十分清楚，但是它们并不矛盾。此外，假设网络是连通的，那么只要网络的耦合强度充分大，类型Ⅰ网络是一定可以实现同步的；而只有当耦合强度属于一定范围内时类型Ⅱ网络才能实现同步，也就是说，太弱或太强个耦合强度都会使类型Ⅱ网络无法实现同步。这里，同步判据Ⅰ和Ⅱ的值一般可以通过数值计算来估计。②全局耦合网络全局耦合网络对应的耦合矩阵为：

它除了零特征根外，其余的特征根均。因此，当网络的规模

时，单调下降趋于无穷，说明网络很容易达到同步。

③星形网络

星形网络对应的耦合矩阵是：

它的第二大特征根为：

，与网络的规模无

关，故同步化能力与网

络规模无关。对于连续时间耗散耦合的类型Ⅰ动态网络式(1)，可以得到一下结论：(1)对给定的耦合强度，不管它有多大，当网络规模充分大时，最近邻耦合网络无法达到同步。(2)对给定的非零耦合强度，不管它有多小，只要网络规模充分大，全局耦合网络必然可以达到同步。(3)星形耦合网络的同步能力与网络的规模无关，即当耦合强度大于一个与网络规模无关的临界值时，星形网络可以实现同步。②全局耦合网络全局耦合网络对应的外耦合矩阵的最小特征值和第二大特征值均为。因此，由前面关于类型Ⅰ网络的描述可知，只要，该网络就可以到达同步。③星形耦合网络星形耦合网路对应的外耦合矩阵的最小特征值和第二大特征值之比为。因此，当网络规模时，此比值也趋于无穷，该网络无法达到同步。由以上分析，对连续时间耗散耦合的类型网络Ⅱ动态网络(1)，可以得到以下结论：(1)对给定的耦合强度，不管它有多大，当网络规模充分大时，最近邻耦合网络和星形网络都无法达到同步。(2)全局耦合网络的同步化能力与网络规模无关，只要，全局耦合网络就可以达到同步。2.小世界网络的完全同步只针对类型Ⅰ网络讨论。考虑具有NW小世界拓扑结构的连续时间耦合动态网络系统式(1)的同步化能力。NW小世界网络的生成规则：①初始：最近邻耦合网络②随机化加边：以概率在随机选取的一对节点之间加上一条边即：这种以概率

加边过程就相当于在最近邻耦合矩阵中的0元素，以概率

置换为1，因此将最近邻耦合矩阵中的的元素，以概率置换为重新计算其对角线元素，这样得到NW小世界网络的耦合矩阵，记为：令是对应的第二大特征根

左图分别给出和的情

形下,具有不同规模的NW小世界网络

模型对应的第二大特征根。①对于规模较小最近邻网络,

近似为0，此时网络的同步

化能力很低。

②在此基础上不断地增加规模，

不断变小，同步化能力不断加强。结论2：在加边概率相同的情况下，规模越大的NW小世界网络的同步化能力越强。22p=0.05p=0.13.无标度网络的完全同步1）无标度网络的完全同步考虑BA无标度拓扑的连续时间耦合动态网络式(1)的同步化能力。这里同样只讨论类型Ⅰ网络。BA无标度网络的生成规则：a.增长：从一个具有个节点的网络开始，每次引入一个新的节点，并且连到

个已存在的节点上，b.优先连接：一个新节点与一个已经存在节点

相连接的概率与节点

的度、节点的度之间满足如下关系：

同步最优网络模型的生成规则如下：①增长：从一个具有

个节点的网络开始，每次引入一个新的节点，并将其连接到个已存在的节点上。②同步最优连接：新节点与已存在的节点

相连接时，要使得构成的新网络的同步化性能最优，即要使得新网络耦合矩阵的第二大特征根最小。这样，经过

步后，产生一个具有个节点，

条边的同步网络。这个网络在其生长过程中，每一步都达到同步化性能最优。同步最优网络模型分析：优点：与BA无标度网络相比，同步最优网络模型的第二大特征根有显著的下降，即：同步化性能有了明显的提高。如：当时，对应有：缺点：分析同步最优网络的节点度分布时还发现，同步最优网络的拓扑结构类似于多中心网络模型：有极少量的节点与大量节点连接，而大部分节点的连接度很小。这使得虽然同步最优网络的同步化性能要比BA无标度网络的同步化性能强，但由于存在极少量的“集散”点（远小于BA无标度网络中的“集散”点的个数），这样，在恶意攻击下它要比BA无标度网络更容易崩溃，对抗恶意攻击更为脆弱。3)同步优先网络虽然同步最优网络模型的同步化能力有了很大提高，但是对于恶意攻击非常脆弱。一种改进的模型是对于随机去节点和恶意攻击都很鲁棒的同步优先网络模型,基于增长和同步优先两种机制生成。同步优先网络的生成规则如下：①增长：初始时有

个节点，在每一时间步内加入一个新的节点,并将其连接到个已存在的节点上；②同步优先连接：新节点与原有节点

相连的概率

和新节点与第

个节点连接后构成的新网络同步化能力有关.即：

这样，经过步后，产生一个具有个节点，

条边的同步优先网络模型。对于特定的值，当趋于无穷时，网络的第二大特征值也趋于一个负常数。例如：当时，对应的三种网络同步化能力的比较：①

无标度网络与同步优先网络的同步化能力非常类似，后者稍逊色于前者。②同步最优网络的同步化能力最强。4)无标度网络的鲁棒性和脆弱性

当网络发生随机故障时，相当于从网络中随机去除部分节点，由于无标度网络的极度不均匀性，此时去除的节点大多数都是度很小的节点。因此，，网络的同步化能力基本上保持不变。当网络受到恶意攻击时，这时被特定去掉的那一部分都是度很大的节点。因此，整个网络的连通性发生了剧烈变化，甚至于网络被分成若干不连通的分支，并且，从而，网络的同步化能力大大地降低甚至丧失了。4、局域世界演化网络模型的完全同步

局域世界演化模型的生成规则：①增长：网络初始时有个节点和条边，每次加入一个节点和附带的条边。②局域世界有线连接：随即的从网络已有的节点中选取个节点(),作为新加入的节点的局域世界。新加入的节点根据优先连接概率：来选择局域世界中的m各节点相连，其中LW是由新选的M个节点组成。对于每一个新加入的节点，它的局域世界都是随机的从网络中挑选构成，其连接度决定了网络的非均匀性，并且度分布在指数和幂律之间的过渡。因此，在这种局域世界演化网络中，Hub节点的数目通常要比无标度网络的少，因而度分布也要比无标度网络更均匀。因此，当面对随机故障的和恶意攻击时，局域世界演化网络的同步鲁棒性和脆弱性也就介于无标度网络和指数网络之间。

一般来说，与无标度网络相比，局域世界演化网络能够在保持鲁棒性的同时，提高网络对恶意攻击的抗脆弱性。五、复杂网络中各因子与完全

同步的关系由前面的分析指导最近邻耦合网络在时不可能达到同步，但是通过加入少量的长程边将网络的平均路径明显缩短，太的同步化能力便会有明显提高。问题：是不是由于平均路径的缩短提高了复杂网络的同步化能力呢？复杂网络中其他结构特性对网络的同步起到了什么作用？究竟是哪些网络基本参数对于提高网络同步化能力起到了关键性作用？。

复杂动态网络有许多基本参数，如特征根及其比率，平均路径长度，节点度及其分布、介数和同类匹配系数等，它们对各种网络的同步化能力都有不同程度的影响。这里主要介绍它们对小世界网络和无标度网路同步化能力的影响。

这里只考虑类型Ⅱ连续时间动态网络。由类型Ⅱ网络的同步判据可知：值越大，网络的同步化能力越差。1.连接概率()和幂律指数()1）和对同步化性能的影响对于小世界网络，当加边或重连概率不断变化时，对应地会产生多个具有不同基本特性的小世界模型；同样，对于无标度网络，当幂律指数不断变化时，也会得到多个不同的无标度网络模型。下面我们就研究由这两个参数和不断变化而产生的不同网络模型，它们的同步化性能与网络基本特性之间的关系。

①小世界网络就小世界网络而言，由前面分析小世界网络的同步化稳定性可以知道，随着网络进行“小世界”的操作(不断的加入长城边或不断重新连边)，网络的特征根比率会随之减少，即随着加边或重连概率的增加，

随之减少。如图：这说明小世界网络的同步化能

力随着“小世界”操作（概率p

增加）而增强。N=2000，100实验的平均值。特征根比率随连接概率p的变化曲线N/2②无标度网络对于度分布为幂律形式

的无标度网络，通过研究具有不同值的无标度网络的同步化性能时发现，值越大的网络，其越小。

说明幂律指数越大对应

的无标度网络的同步化能

力越强。2)和对于网络中各基本参数指标的影响

下面分析网络中各基本特性指标随着和的变化情况，从而进一步得到网络性能指标对同步化性能的影响。①小世界网络小世界网络模型的一个显

著特点是当加边或重连概

率很小时，网络的平均路径长度有大幅度的下降当时，平均路径长度的变化不是很显著。

但是随着的增加，小世

界网络的平均路径会减少。

虽然相对于具有幂律度分布的无标度网络来说，小世界网络是均匀的，但是其网络中各节点所连接的边数并不是完全相等的。因此，用方差指标：来表示节点度的分布，则值越大说明网络中节点度分布范围越大，并有度较大的节点出现，这时网络的度分布变的均匀。由上图的曲线可以看出随着概率的增加，网络变的更加非均匀；同时无论是新加入的长程边（NW小世界）或是重新连接长程边（WS小世界），网络中度的最大值都会增加。②无标度网络对于具有幂律分布的无标度网络模型，用节点的标准偏差来衡量网络的非均匀性，则值越大反而下降，说明网络中节点度的分布越均匀。在无标度网络中，少数具有度非常大的节点将大量的度很小的节点连接在一起，因此这些度大的节点使得网络的平均路径很短。而随着值的增大网络度分布变的比较均匀，因此网络的平均路径就会增加，同时平均度变小。

无标度网络的平均路径D随变化的曲线小图是网络平均度k随变化的曲线总结：由上述对小世界网络和无标度网络的分析可以看到，小世界网络在最近邻耦合网络的基础上通过“小世界操作”，使得网络的平均路径长度减小，同时也增加了网络节点的度分布的非均匀性以及最大的度，从而同步化能力有了显著提高；而对于无标度网络却有了相反的结论，即只有提高网络的均匀性，增大平均路径长度或减小网络的平均度，才能使得无标度网络的同步化性能提高。因此，单纯用度的大小、度分布、或平均路径长度等指标都无法统一表征复杂网络的同步化能力。2.介数某个节点的介数越大说明在信息传播过程中的信息量也会越多，于是也就越容易发生信息堵塞。研究发现，无论是小世界网络还是无标度网络，节点的最大介数值都会随着概率和参数的增加而减小。这说明，介数是一个相对能够统一反映网络同步化能力的参数。

最大介数Bmax随连接概率p的变化图

假设在两组高度连接的子网络之间只有少数的节点相连，那么这几个少数节点的介数就会很大，会有过多的信息经过这几个节点而造成过载从而丢失信息。因此最大介数值变化会降低网络的同步化能力。

为了进一步验证这一结论，现在将小世界网络模型中具有最大介数的节点去掉。这样原本大量从该节点经过的同步流形信息会分散到其他的节点上。用参数：来表示去除节点前后网络同步化性能的变化。仿真实验表明：无论为何值的小世界网络，当具有的节点被去掉以后，特征根比率均会下降(),从而网络的同步化性能显著提高；相反，如果随机去除一个节点，特征根的比率前后没有很大变化，说明介数不大的节点对整个网络同步化性能的影响不是很大。3.影响网络同步化能力的其他因素(1)节点的度分布、平均路径长度以及同类匹配系数这类指标的变化会对小世界网络和无标度网络的同步化性能造成不同的影响，其中具体的原因仍需进一步探讨。(2)网络的社团结构和同型混合等特征也都可能会影响网络的同步化能力。因此，如何进