复杂网络的同步1210课件.ppt

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

2、律而且在时间上很准确。很有规律而且在时间上很准确。这两个例子表现的就是现实这两个例子表现的就是现实世界中的同步现象。世界中的同步现象。当一场精彩的戏剧演出结束时，人们的掌声从三三两两，当一场精彩的戏剧演出结束时，人们的掌声从三三两两，到大家都按着共同的节奏鼓掌。到大家都按着共同的节奏鼓掌。在我们的心脏中，无数的心脏细胞同步震荡着，他们同在我们的心脏中，无数的心脏细胞同步震荡着，他们同时做着一个动作，使心瓣膜舒张开，然后又一下子同时停时做着一个动作，使心瓣膜舒张开，然后又一下子同时停下来，心瓣膜就收缩了。下来，心瓣膜就收缩了。同步在激光系统、超导材料和通信系统等领域中起着重同步在激光系统、超导材

3、料和通信系统等领域中起着重要的作用。要的作用。有些同步时有害的。有些同步时有害的。如：如：20002000年伦敦千年桥落成，当成千年伦敦千年桥落成，当成千上万的人们开始通过大桥时，共振使大桥开始振动。桥体上万的人们开始通过大桥时，共振使大桥开始振动。桥体的的S S形振动所引起的偏差甚至达到了形振动所引起的偏差甚至达到了20cm20cm，使得桥上的人们，使得桥上的人们开始恐慌，大桥不得不临时关闭。开始恐慌，大桥不得不临时关闭。Internet上也有一些对网络性能不利的同步想象。如：上也有一些对网络性能不利的同步想象。如：Internet网上的每个路由器都要周期性地发布路由消息。尽网上的每个路由器

4、都要周期性地发布路由消息。尽管每个路由器都是自己决定它什么时候发布路由信息，但管每个路由器都是自己决定它什么时候发布路由信息，但是研究人员发现不同的路由器最终会以同步的方式发送路是研究人员发现不同的路由器最终会以同步的方式发送路由消息，从而引发网络交通阻塞。由消息，从而引发网络交通阻塞。实际上，在物理学，数学和理论生物等领域，耦合实际上，在物理学，数学和理论生物等领域，耦合动力学系统中的同步现象已经研究了很多年。动力学系统中的同步现象已经研究了很多年。（19671967年，年，WinfreeWinfree开创性的工作）假设每个振子只开创性的工作）假设每个振子只与它周围有限个振子之间存在着强力作

5、用（忽略振子与它周围有限个振子之间存在着强力作用（忽略振子的振幅变化），这样将同步问题转化成研究相位变化的振幅变化），这样将同步问题转化成研究相位变化的问题。的问题。Kuramoto认为，一个具有有限个恒等振子的耦合系认为，一个具有有限个恒等振子的耦合系统，无论系统内部各振子间的耦合强度多么微弱，其统，无论系统内部各振子间的耦合强度多么微弱，其动力学特性都可由一个简单的相位方程表示动力学特性都可由一个简单的相位方程表示。20 20世纪，工作大多数集中在具有规则拓扑形状的世纪，工作大多数集中在具有规则拓扑形状的网络结构上，例：耦合映象格子（全耦合或最近邻耦网络结构上，例：耦合映象格子（全耦合或最

6、近邻耦合等）和细胞神经网络等。人们重点研究网络节点的合等）和细胞神经网络等。人们重点研究网络节点的非线性动力学所产生的复杂行为。缺点：没有考虑网非线性动力学所产生的复杂行为。缺点：没有考虑网络结构复杂性对网络动态行为的影响。络结构复杂性对网络动态行为的影响。然而网络的拓扑结构在决定网络动态特征方面起到很然而网络的拓扑结构在决定网络动态特征方面起到很重要的作用。例如重要的作用。例如，Wu C W的结果表明：在一定条件的结果表明：在一定条件下，足够强的耦合可以导致网络中节点间的同步现象。下，足够强的耦合可以导致网络中节点间的同步现象。缺点：无法解释弱耦合情况下，许多复杂网络仍出现较缺点：无法解释弱

7、耦合情况下，许多复杂网络仍出现较强的同步现象。强的同步现象。各种复杂网络共有的小世界和无标度特性的发现，各种复杂网络共有的小世界和无标度特性的发现，使得人们开始关注网络的拓扑结构与网络同步化行为之使得人们开始关注网络的拓扑结构与网络同步化行为之间的关系。间的关系。二、同步的基本概念二、同步的基本概念(精确精确)同步：两个或多个动力学系统，除了自身的演同步：两个或多个动力学系统，除了自身的演化外，其间还有相互作用（耦合），这种作用既可以化外，其间还有相互作用（耦合），这种作用既可以是单向的，也可以是双向的。当满足一定条件时，在是单向的，也可以是双向的。当满足一定条件时，在耦合的影响下，这些系统的

8、状态输出就会逐渐趋同进耦合的影响下，这些系统的状态输出就会逐渐趋同进而完全相等，称为同步（精确同步）。而完全相等，称为同步（精确同步）。广义的同步还包括相同步和频率同步等等。广义的同步还包括相同步和频率同步等等。复杂系统中的同步主要有两大类：完全同步和广义同复杂系统中的同步主要有两大类：完全同步和广义同步，前者两个相同单元研究得比较多，两个不同单元步，前者两个相同单元研究得比较多，两个不同单元研究得比较少；后者包括部分同步，如相同步、滞后研究得比较少；后者包括部分同步，如相同步、滞后同步、频率同步等。两个不同单元的同步研究更具挑同步、频率同步等。两个不同单元的同步研究更具挑战性，是今后一个重要

9、研究方向。战性，是今后一个重要研究方向。7三、复杂网络的完全同步判据三、复杂网络的完全同步判据1.1.数学描述数学描述 首先介绍一般连续时间耦合网络的完全同步问题。首先介绍一般连续时间耦合网络的完全同步问题。设连续时间耗散耦合动态网络中有设连续时间耗散耦合动态网络中有 个相同的节点，个相同的节点，其中第其中第 个节点的状态变量为：个节点的状态变量为：单个节点满足的状态方程是：单个节点满足的状态方程是：多个节点的耦合动态网络中，多个节点的耦合动态网络中，的状态方程是：的状态方程是：（1 1）其中：其中：是定义好的函数（通常是非线性的）常数是定义好的函数（通常是非线性的）常数 为网络的耦合强度；为

10、网络的耦合强度；Ni()ixf xix0c()()1NxfxcaHxiiijjj()f 1 1 节点状态变量之间的内部耦合函数，也称为节点的节点状态变量之间的内部耦合函数，也称为节点的输出函数，这里假设每个节点的输出函数是相同的。输出函数，这里假设每个节点的输出函数是相同的。所谓耗散耦合是指所谓耗散耦合是指耦合矩阵耦合矩阵 满足耗散耦合满足耗散耦合条件条件 。当所有的节点状态都相同时，（。当所有的节点状态都相同时，（1 1）式右）式右端的耦合项自动消失。端的耦合项自动消失。如果在动态网络（如果在动态网络（1 1）中，当）中，当 时有：时有：（2 2）则称网络达到完全（渐进）同步。则称网络达到完

11、全（渐进）同步。这里，这里，称为网络状态空间中的同步流形。称为网络状态空间中的同步流形。当同步实现后，记其结果为：当同步实现后，记其结果为：（3 3）这里这里 称为同步状态。称为同步状态。()H ijnnAa0ijja t12()()()nxtxtxt12()()()()nx txtxts t()st12nxxx2.2.同步的判定同步的判定 对状态方程（对状态方程（1 1），关于同步状态），关于同步状态 做线性化，令做线性化，令 为第为第 个节点状态向量的变分，则可以得到变分方程：个节点状态向量的变分，则可以得到变分方程：（4 4）这里，这里，和和 分别是分别是 和和 关于关于 的的Jacob

12、iJacobi矩矩阵，通常要求为无界。令：阵，通常要求为无界。令：则上式可以则上式可以写成矩阵方程：写成矩阵方程：（5 5）做分解做分解 ,其中其中 ，而，而 是是矩阵矩阵 的特征根且的特征根且 。()s tii1()(),1,2,NiiijijDf sca DsiN()Df s()D s()f s()ss12,N()()TDf scDsA 1TAS S 12(,)Ndiag 1NkkA10令令 ，则有：，则有：(6)(6)判断同步流形稳定的一个常用判据是要求方程（判断同步流形稳定的一个常用判据是要求方程（6 6）的横截的横截lyapunovlyapunov指数指数全为负值。全为负值。在方程（

13、在方程（6 6）中，只有）中，只有 和和 与与 相关，并考虑到相关，并考虑到外耦合矩阵外耦合矩阵A A为非对称阵时，其特征值可能为复数，故为非对称阵时，其特征值可能为复数，故定义主稳定方程为：定义主稳定方程为：其最大其最大lyapunovlyapunov指数指数 是变量是变量 和和 的函数，称为动的函数，称为动力网络的主稳定函数。力网络的主稳定函数。12,NS，()(),1,2,kkkDf sc D skNkkk yDf sci DsymaxL 给定一个耦合强度给定一个耦合强度 对于每一个固定的对于每一个固定的在在 复平面上可以对应地找到固定的一点复平面上可以对应地找到固定的一点 ，该，该点所

14、对应的点所对应的 正负号反应了该特征模态的稳定性正负号反应了该特征模态的稳定性（负时稳定，正时不稳定）。如果与（负时稳定，正时不稳定）。如果与 对应的所有特征模态都稳定，那么就认为在该耦合强对应的所有特征模态都稳定，那么就认为在该耦合强度下整个网络的同步流形是渐进稳定的。度下整个网络的同步流形是渐进稳定的。(1,2,)kkN(,)kcmaxL(1,2,)kkNc 无权无向连通的简单网络的外耦合矩阵无权无向连通的简单网络的外耦合矩阵A A的特征根均的特征根均为实数，不妨排列为为实数，不妨排列为这时其主稳定方程（这时其主稳定方程（6 6）变为）变为并且其对应的主稳定函数并且其对应的主稳定函数 是实

15、参数是实参数 的函数。使的函数。使得主稳定函数得主稳定函数 为负的为负的 的取值范围的取值范围 称为动态网称为动态网络（络（1 1）的同步化区域，主要由孤立节点上的动力学）的同步化区域，主要由孤立节点上的动力学函数函数 ，耦合强度，耦合强度 以及外耦合矩阵以及外耦合矩阵 和内耦合矩阵和内耦合矩阵函数函数 确定。如果耦合强度确定。如果耦合强度 与每个外耦合矩阵与每个外耦合矩阵 的每的每个负值的特征值之积都属于同步化区域，即：个负值的特征值之积都属于同步化区域，即：那么同步流形是渐进稳定的。那么同步流形是渐进稳定的。N3210 yDfscDsymaxLmaxLS()f cA()cANkSck,3,

16、2,3.3.网络分类网络分类 根据同步化区域根据同步化区域 可以把连续时间复杂动态网络可以把连续时间复杂动态网络（1 1）分为以下几种类型：）分为以下几种类型：1 1）类型）类型网络网络 对应的同步化区域为对应的同步化区域为 ，其中，其中 。若网络耦合强度和外耦合矩阵的特征值满足若网络耦合强度和外耦合矩阵的特征值满足 ，即满足同步判据即满足同步判据：那么类型那么类型网络的同步流形是渐进稳定的。因此，类型网络的同步流形是渐进稳定的。因此，类型网络关于拓扑结构的同步化能力可以用对应的外耦合网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵矩阵 的第二大特征值的第二大特征值 来刻画：来刻画：值越小，

17、其同步化值越小，其同步化能力越强。能力越强。S11(,)S 10 21c120cA222 2）类型）类型网络网络 对应的同步化网络区域对应的同步化网络区域 ，其中，其中 。若网络耦合强度和耦合矩阵的特征。若网络耦合强度和耦合矩阵的特征值满足值满足 和和 ，即满足同步判据条件，即满足同步判据条件：或者或者 那么，类型那么，类型网络的同步流形是渐进稳定的。因此，网络的同步流形是渐进稳定的。因此，类型类型网络关于拓扑结构的同步化能力可以用对应的网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵外耦合矩阵 的特征值的比率的特征值的比率 来刻画：来刻画：值越小，其同步化能力越强。值越小，其同步化能力越强

18、。3 3）类型）类型网络网络 对应的同步化区域为对应的同步化区域为 。对于任意。对于任意 的耦合的耦合强度和外耦合矩阵强度和外耦合矩阵 ，这类网络都无法实现同步。，这类网络都无法实现同步。221(,)S 210 21c2Nc122Nc221NA2N2N3S 空集cA 注意：一个给定的复杂动态网络注意：一个给定的复杂动态网络(1)(1)属于上述三属于上述三种类型中的哪一种是由该网络的孤立节点的动力学函种类型中的哪一种是由该网络的孤立节点的动力学函数数 和网络的内外耦合函数和网络的内外耦合函数 和和 确定的。尽管确定的。尽管同步判据同步判据和和之间的精确关系目前还不十分清楚，之间的精确关系目前还不

19、十分清楚，但是它们并不矛盾。此外，假设网络是连通的，那么但是它们并不矛盾。此外，假设网络是连通的，那么只要网络的耦合强度充分大，类型只要网络的耦合强度充分大，类型网络是一定可以网络是一定可以实现同步的；而只有当耦合强度属于一定范围内时类实现同步的；而只有当耦合强度属于一定范围内时类型型网络才能实现同步，也就是说，太弱或太强个耦网络才能实现同步，也就是说，太弱或太强个耦合强度都会使类型合强度都会使类型网络无法实现同步。这里，同步网络无法实现同步。这里，同步判据判据和和的值一般可以通过数值计算来估计。的值一般可以通过数值计算来估计。()f()四、复杂动力网络的完全同步四、复杂动力网络的完全同步1

20、1、规则网络的完全同步、规则网络的完全同步 1 1）类型）类型网络网络 类型类型网络的同步化能力由耦合矩阵网络的同步化能力由耦合矩阵 的第二大特的第二大特征值征值 确定确定。最近邻耦合网络最近邻耦合网络 对于节点度为（偶数）对于节点度为（偶数）K K的最近邻耦合动态网的最近邻耦合动态网络（络（1 1）而言，它对应的耦合矩阵）而言，它对应的耦合矩阵 是一个特殊的循是一个特殊的循环矩阵，其第二大特征值为：环矩阵，其第二大特征值为：在一般情况下，对于任意在一般情况下，对于任意K K，当网络规模，当网络规模 时，时，单调上升趋于零，意味着当网络规模很大时，最近邻单调上升趋于零，意味着当网络规模很大时，

21、最近邻耦合网络很难或无法达到同步耦合网络很难或无法达到同步A2NCA22,214sin()KNCjjN N,2NC全局耦合网络全局耦合网络 全局耦合网络对应的耦合矩阵为：全局耦合网络对应的耦合矩阵为：它除了零特征根外，其余的特征根均它除了零特征根外，其余的特征根均 。因。因此，当网络的规模此，当网络的规模 时，时，单调下降趋单调下降趋于无穷，说明网络很容易达到同步。于无穷，说明网络很容易达到同步。111111111GCNNANNN,2GCN 星形网络星形网络 星形网络对应的耦合矩阵是：星形网络对应的耦合矩阵是：它的第二大特征根为：它的第二大特征根为：，与网络的规模无与网络的规模无 关，故同步化

22、能力与网关，故同步化能力与网 络规模无关。络规模无关。111110101SCNA,21SC 对于连续时间耗散耦合的类型对于连续时间耗散耦合的类型动态网络式动态网络式(1)(1)，可以，可以得到一下结论：得到一下结论：(1)(1)对给定的耦合强度对给定的耦合强度 ，不管它有多大，当网络规模，不管它有多大，当网络规模充分大时，最近邻耦合网络无法达到同步。充分大时，最近邻耦合网络无法达到同步。(2)(2)对给定的非零耦合强度对给定的非零耦合强度 ，不管它有多小，只要网，不管它有多小，只要网络规模充分大，全局耦合网络必然可以达到同步。络规模充分大，全局耦合网络必然可以达到同步。(3)(3)星形耦合网络

23、的同步能力与网络的规模无关，即当星形耦合网络的同步能力与网络的规模无关，即当耦合强度大于一个与网络规模无关的临界值时，星形耦合强度大于一个与网络规模无关的临界值时，星形网络可以实现同步。网络可以实现同步。cc2 2）类型）类型网络网络 类型类型网络的同步能力由外耦合矩阵网络的同步能力由外耦合矩阵 的最小的最小特征值与第二大特征值之比特征值与第二大特征值之比 确定。确定。最近邻耦合网络最近邻耦合网络对于节点度为（偶数）对于节点度为（偶数）K K的最近邻耦合动态网络（的最近邻耦合动态网络（1 1）而言，它对应的耦合矩阵而言，它对应的耦合矩阵 的特征值满足：的特征值满足：当网络节点当网络节点 很大时

24、，这个特征根的比很大时，这个特征根的比很大，因而网络的同步化能力很差。很大，因而网络的同步化能力很差。2NANCA2,3,2(32),12(1)(2)NC NNCNKNKKN,2NC NNC全局耦合网络全局耦合网络全局耦合网络对应的外耦合矩阵的最小特征值和第全局耦合网络对应的外耦合矩阵的最小特征值和第二大特征值均为二大特征值均为 。因此，由前面关于类型。因此，由前面关于类型网络网络的描述可知，只要的描述可知，只要 ，该网络就可以到达同步。，该网络就可以到达同步。星形耦合网络星形耦合网络 星形耦合网路对应的外耦合矩阵的最小特星形耦合网路对应的外耦合矩阵的最小特征值和第二大特征值之比为征值和第二大

25、特征值之比为 。因此，当网。因此，当网络规模络规模 时，此比值也趋于无穷，该网时，此比值也趋于无穷，该网络无法达到同步。络无法达到同步。N211 NN 由以上分析，对连续时间耗散耦合的类型网络由以上分析，对连续时间耗散耦合的类型网络动态网络动态网络(1)(1)，可以得到以下结论：，可以得到以下结论：(1)(1)对给定的耦合强度对给定的耦合强度 ，不管它有多大，当网络规，不管它有多大，当网络规模充分大时，最近邻耦合网络和星形网络都无法达模充分大时，最近邻耦合网络和星形网络都无法达到同步。到同步。(2)(2)全局耦合网络的同步化能力与网络规模无关，全局耦合网络的同步化能力与网络规模无关，只要只要

26、，全局耦合网络就可以达到同步。，全局耦合网络就可以达到同步。c211 2.2.小世界网络的完全同步小世界网络的完全同步 只针对类型只针对类型网络讨论。考虑具有网络讨论。考虑具有NWNW小世界拓扑结小世界拓扑结构的连续时间耦合动态网络系统式构的连续时间耦合动态网络系统式(1)(1)的同步化能力。的同步化能力。NWNW小世界网络的生成规则：小世界网络的生成规则：初始：最近邻耦合网络初始：最近邻耦合网络 随机化加边：以随机化加边：以 概率在随机选取的一对节点之概率在随机选取的一对节点之间加上一条边间加上一条边即：这种以概率即：这种以概率 加边过程就相当于在最近邻耦合矩加边过程就相当于在最近邻耦合矩阵

27、中的阵中的0 0元素，以概率元素，以概率 置换为置换为1 1，因此将最近邻耦合，因此将最近邻耦合矩阵矩阵 中的中的 的元素，以概率的元素，以概率 置换为置换为 重新计算其对角线元素，这样得到重新计算其对角线元素，这样得到NWNW小世界网络的耦小世界网络的耦合矩阵，记为：合矩阵，记为：令令 是对应的第二大是对应的第二大特征根特征根 NCA1ijjiaa,nwAp N,2(,)nwp Npppp0ijjiaa 左图分别给出左图分别给出 和和 的情的情 形下形下,具有不同加边概率具有不同加边概率 的的NWNW小世小世 界网络模型对应的界网络模型对应的第二大特征根第二大特征根 。对于最近邻网络对于最近

28、邻网络(),(),近似为近似为0 0，此时网络的同步化能力很低。，此时网络的同步化能力很低。在此基础上不断地随机加边（概率在此基础上不断地随机加边（概率 从从0 0变化到变化到1 1）,不断变小最不断变小最 后趋于后趋于 ，同步化能力不断加强。，同步化能力不断加强。结论结论1 1：对于任意给定的耦合强度：对于任意给定的耦合强度 ,当有足够多的节当有足够多的节点个数点个数 ，只要概率，只要概率 大于一定的阈值，该网大于一定的阈值，该网络就会达到同步。络就会达到同步。2 2N=200N=500200N 500N p,2(,)nwp N0p,2(,)nwp Np,2(,)nwp NN0cNd cp

29、左图分别给出左图分别给出 和和 的情的情 形下形下,具有不同规模的具有不同规模的NWNW小世界网络小世界网络 模型对应的模型对应的第二大特征根第二大特征根 。对于规模较小最近邻网络对于规模较小最近邻网络,近似为近似为0 0，此时网络的同步，此时网络的同步 化能力很低。化能力很低。在此基础上不断地增加规模，在此基础上不断地增加规模，不断变小，同步化能力不断加强。不断变小，同步化能力不断加强。结论结论2 2：在加边概率相同的情况下，规模越大的：在加边概率相同的情况下，规模越大的NWNW小世界网络的同步化能力越强。小世界网络的同步化能力越强。2 2p=0.05p=0.10.05p0.1p,2(,)n

30、wp N,2(,)nwp N,2(,)nwp N3.3.无标度网络的完全同步无标度网络的完全同步1 1）无标度网络的完全同步）无标度网络的完全同步 考虑考虑BABA无标度拓扑的连续时间耦合动态网络式无标度拓扑的连续时间耦合动态网络式(1)(1)的同步化能力。这里同样只讨论类型的同步化能力。这里同样只讨论类型网络。网络。BA BA无标度网络的生成规则：无标度网络的生成规则：a.a.增长：从一个具有增长：从一个具有 个节点的网络开始，每次引个节点的网络开始，每次引入一个新的节点，并且连到入一个新的节点，并且连到 个已存在的节点上，个已存在的节点上，b.b.优先连接：一个新节点与一个已经存在节点优先

31、连接：一个新节点与一个已经存在节点 相连相连接的概率接的概率 与节点与节点 的度的度 、节点、节点 的度的度 之间满足如之间满足如下关系：下关系：0mm0mmiiiikjjkiijjkk 构造构造BABA无标度网络时，令无标度网络时，令 耦合矩阵为耦合矩阵为 ,是是 其第二大特征根。通过仿真发现：其第二大特征根。通过仿真发现：随着随着 的增加而下降，并且当的增加而下降，并且当 趋趋 于无穷时，于无穷时，趋于一个负常趋于一个负常 数，左图是对不同的数，左图是对不同的 和和 ，计算，计算 模拟相应的模拟相应的 。当当 时，对应有：时，对应有：结论：在网络规模结论：在网络规模 比较大时，继续增加新的

32、节点不会比较大时，继续增加新的节点不会使使BABA网络的同步化能力下降。网络的同步化能力下降。20mm m(,)sfAm N2(,)sfm N2(,)sfm N2(,)sfm NNNmNN03,5,7mm2()1.2329,2.8758,4.6110sfm 2)2)同步最优网络同步最优网络由上可知：在几种规则网络、由上可知：在几种规则网络、NWNW小世界网络和小世界网络和BABA无标度无标度网络中，全局耦合网络的同步化能力最强，但要构成的网络中，全局耦合网络的同步化能力最强，但要构成的边数却要最多。边数却要最多。问题：问题：如果对于边数相同的网络，什么样拓扑结构的网络同步如果对于边数相同的网络

33、，什么样拓扑结构的网络同步化能力最强？化能力最强？BABA无标度网络是不是同步化性能最佳的增长网络模型？无标度网络是不是同步化性能最佳的增长网络模型？有没有一个增长网络模型的同步化性能比它还好？有没有一个增长网络模型的同步化性能比它还好？因此提出了一个新的网络增长模型因此提出了一个新的网络增长模型-同步最优网络同步最优网络模型。模型。同步最优网络模型的生成规则如下：同步最优网络模型的生成规则如下：增长：增长：从一个具有从一个具有 个节点的网络开始，每次引入个节点的网络开始，每次引入一个新的节点，并将其连接到一个新的节点，并将其连接到 个已存在的节个已存在的节点上。点上。同步最优连接：新节点与已

34、存在的节点同步最优连接：新节点与已存在的节点 相连接时，相连接时，要使得构成的新网络的同步化性能最优，即要使得新要使得构成的新网络的同步化性能最优，即要使得新网络耦合矩阵的第二大特征根最小。网络耦合矩阵的第二大特征根最小。这样，经过这样，经过 步后，产生一个具有步后，产生一个具有 个节点，个节点，条边的同步网络。这个网络在其生长过程中，条边的同步网络。这个网络在其生长过程中，每一步都达到同步化性能最优。每一步都达到同步化性能最优。同步最优网络模型分析：同步最优网络模型分析：优点：与优点：与BABA无标度网络相比，同步最优网络模型的无标度网络相比，同步最优网络模型的第二大特征根有显著的下降，即：

35、同步化性能有了明第二大特征根有显著的下降，即：同步化性能有了明显的提高。显的提高。0m0()mmit0Nt m mt如：当如：当 时，对应有：时，对应有：缺点：分析同步最优网络的节点度分布时还发现，同缺点：分析同步最优网络的节点度分布时还发现，同步最优网络的拓扑结构类似于多中心网络模型：有极步最优网络的拓扑结构类似于多中心网络模型：有极少量的节点与大量节点连接，而大部分节点的连接度少量的节点与大量节点连接，而大部分节点的连接度很小。这使得虽然同步最优网络的同步化性能要比很小。这使得虽然同步最优网络的同步化性能要比BABA无标度网络的同步化性能强，但由于存在极少量的无标度网络的同步化性能强，但由

36、于存在极少量的“集散集散”点（远小于点（远小于BABA无标度网络中的无标度网络中的“集散集散”点的个点的个数），这样，在恶意攻击下它要比数），这样，在恶意攻击下它要比BABA无标度网络更容无标度网络更容易崩溃，对抗恶意攻击更为脆弱。易崩溃，对抗恶意攻击更为脆弱。03,5,7mm2 o()1.9898,3.6935,5.8710sm 3)3)同步优先网络同步优先网络虽然同步最优网络模型的同步化能力有了很大提高，虽然同步最优网络模型的同步化能力有了很大提高，但是对于恶意攻击非常脆弱。一种改进的模型是对于但是对于恶意攻击非常脆弱。一种改进的模型是对于随机去节点和恶意攻击都很鲁棒的同步优先网络模型随机

37、去节点和恶意攻击都很鲁棒的同步优先网络模型,基于增长和同步优先两种机制生成。基于增长和同步优先两种机制生成。同步优先网络的生成规则如下：同步优先网络的生成规则如下：增长：初始时有增长：初始时有 个节点，在每一时间步内加入一个节点，在每一时间步内加入一个新的节点个新的节点,并将其连接到并将其连接到 个已存在的节点上；个已存在的节点上；同步优先连接：新节点与原有节点同步优先连接：新节点与原有节点 相连的概率相连的概率 和和新节点与第新节点与第 个节点连接后构成的新网络同步化能力有个节点连接后构成的新网络同步化能力有关关.0m0()mmiii即：即：这样，经过这样，经过 步后，产生一个具有步后，产生

38、一个具有 个节点，个节点，条边的同步优先网络模型。对于特定的条边的同步优先网络模型。对于特定的 值，当值，当 趋于无穷时，网络的第二大特征值也趋于趋于无穷时，网络的第二大特征值也趋于一个负常数一个负常数 。例如：当例如：当 时，对应的时，对应的jji22iII0mt 0Nt m mtmN2()spm03,5,7mm2()1.2493,2.8765,4.5982spm三种网络同步化能力的比较：三种网络同步化能力的比较：无标度网络与无标度网络与同步优先网络的同步化能同步优先网络的同步化能力非常类似，后者稍逊色力非常类似，后者稍逊色于前者。于前者。同步最优网络的同步化同步最优网络的同步化能力最强。能

39、力最强。03mm4)4)无标度网络的鲁棒性和脆弱性无标度网络的鲁棒性和脆弱性 当网络发生随机故障时，相当于从网络中随机去除当网络发生随机故障时，相当于从网络中随机去除部分节点，由于无标度网络的极度不均匀性，此时去部分节点，由于无标度网络的极度不均匀性，此时去除的节点大多数都是度很小的节点。因此，除的节点大多数都是度很小的节点。因此，网络的同步化能力基本上保持不变。网络的同步化能力基本上保持不变。sfsf22当网络受到恶意攻击时，这时被特定去掉的那一部当网络受到恶意攻击时，这时被特定去掉的那一部分都是度很大的节点。因此，整个网络的连通性发生分都是度很大的节点。因此，整个网络的连通性发生了剧烈变化

40、，甚至于网络被分成若干不连通的分支，了剧烈变化，甚至于网络被分成若干不连通的分支，并且并且 ，从而，网络的同步化能力大大地降，从而，网络的同步化能力大大地降低甚至丧失了。低甚至丧失了。sfsf224 4、局域世界演化网络模型的完全同步、局域世界演化网络模型的完全同步 局域世界演化模型的生成规则：局域世界演化模型的生成规则：增长：网络初始时有增长：网络初始时有 个节点和个节点和 条边，每次加入条边，每次加入一个节点和附带的一个节点和附带的 条边。条边。局域世界有线连接：随即的从网络已有的节点中选局域世界有线连接：随即的从网络已有的节点中选取取 个节点个节点(),(),作为新加入的节点的局域世作为

41、新加入的节点的局域世界。新加入的节点根据优先连接概率：界。新加入的节点根据优先连接概率：来选择局域世界中的来选择局域世界中的m m各节点相连，其中各节点相连，其中LWLW是由新选是由新选的的M M个节点组成。个节点组成。0m0emMMm0()()iilocalilocaljlocaljjjkkMkiLWkmtk 对于每一个新加入的节点，它的局域世界都是随对于每一个新加入的节点，它的局域世界都是随机的从网络中挑选构成，其连接度决定了网络的非均机的从网络中挑选构成，其连接度决定了网络的非均匀性，并且度分布在指数和幂律之间的过渡。因此，匀性，并且度分布在指数和幂律之间的过渡。因此，在这种局域世界演化

42、网络中，在这种局域世界演化网络中，HubHub节点的数目通常要节点的数目通常要比无标度网络的少，因而度分布也要比无标度网络更比无标度网络的少，因而度分布也要比无标度网络更均匀。因此，当面对随机故障的和恶意攻击时，局域均匀。因此，当面对随机故障的和恶意攻击时，局域世界演化网络的同步鲁棒性和脆弱性也就介于无标度世界演化网络的同步鲁棒性和脆弱性也就介于无标度网络和指数网络之间。网络和指数网络之间。一般来说，与无标度网络相比，局域世界演化网络一般来说，与无标度网络相比，局域世界演化网络能够在保持鲁棒性的同时，提高网络对恶意攻击的抗能够在保持鲁棒性的同时，提高网络对恶意攻击的抗脆弱性。脆弱性。五、复杂网

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

44、些网络基本参数对于提高网络同步化能力起到了关键性作用？到了关键性作用？。N 复杂动态网络有许多基本参数，如特征根及其比率，复杂动态网络有许多基本参数，如特征根及其比率，平均路径长度，节点度及其分布、介数和同类匹配系平均路径长度，节点度及其分布、介数和同类匹配系数等，它们对各种网络的同步化能力都有不同程度的数等，它们对各种网络的同步化能力都有不同程度的影响。这里主要介绍它们对小世界网络和无标度网路影响。这里主要介绍它们对小世界网络和无标度网路同步化能力的影响。同步化能力的影响。这里只考虑类型这里只考虑类型连续时间动态网络。由类型连续时间动态网络。由类型网网络的同步判据可知：络的同步判据可知：值越

45、大，网络的同步化能力值越大，网络的同步化能力越差。越差。2N1.1.连接概率连接概率()()和幂律指数和幂律指数()()1 1）和和 对同步化性能的影响对同步化性能的影响 对于小世界网络，当加边或重连概率对于小世界网络，当加边或重连概率 不断变化时，不断变化时，对应地会产生多个具有不同基本特性的小世界模型；同对应地会产生多个具有不同基本特性的小世界模型；同样，对于无标度网络，当幂律指数样，对于无标度网络，当幂律指数 不断变化时，也会不断变化时，也会得到多个不同的无标度网络模型。下面我们就研究由这得到多个不同的无标度网络模型。下面我们就研究由这两个参数两个参数 和和 不断变化而产生的不同网络模型

46、，它们不断变化而产生的不同网络模型，它们的同步化性能与网络基本特性之间的关系。的同步化性能与网络基本特性之间的关系。pppp小世界网络小世界网络 就小世界网络而言，由前面分析小世界网络的同就小世界网络而言，由前面分析小世界网络的同步化稳定性可以知道，随着网络进行步化稳定性可以知道，随着网络进行“小世界小世界”的操的操作作(不断的加入长城边或不断重新连边不断的加入长城边或不断重新连边)，网络的特征，网络的特征根比率会随之减少，即随着加边或重连概率根比率会随之减少，即随着加边或重连概率 的增加的增加，随之减少。如图：随之减少。如图：这说明小世界网络的同步化能这说明小世界网络的同步化能 力随着力随着

47、“小世界小世界”操作（概率操作（概率p p 增加）而增强。增加）而增强。N=2000 N=2000，100100实验的平均值。实验的平均值。特征根比率随连接概率p的变化曲线p2NN/2无标度网络无标度网络 对于度分布为幂律形式对于度分布为幂律形式 的无标度网络的无标度网络，通过研究具有不同，通过研究具有不同 值的无标度网络的同步值的无标度网络的同步化性能时发现，值越大的网络，其化性能时发现，值越大的网络，其 越小。越小。说明幂律指数说明幂律指数 越大对应越大对应 的无标度网络的同步化能的无标度网络的同步化能 力越强。力越强。()Pkk2N2)2)和和 对于网络中各基本参数指标的影响对于网络中各

48、基本参数指标的影响 下面分析网络中各基本特性指标随着下面分析网络中各基本特性指标随着 和和 的变化情的变化情况，从而进一步得到网络性能指标对同步化性能的影况，从而进一步得到网络性能指标对同步化性能的影响。响。小世界网络小世界网络 小世界网络模型的一个显小世界网络模型的一个显 著特点是当加边或重连概著特点是当加边或重连概 率率 很小时，网络的平均很小时，网络的平均 路径长度有大幅度的下降路径长度有大幅度的下降 当当 时，平均路径时，平均路径 长度的变化不是很显著。长度的变化不是很显著。但是随着但是随着 的增加，小世的增加，小世 界网络的平均路径会减少界网络的平均路径会减少。ppp0.51p p

49、虽然相对于具有幂律度分布的无标度网络来说，小虽然相对于具有幂律度分布的无标度网络来说，小世界网络是均匀的，但是其网络中各节点所连接的边世界网络是均匀的，但是其网络中各节点所连接的边数并不是完全相等的。因此，用方差指标：数并不是完全相等的。因此，用方差指标：来表示节点度的分布，则来表示节点度的分布，则 值越大说明网络中节点度值越大说明网络中节点度分布范围越大，并有度较大的节点出现，这时网络的分布范围越大，并有度较大的节点出现，这时网络的度分布变的均匀。由上图的曲线可以看出随着概率度分布变的均匀。由上图的曲线可以看出随着概率 的的增加，网络变的更加非均匀；同时无论是新加入的长增加，网络变的更加非均

50、匀；同时无论是新加入的长程边（程边（NWNW小世界）或是重新连接长程边（小世界）或是重新连接长程边（WSWS小世界）小世界），网络中度的最大值都会增加。，网络中度的最大值都会增加。222iiiikkkNNp无标度网络无标度网络对于具有幂律分布对于具有幂律分布 的无标度网络模型，用节的无标度网络模型，用节点的标准偏差点的标准偏差 来衡量网络的非均匀性，则来衡量网络的非均匀性，则 值越大值越大 反而下降，说明网络中节点度的分布越均匀。在无标反而下降，说明网络中节点度的分布越均匀。在无标度网络中，少数具有度非常大的节点将大量的度很小度网络中，少数具有度非常大的节点将大量的度很小的节点连接在一起，因此