复杂网络的同步1210

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,复杂网络的同步,2010-12-11,1,一、同步现象举例,1665,年，物理学家惠更斯,发现：并排挂在墙上的两个,钟摆不管从什么不同的初始,位置出发，经过一段时间以后会出现同步摆动的现象。,1680,年，荷兰旅行家肯普弗在,泰国,旅行时,观察到了一个奇特的,现象：停在同一棵树上的萤火虫,有时候同时闪光又同时不闪光，,很有规律而且在时间上很准确。,这两个例子表现的就是现实,世界中的同步现象。,2,当一场精彩的戏剧演出结束时，人们的掌声从三三两两，到大家都按着共同的节奏鼓掌。,在我们的心脏中，无数的心脏细胞同步震荡着，他们同时做着一个动作，使心瓣膜舒张开，然后又一下子同时停下来，心瓣膜就收缩了。,同步在激光系统、超导材料和通信系统等领域中起着重要的作用。,有些同步时有害的。,如：,2000,年伦敦千年桥落成，当成千上万的人们开始通过大桥时，共振使大桥开始振动。桥体的,S,形振动所引起的偏差甚至达到了,20cm,，使得桥上的人们开始恐慌，大桥不得不临时关闭。,Internet,上也有一些对网络性能不利的同步想象。如：,Internet,网上的每个路由器都要周期性地发布路由消息。尽管每个路由器都是自己决定它什么时候发布路由信息，但是研究人员发现不同的路由器最终会以同步的方式发送路由消息，从而引发网络交通阻塞。,3,实际上，在物理学，数学和理论生物等领域，耦合动力学系统中的同步现象已经研究了很多年。,（,1967,年，,Winfree,开创性的工作）假设每个振子只与它周围有限个振子之间存在着强力作用（忽略振子的振幅变化），这样将同步问题转化成研究相位变化的问题。,Kuramoto,认为，一个具有有限个恒等振子的耦合系统，无论系统内部各振子间的耦合强度,多么,微弱，其动力学特性都可由一个简单的相位方程表示,。,20,世纪，工作,大多数,集中在具有规则拓扑形状的网络结构上，例：耦合映象格子（全耦合或最近邻耦合等）和细胞神经网络等。人们重点研究网络节点的非线性动力学所产生的复杂行为。缺点：没有考虑网络结构,复杂性,对网络动态行为的影响。,4,然而网络的拓扑结构在决定网络动态特征方面起到很,重要的作用。例如,，,Wu C W,的结果表明：在一定条件,下，足够强的耦合可以导致网络中节点间的同步现象。,缺点：无法解释弱耦合情况下，许多复杂网络仍出现较,强的同步现象。,各种复杂网络共有的小世界和无标度特性的发现，,使得人们开始关注网络的拓扑结构与网络同步化行为之,间的关系。,5,二、同步的基本概念,(,精确,),同步：两个或多个动力学系统，除了自身的演化外，其间还有相互作用（耦合），这种作用既可以是单向的，也可以是双向的。当满足一定条件时，在耦合的影响下，这些系统的状态输出就会逐渐趋同进而完全相等，称为同步（精确同步）。,广义的同步还包括相同步和频率同步等等。,复杂系统中的同步主要有两大类：完全同步和广义同步，前者两个相同单元研究得比较多，两个不同单元研究得比较少；后者包括部分同步，如相同步、滞后同步、频率同步等。两个不同单元的同步研究更具挑战性，是今后一个重要研究方向。,6,三、复杂网络的完全同步判据,1.,数学描述,首先介绍一般连续时间耦合网络的完全同步问题。,设连续时间耗散耦合动态网络中有 个相同的节点，,其中第 个节点的状态变量为：,单个节点满足的状态方程是：,多个节点的耦合动态网络中， 的状态方程是：,（,1,）,其中： 是定义好的函数（通常是非线性的）常数,为网络的耦合强度；,7,1,节点状态变量之间的内部耦合函数，也称为节点的输出函数，这里假设每个节点的输出函数是相同的。,所谓耗散耦合是指,耦合矩阵,满足耗散耦合条件 。当所有的节点状态都相同时，（,1,）式右端的耦合项自动消失。,如果在动态网络（,1,）中，当 时有：,（,2,）,则称网络达到完全（渐进）同步。,这里， 称为网络状态空间中的同步流形。,当同步实现后，记其结果为：,（,3,）,这里 称为同步状态。,8,2.,同步的判定,对状态方程（,1,），关于同步状态 做线性化，令 为第 个节点状态向量的变分，则可以得到变分方程：,（,4,）,这里， 和 分别是 和 关于 的,Jacobi,矩阵，通常要求为无界。令： 则上式可以写成矩阵方程：,（,5,）,做分解,其中 ，而 是矩阵 的特征根且 。,9,令 ，则有：,(6),判断同步流形稳定的一个常用判据是要求方程（,6,）的横截,lyapunov,指数,全为负值。,在方程（,6,）中，只有 和 与 相关，并考虑到外耦合矩阵,A,为非对称阵时，其特征值可能为复数，故定义主稳定方程为：,其最大,lyapunov,指数 是变量 和 的函数，称为动力网络的主稳定函数。,10,给定一个耦合强度 对于每一个固定的,在 复平面上可以对应地找到固定的一点 ，该,点所对应的 正负号反应了该特征模态的稳定性,（负时稳定，正时不稳定）。如果与,对应的所有特征模态都稳定，那么就认为在该耦合强,度下整个网络的同步流形是渐进稳定的。,11,无权无向连通的简单网络的外耦合矩阵,A,的特征根均为实数，不妨排列为,这时其主稳定方程（,6,）变为,并且其对应的主稳定函数 是实参数 的函数。使得主稳定函数 为负的 的取值范围 称为动态网络（,1,）的同步化区域，主要由孤立节点上的动力学函数 ，耦合强度 以及外耦合矩阵 和内耦合矩阵函数,确定。如果耦合强度 与每个外耦合矩阵 的每个负值的特征值之积都属于同步化区域，即：,那么同步流形是渐进稳定的。,12,3.,网络分类,根据同步化区域 可以把连续时间复杂动态网络（,1,）分为以下几种类型：,1,）类型,网络,对应的同步化区域为 ，其中 。若网络耦合强度和外耦合矩阵的特征值满足 ，即满足同步判据,：,那么类型,网络的同步流形是渐进稳定的。因此，类型,网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵 的第二大特征值 来刻画： 值越小，其同步化能力越强。,13,2,）类型,网络,对应的同步化网络区域 ，其中,。若网络耦合强度和耦合矩阵的特征值满足 和 ，即满足同步判据条件,：,或者,那么，类型,网络的同步流形是渐进稳定的。因此，类型,网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵,的特征值的比率,来刻画：,值越小，其同步化能力越强。,3,）类型,网络,对应的同步化区域为 。对于任意 的耦合强度和外耦合矩阵 ，这类网络都无法实现同步。,14,注意：一个给定的复杂动态网络,(1),属于上述三种类型中的哪一种是由该网络的孤立节点的动力学函数 和网络的内外耦合函数 和 确定的。尽管同步判据,和,之间的精确关系目前还不十分清楚，但是它们并不矛盾。此外，假设网络是连通的，那么只要网络的耦合强度充分大，类型,网络是一定可以实现同步的；而只有当耦合强度属于一定范围内时类型,网络才能实现同步，也就是说，太弱或太强个耦合强度都会使类型,网络无法实现同步。这里，同步判据,和,的值一般可以通过数值计算来估计。,15,四、复杂动力网络的完全同步,1,、规则网络的完全同步,1,）类型,网络,类型,网络的同步化能力由耦合矩阵 的第二大特征值 确定,。,最近邻耦合网络,对于节点度为（偶数）,K,的最近邻耦合动态网络（,1,）而言，它对应的耦合矩阵 是一个特殊的循环矩阵，其第二大特征值为：,在一般情况下，对于任意,K,，当网络规模 时，,单调上升趋于零，意味着当网络规模很大时，最近邻耦合网络很难或无法达到同步,16,全局耦合网络,全局耦合网络对应的耦合矩阵为：,它除了零特征根外，其余的特征根均 。因此，当网络的规模,时， 单调下降趋于无穷，说明网络很容易达到同步。,17,星形网络,星形网络对应的耦合矩阵是：,它的第二大特征根为：,， 与网络的规模无,关，故同步化能力与网,络规模无关。,18,对于连续时间耗散耦合的类型,动态网络式,(1),，可以得到一下结论：,(1),对给定的耦合强度 ，不管它有多大，当网络规模充分大时，最近邻耦合网络无法达到同步。,(2),对给定的非零耦合强度 ，不管它有多小，只要网络规模充分大，全局耦合网络必然可以达到同步。,(3),星形耦合网络的同步能力与网络的规模无关，即当耦合强度大于一个与网络规模无关的临界值时，星形网络可以实现同步。,19,2,）类型,网络,类型,网络的同步能力由外耦合矩阵 的最小特征值与第二大特征值之比 确定。,最近邻耦合网络,对于节点度为（偶数）,K,的最近邻耦合动态网络（,1,）而言，它对应的耦合矩阵 的特征值满足：,当网络节点 很大时，这个特征根的比,很大，因而网络的同步化能力很差。,20,全局耦合网络,全局耦合网络对应的外耦合矩阵的最小特征值和第二大特征值均为 。因此，由前面关于类型,网络的描述可知，只要 ，该网络就可以到达同步。,星形耦合网络,星形耦合网路对应的外耦合矩阵的最小特征值和第二大特征值之比为 。因此，当网络规模 时，此比值也趋于无穷，该网络无法达到同步。,21,由以上分析，对连续时间耗散耦合的类型网络,动态网络,(1),，可以得到以下结论：,(1),对给定的耦合强度 ，不管它有多大，当网络规模充分大时，最近邻耦合网络和星形网络都无法达到同步。,(2),全局耦合网络的同步化能力与网络规模无关，只要 ，全局耦合网络就可以达到同步。,22,2.,小世界网络的完全同步,只针对类型,网络讨论。考虑具有,NW,小世界拓扑结构的连续时间耦合动态网络系统式,(1),的同步化能力。,NW,小世界网络的生成规则：, 初始：最近邻耦合网络, 随机化加边：以 概率在随机选取的一对节点之间加上一条边,即：这种以概率,加边过程就相当于在最近邻耦合矩阵中的,0,元素，以概率,置换为,1,，因此将最近邻耦合矩阵 中的 的元素，以概率 置换为,重新计算其对角线元素，这样得到,NW,小世界网络的耦合矩阵，记为： 令 是对应的第二大特征根,23,左图分别给出 和 的情,形下,具有不同加边概率,的,NW,小世,界网络模型对应的,第二大特征根 。, 对于最近邻网络,(,),近似为,0,，此时网络的同步化能力很低。, 在此基础上不断地随机加边（概率,从,0,变化到,1,）,不断变小最,后趋于,，同步化能力不断加强。,结论,1,：对于任意给定的耦合强度,当有足够多的节,点个数,，只要概率,大于一定的阈值，该网,络就会达到同步。,2,2,N=200,N=500,24,左图分别给出 和 的情,形下,具有不同规模的,NW,小世界网络,模型对应的,第二大特征根 。, 对于规模较小最近邻网络,近似为,0,，此时网络的同步,化能力很低。, 在此基础上不断地增加规模，,不断变小，同步化能力不断加强。,结论,2,：在加边概率相同的情况下，规模越大的,NW,小世界网络的同步化能力越强。,2,2,p=0.05,p=0.1,25,3.,无标度网络的完全同步,1,）无标度网络的完全同步,考虑,BA,无标度拓扑的连续时间耦合动态网络式,(1),的同步化能力。这里同样只讨论类型,网络。,BA,无标度网络的生成规则：,a.,增长：从一个具有 个节点的网络开始，每次引,入一个新的节点，并且连到,个已存在的节点上，,b.,优先连接：一个新节点与一个已经存在节点,相连,接的概率 与节点,的度 、节点 的度 之间满足如,下关系：,26,构造,BA,无标度网络时，令,耦合矩阵为,是,其第二大特征根。通过仿真发现：,随着,的增加而下降，并且当,趋,于无穷时， 趋于一个负常,数，左图是对不同的,和,，计算,模拟相应的 。,当 时，对应有：,结论：在网络规模,比较大时，继续增加新的节点不会,使,BA,网络的同步化能力下降。,2,27,2),同步最优网络,由上可知：在几种规则网络、,NW,小世界网络和,BA,无标度网络中，全局耦合网络的同步化能力最强，但要构成的边数却要最多。,问题：,如果对于边数相同的网络，什么样拓扑结构的网络同步,化能力最强？,BA,无标度网络是不是同步化性能最佳的增长网络模型？,有没有一个增长网络模型的同步化性能比它还好？,因此提出了一个新的网络增长模型,-,同步最优网络,模型。,28,同步最优网络模型的生成规则如下：,增长：,从一个具有,个节点的网络开始，每次引入一个新的节点，并将其连接到 个已存在的节点上。,同步最优连接：新节点与已存在的节点,相连接时，要使得构成的新网络的同步化性能最优，即要使得新网络耦合矩阵的第二大特征根最小。,这样，经过,步后，产生一个具有 个节点，,条边的同步网络。这个网络在其生长过程中，每一步都达到同步化性能最优。,同步最优网络模型分析：,优点：与,BA,无标度网络相比，同步最优网络模型的,第二大特征根有显著的下降，即：同步化性能有了明,显的提高。,29,如：当 时，对应有：,缺点：分析同步最优网络的节点度分布时还发现，同,步最优网络的拓扑结构类似于多中心网络模型：有极,少量的节点与大量节点连接，而大部分节点的连接度,很小。这使得虽然同步最优网络的同步化性能要比,BA,无标度网络的同步化性能强，但由于存在极少量的“,集散”点（远小于,BA,无标度网络中的“集散”点的个,数），这样，在恶意攻击下它要比,BA,无标度网络更容,易崩溃，对抗恶意攻击更为脆弱。,30,3),同步优先网络,虽然同步最优网络模型的同步化能力有了很大提高，,但是对于恶意攻击非常脆弱。一种改进的模型是对于,随机去节点和恶意攻击都很鲁棒的同步优先网络模型,基于增长和同步优先两种机制生成。,同步优先网络的生成规则如下：,增长：初始时有,个节点，在每一时间步内加入一,个新的节点,并将其连接到 个已存在的节点上；,同步优先连接：新节点与原有节点,相连的概率,和,新节点与第,个节点连接后构成的新网络同步化能力有,关,.,31,即：,这样，经过 步后，产生一个具有,个节点，,条边的同步优先网络模型。对于特定的 值，当 趋于无穷时，网络的第二大特征值也趋于,一个负常数 。,例如：当 时，对应的,32,三种网络同步化能力的比较：,无标度网络与,同步优先网络的同步化能,力非常类似，后者稍逊色,于前者。, 同步最优网络的同步化,能力最强。,33,4),无标度网络的鲁棒性和脆弱性,当网络发生随机故障时，相当于从网络中随机去除,部分节点，由于无标度网络的极度不均匀性，此时去,除的节点大多数都是度很小的节点。因此， ，,网络的同步化能力基本上保持不变。,34,当网络受到恶意攻击时，这时被特定去掉的那一部,分都是度很大的节点。因此，整个网络的连通性发生,了剧烈变化，甚至于网络被分成若干不连通的分支，,并且 ，从而，网络的同步化能力大大地降,低甚至丧失了。,35,4,、局域世界演化网络模型的完全同步,局域世界演化模型的生成规则：,增长：网络初始时有 个节点和 条边，每次加入一个节点和附带的 条边。,局域世界有线连接：随即的从网络已有的节点中选取 个节点,( ),作为新加入的节点的局域世界。新加入的节点根据优先连接概率：,来选择局域世界中的,m,各节点相连，其中,LW,是由新选,的,M,个节点组成。,36,对于每一个新加入的节点，它的局域世界都是随,机的从网络中挑选构成，其连接度决定了网络的非均,匀性，并且度分布在指数和幂律之间的过渡。因此，,在这种局域世界演化网络中，,Hub,节点的数目通常要,比无标度网络的少，因而度分布也要比无标度网络更,均匀。因此，当面对随机故障的和恶意攻击时，局域,世界演化网络的同步鲁棒性和脆弱性也就介于无标度,网络和指数网络之间。,一般来说，与无标度网络相比，局域世界演化网络,能够在保持鲁棒性的同时，提高网络对恶意攻击的抗,脆弱性。,37,38,39,五、复杂网络中各因子与完全,同步的关系,由前面的分析指导最近邻耦合网络在 时不可能达到同步，但是通过加入少量的长程边将网络的平均路径明显缩短，太的同步化能力便会有明显提高。,问题：,是不是由于平均路径的缩短提高了复杂网络的同步化能力呢？,复杂网络中其他结构特性对网络的同步起到了什么作用？,究竟是哪些网络基本参数对于提高网络同步化能力起到了关键性作用？,。,40,复杂动态网络有许多基本参数，如特征根及其比率，,平均路径长度，节点度及其分布、介数和同类匹配系,数等，它们对各种网络的同步化能力都有不同程度的,影响。这里主要介绍它们对小世界网络和无标度网路,同步化能力的影响。,这里只考虑类型,连续时间动态网络。由类型,网络的同步判据可知： 值越大，网络的同步化能力越差。,41,1.,连接概率,( ),和幂律指数,( ),1,） 和 对同步化性能的影响,对于小世界网络，当加边或重连概率 不断变化时，,对应地会产生多个具有不同基本特性的小世界模型；同,样，对于无标度网络，当幂律指数 不断变化时，也会,得到多个不同的无标度网络模型。下面我们就研究由这,两个参数 和 不断变化而产生的不同网络模型，它们,的同步化性能与网络基本特性之间的关系。,42,小世界网络,就小世界网络而言，由前面分析小世界网络的同步化稳定性可以知道，随着网络进行“小世界”的操作,(,不断的加入长城边或不断重新连边,),，网络的特征根比率会随之减少，即随着加边或重连概率 的增加，,随之减少。如图：,这说明小世界网络的同步化能,力随着“小世界”操作（概率,p,增加）而增强。,N=2000,，,100,实验的平均值。,特征根比率随连接概率,p,的变化曲线,N,/,2,43,无标度网络,对于度分布为幂律形式,的无标度网络，通过研究具有不同 值的无标度网络的同步化性能时发现，值越大的网络，其 越小。,说明幂律指数 越大对应,的无标度网络的同步化能,力越强。,44,2),和 对于网络中各基本参数指标的影响,下面分析网络中各基本特性指标随着 和 的变化情况，从而进一步得到网络性能指标对同步化性能的影响。,小世界网络,小世界网络模型的一个显,著特点是当加边或重连概,率 很小时，网络的平均,路径长度有大幅度的下降,当 时，平均路径,长度的变化不是很显著。,但是随着 的增加，小世,界网络的平均路径会减少。,45,虽然相对于具有幂律度分布的无标度网络来说，小世界网络是均匀的，但是其网络中各节点所连接的边数并不是完全相等的。因此，用方差指标：,来表示节点度的分布，则 值越大说明网络中节点度分布范围越大，并有度较大的节点出现，这时网络的度分布变的均匀。由上图的曲线可以看出随着概率 的增加，网络变的更加非均匀；同时无论是新加入的长程边（,NW,小世界）或是重新连接长程边（,WS,小世界），网络中度的最大值都会增加。,46,无标度网络,对于具有幂律分布 的无标度网络模型，用节点的标准偏差 来衡量网络的非均匀性，则 值越大 反而下降，说明网络中节点度的分布越均匀。在无标度网络中，少数具有度非常大的节点将大量的度很小的节点连接在一起，因此这些度大的节点使得网络的平均路径很短。而随着 值的增大网络度分布变的比较均匀，因此网络的平均路径就会增加，同时平均度变小。,无标度网络的平均路径,D,随,变化的曲线,小图是网络平均度,k,随变化的曲线,47,总结：由上述对小世界网络和无标度网络的分析,可以看到，小世界网络在最近邻耦合网络的基础上通,过“小世界操作”，使得网络的平均路径长度减小，,同时也增加了网络节点的度分布的非均匀性以及最大,的度，从而同步化能力有了显著提高；而对于无标度,网络却有了相反的结论，即只有提高网络的均匀性，,增大平均路径长度或减小网络的平均度，才能使得无,标度网络的同步化性能提高。因此，单纯用度的大小,、度分布、或平均路径长度等指标都无法统一表征复,杂网络的同步化能力。,48,2.,介数,某个节点的介数越大说明在信息传播过程中的信,息量也会越多，于是也就越容易发生信息堵塞。研究,发现，无论是小世界网络还是无标度网络，节点的最,大介数值都会随着概率 和参数 的增加而减小。这说,明，介数是一个相对能够统一反映网络同步化能力的,参数。,最大介数,B,max,随连接概率,p,的变化图,49,假设在两组高度连接的子网络之间只有少数的节,点相连，那么这几个少数节点的介数就会很大，会有,过多的信息经过这几个节点而造成过载从而丢失信息,。因此最大介数值变化会降低网络的同步化能力。,为了进一步验证这一结论，现在将小世界网络模,型中具有最大介数 的节点去掉。这样原本大量从,该节点经过的同步流形信息会分散到其他的节点上。,用参数：,来表示去除节点前后网络同步化性能的变化。,50,仿真实验表明：无论 为何值,的小世界网络，当具有 的,节点被去掉以后，特征根比,率均会下降,( ),从而网络,的同步化性能显著提高；相,反，如果随机去除一个节点,，特征根的比率前后没有很,大变化，说明介数不大的节点对整个网络同步化性能的影响不是很大。,51,3.,影响网络同步化能力的其他因素,(1),节点的度分布、平均路径长度以及同类匹配系数这类指标的变化会对小世界网络和无标度网络的同步化性能造成不同的影响，其中具体的原因仍需进一步探讨。,(2),网络的社团结构和同型混合等特征也都可能会影响网络的同步化能力。因此，如何进一步从本质上刻画影响网络同步化性能的因素是一个值得研究的课题。,52,六、网络模体的同步,上面讨论的是整个网络的同步，下面研究网络模体的同步。,模体：网络中出现频率较高的子图。,(,和同一网络的完全随机化形式相比较而言,),随着耦合强度,c,的增加，产生同步的概率,P,sync,也随着增加。,定义参数,c*,：,c*,为当,P,sync,1/2,时的,c,值。,显然,:,不同模体对应的,c*,也不相同。模体的,c*,越小，说明它越容易达到同步。,当模体的规模固定时，不同的连接方式决定了不同模体结构的不同同步阈值。（见图和表）,53,5,种不同模体结构同步的,概率值,重复,1000,次,54,55,对于模体,4,，,6,，,9,，它们,都是由四个节点构成，,但,连接,节点的,方式,不同，,结果是它们的,c*,差别很大。, 模体,内部,的,连接,越多，,c*,值就越小,c*,模体,4,6,9,不同模体结构对应的,概率,P,sync,1/2,模体同步,的耦合强度值,55,表示网络的拓扑结构，当 表示一个无权无向简单图的拓扑结构时，具体定义如下：,如果节点 和 之间存在连接，则 ，否则,。耗散耦合表示为：,其中， 为节点 的度数。,矩阵 的一些特殊性质：,1.,是实对称矩阵，且满足每行元素之和为零。每行元素之和为零这一性质也成为耗散性，具有耗散性的矩阵称为耗散矩阵。,2.,矩阵的对角元素为负数，非对角元素为非负数。,3.,只有一个特征值为,0,，其他特征值都为负数。,56,变分法是处理函数的函数的数学领域，和处理数的函数的微积分是相对的。,对于一个,n,个变量的动力系统。选一个点，并取一个中心在该点的一个小的,n,维的球，随着时间的增加，球将变形成为一个近似椭球；在球的半径趋于零的极限情况下，映象保持与椭球相同的时间将趋向于无穷大。,在一次迭代中（对于映射来说）或一个单位时间中（对于流来说）椭球的轴长增加的倍数的长期平均值，称为,Lyapunov,数，其对数称为,Lyapunov,指数。一个正,Lyapunov,指数意味着在系统相空间中，无论初始的两条轨线的间距多么小，其差别会随着时间的演化而成指数率的增加，以致达到无法预测，这就是混沌现象。,57,