复杂网络的同步.ppt

《复杂网络的同步.ppt》由会员分享，可在线阅读，更多相关《复杂网络的同步.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复杂网络的同步复杂网络的同步许秀竹许秀竹 2010-12-112010-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、络的耦合强度；1 1 节点状态变量之间的内部耦合函数，也称为节点的节点状态变量之间的内部耦合函数，也称为节点的输出函数，这里假设每个节点的输出函数是相同的。输出函数，这里假设每个节点的输出函数是相同的。所谓耗散耦合是指所谓耗散耦合是指耦合矩阵耦合矩阵 满足耗散耦合满足耗散耦合条件条件 。当所有的节点状态都相同时，（。当所有的节点状态都相同时，（1 1）式右）式右端的耦合项自动消失。端的耦合项自动消失。如果在动态网络（如果在动态网络（1 1）中，当）中，当 时有：时有：（2 2）则称网络达到完全（渐进）同步。则称网络达到完全（渐进）同步。这里，这里，称为网络状态空间中的同步流形。称为网络状态空间

11、中的同步流形。当同步实现后，记其结果为：当同步实现后，记其结果为：（3 3）这里这里 称为同步状态。称为同步状态。2.2.同步的判定同步的判定 对状态方程（对状态方程（1 1），关于同步状态），关于同步状态 做线性化，令做线性化，令 为第为第 个节点状态向量的变分，则可以得到变分方程：个节点状态向量的变分，则可以得到变分方程：（4 4）这里，这里，和和 分别是分别是 和和 关于关于 的的JacobiJacobi矩矩阵，通常要求为无界。令：阵，通常要求为无界。令：则上式可以则上式可以写成矩阵方程：写成矩阵方程：（5 5）做分解做分解 ,其中其中 ，而，而 是是矩阵矩阵 的特征根且的特征根且 。令

12、令 ，则有：，则有：(6)(6)判断同步流形稳定的一个常用判据是要求方程（判断同步流形稳定的一个常用判据是要求方程（6 6）的横截的横截lyapunovlyapunov指数指数全为负值。全为负值。在方程（在方程（6 6）中，只有）中，只有 和和 与与 相关，并考虑到相关，并考虑到外耦合矩阵外耦合矩阵A A为非对称阵时，其特征值可能为复数，故为非对称阵时，其特征值可能为复数，故定义主稳定方程为：定义主稳定方程为：其最大其最大lyapunovlyapunov指数指数 是变量是变量 和和 的函数，称为动的函数，称为动力网络的主稳定函数。力网络的主稳定函数。给定一个耦合强度给定一个耦合强度 对于每一个

13、固定的对于每一个固定的在在 复平面上可以对应地找到固定的一点复平面上可以对应地找到固定的一点 ，该，该点所对应的点所对应的 正负号反应了该特征模态的稳定性正负号反应了该特征模态的稳定性（负时稳定，正时不稳定）。如果与（负时稳定，正时不稳定）。如果与 对应的所有特征模态都稳定，那么就认为在该耦合强对应的所有特征模态都稳定，那么就认为在该耦合强度下整个网络的同步流形是渐进稳定的。度下整个网络的同步流形是渐进稳定的。无权无向连通的简单网络的外耦合矩阵无权无向连通的简单网络的外耦合矩阵A A的特征根均为的特征根均为实数，不妨排列为实数，不妨排列为这时其主稳定方程（这时其主稳定方程（6 6）变为）变为并

14、且其对应的主稳定函数并且其对应的主稳定函数 是实参数是实参数 的函数。使得的函数。使得主稳定函数主稳定函数 为负的为负的 的取值范围的取值范围 称为动态网络称为动态网络（1 1）的同步化区域，主要由孤立节点上的动力学函数）的同步化区域，主要由孤立节点上的动力学函数 ，耦合强度，耦合强度 以及外耦合矩阵以及外耦合矩阵 和内耦合矩阵函数和内耦合矩阵函数 确定。如果耦合强度确定。如果耦合强度 与每个外耦合矩阵与每个外耦合矩阵 的每个的每个负值的特征值之积都属于同步化区域，即：负值的特征值之积都属于同步化区域，即：那么同步流形是渐进稳定的。那么同步流形是渐进稳定的。3.3.网络分类网络分类 根据同步化

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

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

17、于任意 的耦合的耦合强度和外耦合矩阵强度和外耦合矩阵 ，这类网络都无法实现同步。，这类网络都无法实现同步。注意：一个给定的复杂动态网络注意：一个给定的复杂动态网络(1)(1)属于上述三种属于上述三种类型中的哪一种是由该网络的孤立节点的动力学函数类型中的哪一种是由该网络的孤立节点的动力学函数 和网络的内外耦合函数和网络的内外耦合函数 和和 确定的。尽管同步判确定的。尽管同步判据据和和之间的精确关系目前还不十分清楚，但是它之间的精确关系目前还不十分清楚，但是它们并不矛盾。此外，假设网络是连通的，那么只要网们并不矛盾。此外，假设网络是连通的，那么只要网络的耦合强度充分大，类型络的耦合强度充分大，类型

18、网络是一定可以实现同网络是一定可以实现同步的；而只有当耦合强度属于一定范围内时类型步的；而只有当耦合强度属于一定范围内时类型网网络才能实现同步，也就是说，太弱或太强个耦合强度络才能实现同步，也就是说，太弱或太强个耦合强度都会使类型都会使类型网络无法实现同步。这里，同步判据网络无法实现同步。这里，同步判据和和的值一般可以通过数值计算来估计。的值一般可以通过数值计算来估计。四、复杂动力网络的完全同步四、复杂动力网络的完全同步1 1、规则网络的完全同步、规则网络的完全同步 1 1）类型）类型网络网络 类型类型网络的同步化能力由耦合矩阵网络的同步化能力由耦合矩阵 的第二大特的第二大特征值征值 确定确定

19、。最近邻耦合网络最近邻耦合网络 对于节点度为（偶数）对于节点度为（偶数）K K的最近邻耦合动态网络的最近邻耦合动态网络（1 1）而言，它对应的耦合矩阵）而言，它对应的耦合矩阵 是一个特殊的循环是一个特殊的循环矩阵，其第二大特征值为：矩阵，其第二大特征值为：在一般情况下，对于任意在一般情况下，对于任意K K，当网络规模，当网络规模 时，时，单调上升趋于零，意味着当网络规模很大时，最近邻单调上升趋于零，意味着当网络规模很大时，最近邻耦合网络很难或无法达到同步耦合网络很难或无法达到同步全局耦合网络全局耦合网络 全局耦合网络对应的耦合矩阵为：全局耦合网络对应的耦合矩阵为：它除了零特征根外，其余的特征根

20、均它除了零特征根外，其余的特征根均 。因。因此，当网络的规模此，当网络的规模 时，时，单调下降趋单调下降趋于无穷，说明网络很容易达到同步。于无穷，说明网络很容易达到同步。星形网络星形网络 星形网络对应的耦合矩阵是：星形网络对应的耦合矩阵是：它的第二大特征根为：它的第二大特征根为：，与网络的规模无与网络的规模无 关，故同步化能力与网关，故同步化能力与网 络规模无关。络规模无关。对于连续时间耗散耦合的类型对于连续时间耗散耦合的类型动态网络式动态网络式(1)(1)，可以，可以得到一下结论：得到一下结论：(1)(1)对给定的耦合强度对给定的耦合强度 ，不管它有多大，当网络规模充，不管它有多大，当网络规

21、模充分大时，最近邻耦合网络无法达到同步。分大时，最近邻耦合网络无法达到同步。(2)(2)对给定的非零耦合强度对给定的非零耦合强度 ，不管它有多小，只要网络，不管它有多小，只要网络规模充分大，全局耦合网络必然可以达到同步。规模充分大，全局耦合网络必然可以达到同步。(3)(3)星形耦合网络的同步能力与网络的规模无关，即当星形耦合网络的同步能力与网络的规模无关，即当耦合强度大于一个与网络规模无关的临界值时，星形网耦合强度大于一个与网络规模无关的临界值时，星形网络可以实现同步。络可以实现同步。2 2）类型）类型网络网络 类型类型网络的同步能力由外耦合矩阵网络的同步能力由外耦合矩阵 的最小特的最小特征值

22、与第二大特征值之比征值与第二大特征值之比 确定。确定。最近邻耦合网络最近邻耦合网络对于节点度为（偶数）对于节点度为（偶数）K K的最近邻耦合动态网络的最近邻耦合动态网络（1 1）而言，它对应的耦合矩阵）而言，它对应的耦合矩阵 的特征值满足：的特征值满足：当网络节点当网络节点 很大时，这个特征根的比很大时，这个特征根的比很大，因而网络的同步化能力很差。很大，因而网络的同步化能力很差。全局耦合网络全局耦合网络全局耦合网络对应的外耦合矩阵的最小特征值和第全局耦合网络对应的外耦合矩阵的最小特征值和第二大特征值均为二大特征值均为 。因此，由前面关于类型。因此，由前面关于类型网络网络的描述可知，只要的描述

23、可知，只要 ，该网络就可以到达同步。，该网络就可以到达同步。星形耦合网络星形耦合网络 星形耦合网路对应的外耦合矩阵的最小特星形耦合网路对应的外耦合矩阵的最小特征值和第二大特征值之比为征值和第二大特征值之比为 。因此，当网。因此，当网络规模络规模 时，此比值也趋于无穷，该网络时，此比值也趋于无穷，该网络无法达到同步。无法达到同步。由以上分析，对连续时间耗散耦合的类型网络由以上分析，对连续时间耗散耦合的类型网络动态网络动态网络(1)(1)，可以得到以下结论：，可以得到以下结论：(1)(1)对给定的耦合强度对给定的耦合强度 ，不管它有多大，当网络规，不管它有多大，当网络规模充分大时，最近邻耦合网络和

24、星形网络都无法达模充分大时，最近邻耦合网络和星形网络都无法达到同步。到同步。(2)(2)全局耦合网络的同步化能力与网络规模无关，全局耦合网络的同步化能力与网络规模无关，只要只要 ，全局耦合网络就可以达到同步。，全局耦合网络就可以达到同步。2.2.小世界网络的完全同步小世界网络的完全同步 只针对类型只针对类型网络讨论。考虑具有网络讨论。考虑具有NWNW小世界拓扑结小世界拓扑结构的连续时间耦合动态网络系统式构的连续时间耦合动态网络系统式(1)(1)的同步化能力。的同步化能力。NWNW小世界网络的生成规则：小世界网络的生成规则：初始：最近邻耦合网络初始：最近邻耦合网络 随机化加边：以随机化加边：以

25、概率在随机选取的一对节点之间概率在随机选取的一对节点之间加上一条边加上一条边即：这种以概率即：这种以概率 加边过程就相当于在最近邻耦合矩加边过程就相当于在最近邻耦合矩阵中的阵中的0 0元素，以概率元素，以概率 置换为置换为1 1，因此将最近邻耦合，因此将最近邻耦合矩阵矩阵 中的中的 的元素，以概率的元素，以概率 置换为置换为 重新计算其对角线元素，这样得到重新计算其对角线元素，这样得到NWNW小世界网络的耦小世界网络的耦合矩阵，记为：合矩阵，记为：令令 是对应的第二大是对应的第二大特征根特征根 左图分别给出左图分别给出 和和 的情的情 形下形下,具有不同加边概率具有不同加边概率 的的NWNW小

26、世小世 界网络模型对应的界网络模型对应的第二大特征根第二大特征根 。对于最近邻网络对于最近邻网络(),),近似为近似为0 0，此时网络的同步化能力很低。，此时网络的同步化能力很低。在此基础上不断地随机加边（概率在此基础上不断地随机加边（概率 从从0 0变化到变化到1 1）,不断变小最不断变小最 后趋于后趋于 ，同步化能力不断加强。，同步化能力不断加强。结论结论1 1：对于任意给定的耦合强度：对于任意给定的耦合强度 ,当有足够多的节当有足够多的节点个数点个数 ，只要概率，只要概率 大于一定的阈值，该网大于一定的阈值，该网络就会达到同步。络就会达到同步。2 2N=200N=500 左图分别给出左图

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

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

29、节点 的度的度 之间满足如之间满足如下关系：下关系：构造构造BABA无标度网络时，令无标度网络时，令 耦合矩阵为耦合矩阵为 ,是是 其第二大特征根。通过仿真发现：其第二大特征根。通过仿真发现：随着随着 的增加而下降，并且当的增加而下降，并且当 趋趋 于无穷时，于无穷时，趋于一个负常趋于一个负常 数，左图是对不同的数，左图是对不同的 和和 ，计算，计算 模拟相应的模拟相应的 。当当 时，对应有：时，对应有：结论：在网络规模结论：在网络规模 比较大时，继续增加新的节点不会比较大时，继续增加新的节点不会使使BABA网络的同步化能力下降。网络的同步化能力下降。22)2)同步最优网络同步最优网络由上可知

30、：在几种规则网络、由上可知：在几种规则网络、NWNW小世界网络和小世界网络和BABA无标度无标度网络中，全局耦合网络的同步化能力最强，但要构成网络中，全局耦合网络的同步化能力最强，但要构成的边数却要最多。的边数却要最多。问题：问题：如果对于边数相同的网络，什么样拓扑结构的网络同步如果对于边数相同的网络，什么样拓扑结构的网络同步化能力最强？化能力最强？BABA无标度网络是不是同步化性能最佳的增长网络模型？无标度网络是不是同步化性能最佳的增长网络模型？有没有一个增长网络模型的同步化性能比它还好？有没有一个增长网络模型的同步化性能比它还好？因此提出了一个新的网络增长模型因此提出了一个新的网络增长模型

31、-同步最优网络同步最优网络模型。模型。同步最优网络模型的生成规则如下：同步最优网络模型的生成规则如下：增长：增长：从一个具有从一个具有 个节点的网络开始，每次引入个节点的网络开始，每次引入一个新的节点，并将其连接到一个新的节点，并将其连接到 个已存在的个已存在的节点上。节点上。同步最优连接：新节点与已存在的节点同步最优连接：新节点与已存在的节点 相连接时，相连接时，要使得构成的新网络的同步化性能最优，即要使得要使得构成的新网络的同步化性能最优，即要使得新网络耦合矩阵的第二大特征根最小。新网络耦合矩阵的第二大特征根最小。这样，经过这样，经过 步后，产生一个具有步后，产生一个具有 个节点，个节点，

32、条边的同步网络。这个网络在其生长过程中，条边的同步网络。这个网络在其生长过程中，每一步都达到同步化性能最优。每一步都达到同步化性能最优。同步最优网络模型分析：同步最优网络模型分析：优点：与优点：与BABA无标度网络相比，同步最优网络模型的无标度网络相比，同步最优网络模型的第二大特征根有显著的下降，即：同步化性能有了明第二大特征根有显著的下降，即：同步化性能有了明显的提高。显的提高。如：当如：当 时，对应有：时，对应有：缺点：分析同步最优网络的节点度分布时还发现，同缺点：分析同步最优网络的节点度分布时还发现，同步最优网络的拓扑结构类似于多中心网络模型：有极步最优网络的拓扑结构类似于多中心网络模型

33、：有极少量的节点与大量节点连接，而大部分节点的连接度少量的节点与大量节点连接，而大部分节点的连接度很小。这使得虽然同步最优网络的同步化性能要比很小。这使得虽然同步最优网络的同步化性能要比BABA无标度网络的同步化性能强，但由于存在极少量的无标度网络的同步化性能强，但由于存在极少量的“集散集散”点（远小于点（远小于BABA无标度网络中的无标度网络中的“集散集散”点的个点的个数），这样，在恶意攻击下它要比数），这样，在恶意攻击下它要比BABA无标度网络更容无标度网络更容易崩溃，对抗恶意攻击更为脆弱。易崩溃，对抗恶意攻击更为脆弱。3)3)同步优先网络同步优先网络虽然同步最优网络模型的同步化能力有了很

34、大提高，虽然同步最优网络模型的同步化能力有了很大提高，但是对于恶意攻击非常脆弱。一种改进的模型是对于但是对于恶意攻击非常脆弱。一种改进的模型是对于随机去节点和恶意攻击都很鲁棒的同步优先网络模型随机去节点和恶意攻击都很鲁棒的同步优先网络模型,基于增长和同步优先两种机制生成。基于增长和同步优先两种机制生成。同步优先网络的生成规则如下：同步优先网络的生成规则如下：增长：初始时有增长：初始时有 个节点，在每一时间步内加入一个节点，在每一时间步内加入一个新的节点个新的节点,并将其连接到并将其连接到 个已存在的节点上；个已存在的节点上；同步优先连接：新节点与原有节点同步优先连接：新节点与原有节点 相连的概

35、率相连的概率 和和新节点与第新节点与第 个节点连接后构成的新网络同步化能力有个节点连接后构成的新网络同步化能力有关关.即：即：这样，经过这样，经过 步后，产生一个具有步后，产生一个具有 个节点，个节点，条边的同步优先网络模型。对于特定的条边的同步优先网络模型。对于特定的 值，当值，当 趋于无穷时，网络的第二大特征值也趋于趋于无穷时，网络的第二大特征值也趋于一个负常数一个负常数 。例如：当例如：当 时，对应的时，对应的三种网络同步化能力的比较：三种网络同步化能力的比较：无标度网络与无标度网络与同步优先网络的同步化能同步优先网络的同步化能力非常类似，后者稍逊色力非常类似，后者稍逊色于前者。于前者。

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

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

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

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

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

41、杂动态网络有许多基本参数，如特征根及其比率，复杂动态网络有许多基本参数，如特征根及其比率，平均路径长度，节点度及其分布、介数和同类匹配系平均路径长度，节点度及其分布、介数和同类匹配系数等，它们对各种网络的同步化能力都有不同程度的数等，它们对各种网络的同步化能力都有不同程度的影响。这里主要介绍它们对小世界网络和无标度网路影响。这里主要介绍它们对小世界网络和无标度网路同步化能力的影响。同步化能力的影响。这里只考虑类型这里只考虑类型连续时间动态网络。由类型连续时间动态网络。由类型网络网络的同步判据可知：的同步判据可知：值越大，网络的同步化能力越值越大，网络的同步化能力越差。差。1.1.连接概率连接概

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

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

44、=2000，100100实验的平均值。实验的平均值。特征根比率随连接概率p的变化曲线N/2无标度网络无标度网络 对于度分布为幂律形式对于度分布为幂律形式 的无标度网络，的无标度网络，通过研究具有不同通过研究具有不同 值的无标度网络的同步化值的无标度网络的同步化性能时发现，值越大的网络，其性能时发现，值越大的网络，其 越小。越小。说明幂律指数说明幂律指数 越大对应越大对应 的无标度网络的同步化能的无标度网络的同步化能 力越强。力越强。2)2)和和 对于网络中各基本参数指标的影响对于网络中各基本参数指标的影响 下面分析网络中各基本特性指标随着下面分析网络中各基本特性指标随着 和和 的变化情的变化情

45、况，从而进一步得到网络性能指标对同步化性能的影响。况，从而进一步得到网络性能指标对同步化性能的影响。小世界网络小世界网络 小世界网络模型的一个显小世界网络模型的一个显 著特点是当加边或重连概著特点是当加边或重连概 率率 很小时，网络的平均很小时，网络的平均 路径长度有大幅度的下降路径长度有大幅度的下降 当当 时，平均路径时，平均路径 长度的变化不是很显著。长度的变化不是很显著。但是随着但是随着 的增加，小世的增加，小世 界网络的平均路径会减少。界网络的平均路径会减少。虽然相对于具有幂律度分布的无标度网络来说，小虽然相对于具有幂律度分布的无标度网络来说，小世界网络是均匀的，但是其网络中各节点所连

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

47、网络中度的最大值都会增加。网络中度的最大值都会增加。无标度网络无标度网络对于具有幂律分布对于具有幂律分布 的无标度网络模型，用节的无标度网络模型，用节点的标准偏差点的标准偏差 来衡量网络的非均匀性，则来衡量网络的非均匀性，则 值越大值越大 反而下降，说明网络中节点度的分布越均匀。在无标反而下降，说明网络中节点度的分布越均匀。在无标度网络中，少数具有度非常大的节点将大量的度很小度网络中，少数具有度非常大的节点将大量的度很小的节点连接在一起，因此这些度大的节点使得网络的的节点连接在一起，因此这些度大的节点使得网络的平均路径很短。而随着平均路径很短。而随着 值的增大网络度分布变的比值的增大网络度分布

48、变的比较均匀，因此网络的平均路径就会增加，同时平均度较均匀，因此网络的平均路径就会增加，同时平均度变小。变小。无标度网络的平均路径无标度网络的平均路径D D随随 变化的曲线变化的曲线 小图是网络平均度小图是网络平均度k k随随 变化的曲线变化的曲线 总结：由上述对小世界网络和无标度网络的分析总结：由上述对小世界网络和无标度网络的分析可以看到，小世界网络在最近邻耦合网络的基础上通可以看到，小世界网络在最近邻耦合网络的基础上通过过“小世界操作小世界操作”，使得网络的平均路径长度减小，使得网络的平均路径长度减小，同时也增加了网络节点的度分布的非均匀性以及最大同时也增加了网络节点的度分布的非均匀性以及

49、最大的度，从而同步化能力有了显著提高；而对于无标度的度，从而同步化能力有了显著提高；而对于无标度网络却有了相反的结论，即只有提高网络的均匀性，网络却有了相反的结论，即只有提高网络的均匀性，增大平均路径长度或减小网络的平均度，才能使得无增大平均路径长度或减小网络的平均度，才能使得无标度网络的同步化性能提高。因此，单纯用度的大小标度网络的同步化性能提高。因此，单纯用度的大小、度分布、或平均路径长度等指标都无法统一表征复、度分布、或平均路径长度等指标都无法统一表征复杂网络的同步化能力。杂网络的同步化能力。2.2.介数介数 某个节点的介数越大说明在信息传播过程中的信某个节点的介数越大说明在信息传播过程

50、中的信息量也会越多，于是也就越容易发生信息堵塞。研究息量也会越多，于是也就越容易发生信息堵塞。研究发现，无论是小世界网络还是无标度网络，节点的最发现，无论是小世界网络还是无标度网络，节点的最大介数值都会随着概率大介数值都会随着概率 和参数和参数 的增加而减小。这说的增加而减小。这说明，介数是一个相对能够统一反映网络同步化能力的明，介数是一个相对能够统一反映网络同步化能力的参数。参数。最大介数最大介数B Bmaxmax随连接概率随连接概率p p的变化图的变化图 假设在两组高度连接的子网络之间只有少数的节假设在两组高度连接的子网络之间只有少数的节点相连，那么这几个少数节点的介数就会很大，会有点相连