复杂网络的同步精选PPT.ppt

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

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

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

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

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

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

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

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

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

9、，是今率同步等。两个不同单元的同步研究更具挑战性，是今后一个重要研究方向。后一个重要研究方向。第6页，此课件共57页哦7三、复杂网络的完全同步判据三、复杂网络的完全同步判据1.1.数学描述数学描述 首先介绍一般连续时间耦合网络的完全同步问题。首先介绍一般连续时间耦合网络的完全同步问题。设连续时间耗散耦合动态网络中有设连续时间耗散耦合动态网络中有 个相同的节点，个相同的节点，其中第其中第 个节点的状态变量为：个节点的状态变量为：单个节点满足的状态方程是：单个节点满足的状态方程是：多个节点的耦合动态网络中，多个节点的耦合动态网络中，的状态方程是：的状态方程是：（1 1）其中：其中：是定义好的函数（

10、通常是非线性的）常数是定义好的函数（通常是非线性的）常数 为网络的耦合强度；为网络的耦合强度；第7页，此课件共57页哦1 1 节点状态变量之间的内部耦合函数，也称为节点的输节点状态变量之间的内部耦合函数，也称为节点的输出函数，这里假设每个节点的输出函数是相同的。出函数，这里假设每个节点的输出函数是相同的。所谓耗散耦合是指所谓耗散耦合是指耦合矩阵耦合矩阵 满足耗散耦合条件满足耗散耦合条件 。当所有的节点状态都相同时，（。当所有的节点状态都相同时，（1 1）式右端的耦合项自动消失。）式右端的耦合项自动消失。如果在动态网络（如果在动态网络（1 1）中，当）中，当 时有：时有：（2 2）则称网络达到完

11、全（渐进）同步。则称网络达到完全（渐进）同步。这里，这里，称为网络状态空间中的同步流形。称为网络状态空间中的同步流形。当同步实现后，记其结果为：当同步实现后，记其结果为：（3 3）这里这里 称为同步状态。称为同步状态。第8页，此课件共57页哦2.2.同步的判定同步的判定 对状态方程（对状态方程（1 1），关于同步状态），关于同步状态 做线性化，令做线性化，令 为第为第 个节点状态向量的变分，则可以得到变分方程：个节点状态向量的变分，则可以得到变分方程：（4 4）这里，这里，和和 分别是分别是 和和 关于关于 的的JacobiJacobi矩阵，矩阵，通常要求为无界。令：通常要求为无界。令：则上式

12、可以写成矩则上式可以写成矩阵方程：阵方程：（5 5）做分解做分解 ,其中其中 ，而，而 是矩阵是矩阵 的特征根且的特征根且 。第9页，此课件共57页哦令令 ，则有：，则有：(6)(6)判断同步流形稳定的一个常用判据是要求方程（判断同步流形稳定的一个常用判据是要求方程（6 6）的横）的横截截lyapunovlyapunov指数指数全为负值。全为负值。在方程（在方程（6 6）中，只有）中，只有 和和 与与 相关，并考虑到外耦相关，并考虑到外耦合矩阵合矩阵A A为非对称阵时，其特征值可能为复数，故定义主稳为非对称阵时，其特征值可能为复数，故定义主稳定方程为：定方程为：其最大其最大lyapunovly

13、apunov指数指数 是变量是变量 和和 的函数，称为动力的函数，称为动力网络的主稳定函数。网络的主稳定函数。第10页，此课件共57页哦 给定一个耦合强度给定一个耦合强度 对于每一个固定的对于每一个固定的在在 复平面上可以对应地找到固定的一点复平面上可以对应地找到固定的一点 ，该，该点所对应的点所对应的 正负号反应了该特征模态的稳定性正负号反应了该特征模态的稳定性（负时稳定，正时不稳定）。如果与（负时稳定，正时不稳定）。如果与 对应的所有特征模态都稳定，那么就认为在该耦合强对应的所有特征模态都稳定，那么就认为在该耦合强度下整个网络的同步流形是渐进稳定的。度下整个网络的同步流形是渐进稳定的。第1

14、1页，此课件共57页哦 无权无向连通的简单网络的外耦合矩阵无权无向连通的简单网络的外耦合矩阵A A的特征根均为实的特征根均为实数，不妨排列为数，不妨排列为这时其主稳定方程（这时其主稳定方程（6 6）变为）变为并且其对应的主稳定函数并且其对应的主稳定函数 是实参数是实参数 的函数。使得主的函数。使得主稳定函数稳定函数 为负的为负的 的取值范围的取值范围 称为动态网络（称为动态网络（1 1）的同步化区域，主要由孤立节点上的动力学函数的同步化区域，主要由孤立节点上的动力学函数 ，耦，耦合强度合强度 以及外耦合矩阵以及外耦合矩阵 和内耦合矩阵函数和内耦合矩阵函数 确定。如果耦合强度确定。如果耦合强度

15、与每个外耦合矩阵与每个外耦合矩阵 的每个负的每个负值的特征值之积都属于同步化区域，即：值的特征值之积都属于同步化区域，即：那么同步流形是渐进稳定的。那么同步流形是渐进稳定的。第12页，此课件共57页哦3.3.网络分类网络分类 根据同步化区域根据同步化区域 可以把连续时间复杂动态网络可以把连续时间复杂动态网络（1 1）分为以下几种类型：）分为以下几种类型：1 1）类型）类型网络网络 对应的同步化区域为对应的同步化区域为 ，其中，其中 。若网。若网络耦合强度和外耦合矩阵的特征值满足络耦合强度和外耦合矩阵的特征值满足 ，即满足同，即满足同步判据步判据：那么类型那么类型网络的同步流形是渐进稳定的。因此

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

17、构的同步化能力可以用对应的外耦合网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵矩阵 的特征值的比率的特征值的比率 来刻画：来刻画：值越小，其值越小，其同步化能力越强。同步化能力越强。3 3）类型）类型网络网络 对应的同步化区域为对应的同步化区域为 。对于任意。对于任意 的耦合强的耦合强度和外耦合矩阵度和外耦合矩阵 ，这类网络都无法实现同步。，这类网络都无法实现同步。第14页，此课件共57页哦 注意：一个给定的复杂动态网络注意：一个给定的复杂动态网络(1)(1)属于上述三种类型属于上述三种类型中的哪一种是由该网络的孤立节点的动力学函数中的哪一种是由该网络的孤立节点的动力学函数 和网络和网络的

18、内外耦合函数的内外耦合函数 和和 确定的。尽管同步判据确定的。尽管同步判据和和之间之间的精确关系目前还不十分清楚，但是它们并不矛盾。此外，的精确关系目前还不十分清楚，但是它们并不矛盾。此外，假设网络是连通的，那么只要网络的耦合强度充分大，类型假设网络是连通的，那么只要网络的耦合强度充分大，类型网络是一定可以实现同步的；而只有当耦合强度属于一定网络是一定可以实现同步的；而只有当耦合强度属于一定范围内时类型范围内时类型网络才能实现同步，也就是说，太弱或太强网络才能实现同步，也就是说，太弱或太强个耦合强度都会使类型个耦合强度都会使类型网络无法实现同步。这里，同步判网络无法实现同步。这里，同步判据据和

19、和的值一般可以通过数值计算来估计。的值一般可以通过数值计算来估计。第15页，此课件共57页哦四、复杂动力网络的完全同步四、复杂动力网络的完全同步1 1、规则网络的完全同步、规则网络的完全同步 1 1）类型）类型网络网络 类型类型网络的同步化能力由耦合矩阵网络的同步化能力由耦合矩阵 的第二大特征值的第二大特征值 确定确定。最近邻耦合网络最近邻耦合网络 对于节点度为（偶数）对于节点度为（偶数）K K的最近邻耦合动态网络（的最近邻耦合动态网络（1 1）而）而言，它对应的耦合矩阵言，它对应的耦合矩阵 是一个特殊的循环矩阵，其第二大是一个特殊的循环矩阵，其第二大特征值为：特征值为：在一般情况下，对于任意

20、在一般情况下，对于任意K K，当网络规模，当网络规模 时，时，单调上升趋于零，意味着当网络规模很大时，最近邻耦合网络单调上升趋于零，意味着当网络规模很大时，最近邻耦合网络很难或无法达到同步很难或无法达到同步第16页，此课件共57页哦全局耦合网络全局耦合网络 全局耦合网络对应的耦合矩阵为：全局耦合网络对应的耦合矩阵为：它除了零特征根外，其余的特征根均它除了零特征根外，其余的特征根均 。因。因此，当网络的规模此，当网络的规模 时，时，单调下降趋单调下降趋于无穷，说明网络很容易达到同步。于无穷，说明网络很容易达到同步。第17页，此课件共57页哦星形网络星形网络 星形网络对应的耦合矩阵是：星形网络对应

21、的耦合矩阵是：它的第二大特征根为：它的第二大特征根为：，与网络的规模无与网络的规模无 关，故同步化能力与网关，故同步化能力与网 络规模无关。络规模无关。第18页，此课件共57页哦对于连续时间耗散耦合的类型对于连续时间耗散耦合的类型动态网络式动态网络式(1)(1)，可以得，可以得到一下结论：到一下结论：(1)(1)对给定的耦合强度对给定的耦合强度 ，不管它有多大，当网络规模充分大时，不管它有多大，当网络规模充分大时，最近邻耦合网络无法达到同步。最近邻耦合网络无法达到同步。(2)(2)对给定的非零耦合强度对给定的非零耦合强度 ，不管它有多小，只要网络，不管它有多小，只要网络规模充分大，全局耦合网络

22、必然可以达到同步。规模充分大，全局耦合网络必然可以达到同步。(3)(3)星形耦合网络的同步能力与网络的规模无关，即当耦合强星形耦合网络的同步能力与网络的规模无关，即当耦合强度大于一个与网络规模无关的临界值时，星形网络可以实现度大于一个与网络规模无关的临界值时，星形网络可以实现同步。同步。第19页，此课件共57页哦2 2）类型）类型网络网络 类型类型网络的同步能力由外耦合矩阵网络的同步能力由外耦合矩阵 的最小特征值与的最小特征值与第二大特征值之比第二大特征值之比 确定。确定。最近邻耦合网络最近邻耦合网络对于节点度为（偶数）对于节点度为（偶数）K K的最近邻耦合动态网络（的最近邻耦合动态网络（1

23、1）而言，）而言，它对应的耦合矩阵它对应的耦合矩阵 的特征值满足：的特征值满足：当网络节点当网络节点 很大时，这个特征根的比很大时，这个特征根的比很大，因而网络的同步化能力很差。很大，因而网络的同步化能力很差。第20页，此课件共57页哦全局耦合网络全局耦合网络全局耦合网络对应的外耦合矩阵的最小特征值和第二大全局耦合网络对应的外耦合矩阵的最小特征值和第二大特征值均为特征值均为 。因此，由前面关于类型。因此，由前面关于类型网络的描述可网络的描述可知，只要知，只要 ，该网络就可以到达同步。，该网络就可以到达同步。星形耦合网络星形耦合网络 星形耦合网路对应的外耦合矩阵的最小特星形耦合网路对应的外耦合矩

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

25、模无关，只要全局耦合网络的同步化能力与网络规模无关，只要 ，全局耦合网络就可以达到同步。，全局耦合网络就可以达到同步。第22页，此课件共57页哦2.2.小世界网络的完全同步小世界网络的完全同步 只针对类型只针对类型网络讨论。考虑具有网络讨论。考虑具有NWNW小世界拓扑结构的连续小世界拓扑结构的连续时间耦合动态网络系统式时间耦合动态网络系统式(1)(1)的同步化能力。的同步化能力。NWNW小世界网络的生成规则：小世界网络的生成规则：初始：最近邻耦合网络初始：最近邻耦合网络 随机化加边：以随机化加边：以 概率在随机选取的一对节点之间加概率在随机选取的一对节点之间加上一条边上一条边即：这种以概率即：

26、这种以概率 加边过程就相当于在最近邻耦合矩阵中加边过程就相当于在最近邻耦合矩阵中的的0 0元素，以概率元素，以概率 置换为置换为1 1，因此将最近邻耦合矩阵，因此将最近邻耦合矩阵 中的中的 的元素，以概率的元素，以概率 置换为置换为 重新计算其对角线元素，这样得到重新计算其对角线元素，这样得到NWNW小世界网络的耦合矩阵，小世界网络的耦合矩阵，记为：记为：令令 是对应的第二大特征根是对应的第二大特征根 第23页，此课件共57页哦 左图分别给出左图分别给出 和和 的情的情 形下形下,具有不同加边概率具有不同加边概率 的的NWNW小世小世 界网络模型对应的第二大特征根界网络模型对应的第二大特征根

27、。对于最近邻网络对于最近邻网络(),(),近似为近似为0 0，此时网络的同步化能力很低。，此时网络的同步化能力很低。在此基础上不断地随机加边（概率在此基础上不断地随机加边（概率 从从0 0变化到变化到1 1）,不断变小最不断变小最 后趋于后趋于 ，同步化能力不断加强。，同步化能力不断加强。结论结论1 1：对于任意给定的耦合强度：对于任意给定的耦合强度 ,当有足够多的节当有足够多的节点个数点个数 ，只要概率，只要概率 大于一定的阈值，该网大于一定的阈值，该网络就会达到同步。络就会达到同步。2 2N=200N=500第24页，此课件共57页哦 左图分别给出左图分别给出 和和 的情的情 形下形下,具

28、有不同规模的具有不同规模的NWNW小世界网络小世界网络 模型对应的第二大特征根模型对应的第二大特征根 。对于规模较小最近邻网络对于规模较小最近邻网络,近似为近似为0 0，此时网络的同步，此时网络的同步 化能力很低。化能力很低。在此基础上不断地增加规模，在此基础上不断地增加规模，不断变小，同步化能力不断加强。不断变小，同步化能力不断加强。结论结论2 2：在加边概率相同的情况下，规模越大的：在加边概率相同的情况下，规模越大的NWNW小世界网络的同步化能力越强。小世界网络的同步化能力越强。2 2p=0.05p=0.1第25页，此课件共57页哦3.3.无标度网络的完全同步无标度网络的完全同步1 1）无

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

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

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

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

33、过这样，经过 步后，产生一个具有步后，产生一个具有 个节点，个节点，条边的同步网络。这个网络在其生长过程中，每一步都条边的同步网络。这个网络在其生长过程中，每一步都达到同步化性能最优。达到同步化性能最优。同步最优网络模型分析：同步最优网络模型分析：优点：与优点：与BABA无标度网络相比，同步最优网络模型的无标度网络相比，同步最优网络模型的第二大特征根有显著的下降，即：同步化性能有了明第二大特征根有显著的下降，即：同步化性能有了明显的提高。显的提高。第29页，此课件共57页哦如：当如：当 时，对应有：时，对应有：缺点：分析同步最优网络的节点度分布时还发现，同缺点：分析同步最优网络的节点度分布时还

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

35、，对抗恶意攻击更为脆弱。第30页，此课件共57页哦3)3)同步优先网络同步优先网络虽然同步最优网络模型的同步化能力有了很大提高，虽然同步最优网络模型的同步化能力有了很大提高，但是对于恶意攻击非常脆弱。一种改进的模型是对于但是对于恶意攻击非常脆弱。一种改进的模型是对于随机去节点和恶意攻击都很鲁棒的同步优先网络模型随机去节点和恶意攻击都很鲁棒的同步优先网络模型,基于增长和同步优先两种机制生成。基于增长和同步优先两种机制生成。同步优先网络的生成规则如下：同步优先网络的生成规则如下：增长：初始时有增长：初始时有 个节点，在每一时间步内加入一个节点，在每一时间步内加入一个新的节点个新的节点,并将其连接到

36、并将其连接到 个已存在的节点上；个已存在的节点上；同步优先连接：新节点与原有节点同步优先连接：新节点与原有节点 相连的概率相连的概率 和和新节点与第新节点与第 个节点连接后构成的新网络同步化能力有个节点连接后构成的新网络同步化能力有关关.第31页，此课件共57页哦即：即：这样，经过这样，经过 步后，产生一个具有步后，产生一个具有 个节点，个节点，条边的同步优先网络模型。对于特定的条边的同步优先网络模型。对于特定的 值，当值，当 趋于无穷时，网络的第二大特征值也趋于趋于无穷时，网络的第二大特征值也趋于一个负常数一个负常数 。例如：当例如：当 时，对应的时，对应的第32页，此课件共57页哦三种网络

37、同步化能力的比较：三种网络同步化能力的比较：无标度网络与无标度网络与同步优先网络的同步化能同步优先网络的同步化能力非常类似，后者稍逊色力非常类似，后者稍逊色于前者。于前者。同步最优网络的同步化同步最优网络的同步化能力最强。能力最强。第33页，此课件共57页哦4)4)无标度网络的鲁棒性和脆弱性无标度网络的鲁棒性和脆弱性 当网络发生随机故障时，相当于从网络中随机去除当网络发生随机故障时，相当于从网络中随机去除部分节点，由于无标度网络的极度不均匀性，此时去部分节点，由于无标度网络的极度不均匀性，此时去除的节点大多数都是度很小的节点。因此，除的节点大多数都是度很小的节点。因此，网络的同步化能力基本上保

38、持不变。网络的同步化能力基本上保持不变。第34页，此课件共57页哦当网络受到恶意攻击时，这时被特定去掉的那一部当网络受到恶意攻击时，这时被特定去掉的那一部分都是度很大的节点。因此，整个网络的连通性发生分都是度很大的节点。因此，整个网络的连通性发生了剧烈变化，甚至于网络被分成若干不连通的分支，了剧烈变化，甚至于网络被分成若干不连通的分支，并且并且 ，从而，网络的同步化能力大大地降，从而，网络的同步化能力大大地降低甚至丧失了。低甚至丧失了。第35页，此课件共57页哦4 4、局域世界演化网络模型的完全同步、局域世界演化网络模型的完全同步 局域世界演化模型的生成规则：局域世界演化模型的生成规则：增长：

39、网络初始时有增长：网络初始时有 个节点和个节点和 条边，每次加入一个节条边，每次加入一个节点和附带的点和附带的 条边。条边。局域世界有线连接：随即的从网络已有的节点中选取局域世界有线连接：随即的从网络已有的节点中选取 个个节点节点(),(),作为新加入的节点的局域世界。新加入的节点作为新加入的节点的局域世界。新加入的节点根据优先连接概率：根据优先连接概率：来选择局域世界中的来选择局域世界中的m m各节点相连，其中各节点相连，其中LWLW是由新选是由新选的的M M个节点组成。个节点组成。第36页，此课件共57页哦 对于每一个新加入的节点，它的局域世界都是随对于每一个新加入的节点，它的局域世界都是

40、随机的从网络中挑选构成，其连接度决定了网络的非均机的从网络中挑选构成，其连接度决定了网络的非均匀性，并且度分布在指数和幂律之间的过渡。因此，匀性，并且度分布在指数和幂律之间的过渡。因此，在这种局域世界演化网络中，在这种局域世界演化网络中，HubHub节点的数目通常要节点的数目通常要比无标度网络的少，因而度分布也要比无标度网络更比无标度网络的少，因而度分布也要比无标度网络更均匀。因此，当面对随机故障的和恶意攻击时，局域均匀。因此，当面对随机故障的和恶意攻击时，局域世界演化网络的同步鲁棒性和脆弱性也就介于无标度世界演化网络的同步鲁棒性和脆弱性也就介于无标度网络和指数网络之间。网络和指数网络之间。一

41、般来说，与无标度网络相比，局域世界演化网络一般来说，与无标度网络相比，局域世界演化网络能够在保持鲁棒性的同时，提高网络对恶意攻击的抗能够在保持鲁棒性的同时，提高网络对恶意攻击的抗脆弱性。脆弱性。第37页，此课件共57页哦第38页，此课件共57页哦第39页，此课件共57页哦五、复杂网络中各因子与完全五、复杂网络中各因子与完全同步的关系同步的关系 由前面的分析指导最近邻耦合网络在由前面的分析指导最近邻耦合网络在 时不可能达到同时不可能达到同步，但是通过加入少量的长程边将网络的平均路径明显缩短，步，但是通过加入少量的长程边将网络的平均路径明显缩短，太的同步化能力便会有明显提高。太的同步化能力便会有明

42、显提高。问题：问题：是不是由于平均路径的缩短提高了复杂网络的同步化能力是不是由于平均路径的缩短提高了复杂网络的同步化能力呢？呢？复杂网络中其他结构特性对网络的同步起到了什么作用复杂网络中其他结构特性对网络的同步起到了什么作用？究竟是哪些网络基本参数对于提高网络同步化能力起到究竟是哪些网络基本参数对于提高网络同步化能力起到了关键性作用？了关键性作用？。第40页，此课件共57页哦 复杂动态网络有许多基本参数，如特征根及其比率，复杂动态网络有许多基本参数，如特征根及其比率，平均路径长度，节点度及其分布、介数和同类匹配系平均路径长度，节点度及其分布、介数和同类匹配系数等，它们对各种网络的同步化能力都有

43、不同程度的数等，它们对各种网络的同步化能力都有不同程度的影响。这里主要介绍它们对小世界网络和无标度网路影响。这里主要介绍它们对小世界网络和无标度网路同步化能力的影响。同步化能力的影响。这里只考虑类型这里只考虑类型连续时间动态网络。由类型连续时间动态网络。由类型网络的同网络的同步判据可知：步判据可知：值越大，网络的同步化能力越差。值越大，网络的同步化能力越差。第41页，此课件共57页哦1.1.连接概率连接概率()()和幂律指数和幂律指数()()1 1）和和 对同步化性能的影响对同步化性能的影响 对于小世界网络，当加边或重连概率对于小世界网络，当加边或重连概率 不断变化时，不断变化时，对应地会产生

44、多个具有不同基本特性的小世界模型；同对应地会产生多个具有不同基本特性的小世界模型；同样，对于无标度网络，当幂律指数样，对于无标度网络，当幂律指数 不断变化时，也会不断变化时，也会得到多个不同的无标度网络模型。下面我们就研究由这得到多个不同的无标度网络模型。下面我们就研究由这两个参数两个参数 和和 不断变化而产生的不同网络模型，它们不断变化而产生的不同网络模型，它们的同步化性能与网络基本特性之间的关系。的同步化性能与网络基本特性之间的关系。第42页，此课件共57页哦小世界网络小世界网络 就小世界网络而言，由前面分析小世界网络的同步化稳就小世界网络而言，由前面分析小世界网络的同步化稳定性可以知道，

45、随着网络进行定性可以知道，随着网络进行“小世界小世界”的操作的操作(不断的加不断的加入长城边或不断重新连边入长城边或不断重新连边)，网络的特征根比率会随之减少，网络的特征根比率会随之减少，即随着加边或重连概率即随着加边或重连概率 的增加，的增加，随之减少。如图：随之减少。如图：这说明小世界网络的同步化能这说明小世界网络的同步化能 力随着力随着“小世界小世界”操作（概率操作（概率p p 增加）而增强。增加）而增强。N=2000 N=2000，100100实验的平均值。实验的平均值。特征根比率随连接概率p的变化曲线N/2第43页，此课件共57页哦无标度网络无标度网络 对于度分布为幂律形式对于度分布

46、为幂律形式 的无标度网络，的无标度网络，通过研究具有不同通过研究具有不同 值的无标度网络的同步化值的无标度网络的同步化性能时发现，值越大的网络，其性能时发现，值越大的网络，其 越小。越小。说明幂律指数说明幂律指数 越大对应越大对应 的无标度网络的同步化能的无标度网络的同步化能 力越强。力越强。第44页，此课件共57页哦2)2)和和 对于网络中各基本参数指标的影响对于网络中各基本参数指标的影响 下面分析网络中各基本特性指标随着下面分析网络中各基本特性指标随着 和和 的变化情况，从的变化情况，从而进一步得到网络性能指标对同步化性能的影响。而进一步得到网络性能指标对同步化性能的影响。小世界网络小世界

47、网络 小世界网络模型的一个显小世界网络模型的一个显 著特点是当加边或重连概著特点是当加边或重连概 率率 很小时，网络的平均很小时，网络的平均 路径长度有大幅度的下降路径长度有大幅度的下降 当当 时，平均路径时，平均路径 长度的变化不是很显著。长度的变化不是很显著。但是随着但是随着 的增加，小世的增加，小世 界网络的平均路径会减少。界网络的平均路径会减少。第45页，此课件共57页哦 虽然相对于具有幂律度分布的无标度网络来说，小世虽然相对于具有幂律度分布的无标度网络来说，小世界网络是均匀的，但是其网络中各节点所连接的边数并界网络是均匀的，但是其网络中各节点所连接的边数并不是完全相等的。因此，用方差

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

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

50、增加，同时平均度变小。就会增加，同时平均度变小。无标度网络的平均路径无标度网络的平均路径D D随随 变化的曲线变化的曲线 小图是网络平均度小图是网络平均度k k随随 变化的曲线变化的曲线第47页，此课件共57页哦 总结：由上述对小世界网络和无标度网络的分析总结：由上述对小世界网络和无标度网络的分析可以看到，小世界网络在最近邻耦合网络的基础上通可以看到，小世界网络在最近邻耦合网络的基础上通过过“小世界操作小世界操作”，使得网络的平均路径长度减小，使得网络的平均路径长度减小，同时也增加了网络节点的度分布的非均匀性以及最大同时也增加了网络节点的度分布的非均匀性以及最大的度，从而同步化能力有了显著提高