《最新复杂网络的同步1210幻灯片》由会员分享,可在线阅读,更多相关《最新复杂网络的同步1210幻灯片(58页珍藏版)》请在金锄头文库上搜索。
1、复杂网络的同步复杂网络的同步12101210一、同步现象举例一、同步现象举例 1665 1665年,物理学家惠更斯年,物理学家惠更斯发现:并排挂在墙上的两个发现:并排挂在墙上的两个钟摆不管从什么不同的初始钟摆不管从什么不同的初始位置出发,经过一段时间以后会出现同步摆动的现象。位置出发,经过一段时间以后会出现同步摆动的现象。 1680 1680年,荷兰旅行家肯普弗在年,荷兰旅行家肯普弗在泰国泰国旅行时旅行时观察到了一个奇特的观察到了一个奇特的现象:停在同一棵树上的萤火虫现象:停在同一棵树上的萤火虫有时候同时闪光又同时不闪光,有时候同时闪光又同时不闪光,很有规律而且在时间上很准确。很有规律而且在时
2、间上很准确。 这两个例子表现的就是现实这两个例子表现的就是现实世界中的同步现象。世界中的同步现象。2.2.同步的判定同步的判定 对状态方程(对状态方程(1 1),关于同步状态),关于同步状态 做线性化,令做线性化,令 为第为第 个节点状态向量的变分,则可以得到变分方程:个节点状态向量的变分,则可以得到变分方程: (4 4)这里,这里, 和和 分别是分别是 和和 关于关于 的的JacobiJacobi矩矩阵,通常要求为无界。令:阵,通常要求为无界。令: 则上式可以则上式可以写成矩阵方程:写成矩阵方程: (5 5)做分解做分解 , ,其中其中 ,而,而 是是矩阵矩阵 的特征根且的特征根且 。令令
3、,则有:,则有: (6) (6) 判断同步流形稳定的一个常用判据是要求方程(判断同步流形稳定的一个常用判据是要求方程(6 6)的横截的横截lyapunovlyapunov指数指数全为负值。全为负值。 在方程(在方程(6 6)中,只有)中,只有 和和 与与 相关,并考虑到相关,并考虑到外耦合矩阵外耦合矩阵A A为非对称阵时,其特征值可能为复数,故为非对称阵时,其特征值可能为复数,故定义主稳定方程为:定义主稳定方程为:其最大其最大lyapunovlyapunov指数指数 是变量是变量 和和 的函数,称为动的函数,称为动力网络的主稳定函数。力网络的主稳定函数。 给定一个耦合强度给定一个耦合强度 对于
4、每一个固定的对于每一个固定的在在 复平面上可以对应地找到固定的一点复平面上可以对应地找到固定的一点 ,该,该点所对应的点所对应的 正负号反应了该特征模态的稳定性正负号反应了该特征模态的稳定性(负时稳定,正时不稳定)。如果与(负时稳定,正时不稳定)。如果与 对应的所有特征模态都稳定,那么就认为在该耦合强对应的所有特征模态都稳定,那么就认为在该耦合强度下整个网络的同步流形是渐进稳定的。度下整个网络的同步流形是渐进稳定的。 无权无向连通的简单网络的外耦合矩阵无权无向连通的简单网络的外耦合矩阵A A的特征根均为的特征根均为实数,不妨排列为实数,不妨排列为这时其主稳定方程(这时其主稳定方程(6 6)变为
5、)变为并且其对应的主稳定函数并且其对应的主稳定函数 是实参数是实参数 的函数。使得的函数。使得主稳定函数主稳定函数 为负的为负的 的取值范围的取值范围 称为动态网络称为动态网络(1 1)的同步化区域,主要由孤立节点上的动力学函数)的同步化区域,主要由孤立节点上的动力学函数 ,耦合强度,耦合强度 以及外耦合矩阵以及外耦合矩阵 和内耦合矩阵函数和内耦合矩阵函数 确定。如果耦合强度确定。如果耦合强度 与每个外耦合矩阵与每个外耦合矩阵 的每个的每个负值的特征值之积都属于同步化区域,即:负值的特征值之积都属于同步化区域,即:那么同步流形是渐进稳定的。那么同步流形是渐进稳定的。3.3.网络分类网络分类 根
6、据同步化区域根据同步化区域 可以把连续时间复杂动态网络可以把连续时间复杂动态网络(1 1)分为以下几种类型:)分为以下几种类型:1 1)类型)类型网络网络 对应的同步化区域为对应的同步化区域为 ,其中,其中 。若网络耦合强度和外耦合矩阵的特征值满足若网络耦合强度和外耦合矩阵的特征值满足 ,即满足同步判据即满足同步判据:那么类型那么类型网络的同步流形是渐进稳定的。因此,类型网络的同步流形是渐进稳定的。因此,类型网络关于拓扑结构的同步化能力可以用对应的外耦合网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵矩阵 的第二大特征值的第二大特征值 来刻画:来刻画: 值越小,其同步化值越小,其同步化能力越
7、强。能力越强。2 2)类型)类型网络网络 对应的同步化网络区域对应的同步化网络区域 ,其中,其中 。若网络耦合强度和耦合矩阵的特征。若网络耦合强度和耦合矩阵的特征值满足值满足 和和 ,即满足同步判据条件,即满足同步判据条件: 或者或者 那么,类型那么,类型网络的同步流形是渐进稳定的。因此,网络的同步流形是渐进稳定的。因此,类型类型网络关于拓扑结构的同步化能力可以用对应的网络关于拓扑结构的同步化能力可以用对应的外耦合矩阵外耦合矩阵 的特征值的比率的特征值的比率 来刻画:来刻画: 值越小,其同步化能力越强。值越小,其同步化能力越强。3 3)类型)类型网络网络 对应的同步化区域为对应的同步化区域为
8、。对于任意。对于任意 的耦合的耦合强度和外耦合矩阵强度和外耦合矩阵 ,这类网络都无法实现同步。,这类网络都无法实现同步。 注意:一个给定的复杂动态网络注意:一个给定的复杂动态网络(1)(1)属于上述三种属于上述三种类型中的哪一种是由该网络的孤立节点的动力学函数类型中的哪一种是由该网络的孤立节点的动力学函数 和网络的内外耦合函数和网络的内外耦合函数 和和 确定的。尽管同步判确定的。尽管同步判据据和和之间的精确关系目前还不十分清楚,但是它之间的精确关系目前还不十分清楚,但是它们并不矛盾。此外,假设网络是连通的,那么只要网们并不矛盾。此外,假设网络是连通的,那么只要网络的耦合强度充分大,类型络的耦合
9、强度充分大,类型网络是一定可以实现同网络是一定可以实现同步的;而只有当耦合强度属于一定范围内时类型步的;而只有当耦合强度属于一定范围内时类型网网络才能实现同步,也就是说,太弱或太强个耦合强度络才能实现同步,也就是说,太弱或太强个耦合强度都会使类型都会使类型网络无法实现同步。这里,同步判据网络无法实现同步。这里,同步判据和和的值一般可以通过数值计算来估计。的值一般可以通过数值计算来估计。四、复杂动力网络的完全同步四、复杂动力网络的完全同步1 1、规则网络的完全同步、规则网络的完全同步 1 1)类型)类型网络网络 类型类型网络的同步化能力由耦合矩阵网络的同步化能力由耦合矩阵 的第二大特的第二大特征
10、值征值 确定确定。 最近邻耦合网络最近邻耦合网络 对于节点度为(偶数)对于节点度为(偶数)K K的最近邻耦合动态网络的最近邻耦合动态网络(1 1)而言,它对应的耦合矩阵)而言,它对应的耦合矩阵 是一个特殊的循环是一个特殊的循环矩阵,其第二大特征值为:矩阵,其第二大特征值为:在一般情况下,对于任意在一般情况下,对于任意K K,当网络规模,当网络规模 时,时, 单调上升趋于零,意味着当网络规模很大时,最近邻单调上升趋于零,意味着当网络规模很大时,最近邻耦合网络很难或无法达到同步耦合网络很难或无法达到同步全局耦合网络全局耦合网络 全局耦合网络对应的耦合矩阵为:全局耦合网络对应的耦合矩阵为: 它除了零
11、特征根外,其余的特征根均它除了零特征根外,其余的特征根均 。因。因此,当网络的规模此,当网络的规模 时,时, 单调下降趋单调下降趋于无穷,说明网络很容易达到同步。于无穷,说明网络很容易达到同步。 星形网络星形网络 星形网络对应的耦合矩阵是:星形网络对应的耦合矩阵是: 它的第二大特征根为:它的第二大特征根为: , 与网络的规模无与网络的规模无 关,故同步化能力与网关,故同步化能力与网 络规模无关。络规模无关。对于连续时间耗散耦合的类型对于连续时间耗散耦合的类型动态网络式动态网络式(1)(1),可以,可以得到一下结论:得到一下结论:(1)(1)对给定的耦合强度对给定的耦合强度 ,不管它有多大,当网
12、络规模充,不管它有多大,当网络规模充分大时,最近邻耦合网络无法达到同步。分大时,最近邻耦合网络无法达到同步。(2)(2)对给定的非零耦合强度对给定的非零耦合强度 ,不管它有多小,只要网络,不管它有多小,只要网络规模充分大,全局耦合网络必然可以达到同步。规模充分大,全局耦合网络必然可以达到同步。(3)(3)星形耦合网络的同步能力与网络的规模无关,即当星形耦合网络的同步能力与网络的规模无关,即当耦合强度大于一个与网络规模无关的临界值时,星形网耦合强度大于一个与网络规模无关的临界值时,星形网络可以实现同步。络可以实现同步。2 2)类型)类型网络网络 类型类型网络的同步能力由外耦合矩阵网络的同步能力由
13、外耦合矩阵 的最小特的最小特征值与第二大特征值之比征值与第二大特征值之比 确定。确定。最近邻耦合网络最近邻耦合网络对于节点度为(偶数)对于节点度为(偶数)K K的最近邻耦合动态网络的最近邻耦合动态网络(1 1)而言,它对应的耦合矩阵)而言,它对应的耦合矩阵 的特征值满足:的特征值满足:当网络节点当网络节点 很大时,这个特征根的比很大时,这个特征根的比很大,因而网络的同步化能力很差。很大,因而网络的同步化能力很差。 全局耦合网络全局耦合网络全局耦合网络对应的外耦合矩阵的最小特征值和第全局耦合网络对应的外耦合矩阵的最小特征值和第二大特征值均为二大特征值均为 。因此,由前面关于类型。因此,由前面关于
14、类型网络网络的描述可知,只要的描述可知,只要 ,该网络就可以到达同步。,该网络就可以到达同步。星形耦合网络星形耦合网络 星形耦合网路对应的外耦合矩阵的最小特星形耦合网路对应的外耦合矩阵的最小特征值和第二大特征值之比为征值和第二大特征值之比为 。因此,当网。因此,当网络规模络规模 时,此比值也趋于无穷,该网时,此比值也趋于无穷,该网络无法达到同步。络无法达到同步。 由以上分析,对连续时间耗散耦合的类型网络由以上分析,对连续时间耗散耦合的类型网络动态网络动态网络(1)(1),可以得到以下结论:,可以得到以下结论:(1)(1)对给定的耦合强度对给定的耦合强度 ,不管它有多大,当网络规,不管它有多大,
15、当网络规模充分大时,最近邻耦合网络和星形网络都无法达模充分大时,最近邻耦合网络和星形网络都无法达到同步。到同步。(2)(2)全局耦合网络的同步化能力与网络规模无关,全局耦合网络的同步化能力与网络规模无关,只要只要 ,全局耦合网络就可以达到同步。,全局耦合网络就可以达到同步。2.2.小世界网络的完全同步小世界网络的完全同步 只针对类型只针对类型网络讨论。考虑具有网络讨论。考虑具有NWNW小世界拓扑结小世界拓扑结构的连续时间耦合动态网络系统式构的连续时间耦合动态网络系统式(1)(1)的同步化能力。的同步化能力。NWNW小世界网络的生成规则:小世界网络的生成规则: 初始:最近邻耦合网络初始:最近邻耦
16、合网络 随机化加边:以随机化加边:以 概率在随机选取的一对节点之间概率在随机选取的一对节点之间加上一条边加上一条边即:这种以概率即:这种以概率 加边过程就相当于在最近邻耦合矩加边过程就相当于在最近邻耦合矩阵中的阵中的0 0元素,以概率元素,以概率 置换为置换为1 1,因此将最近邻耦合,因此将最近邻耦合矩阵矩阵 中的中的 的元素,以概率的元素,以概率 置换为置换为 重新计算其对角线元素,这样得到重新计算其对角线元素,这样得到NWNW小世界网络的耦小世界网络的耦合矩阵,记为:合矩阵,记为: 令令 是对应的第二大是对应的第二大特征根特征根 左图分别给出左图分别给出 和和 的情的情 形下形下, ,具有
17、不同加边概率具有不同加边概率 的的NWNW小世小世 界网络模型对应的界网络模型对应的第二大特征根第二大特征根 。 对于最近邻网络对于最近邻网络( ( ), ), 近似为近似为0 0,此时网络的同步化能力很低。,此时网络的同步化能力很低。 在此基础上不断地随机加边(概率在此基础上不断地随机加边(概率 从从0 0变化到变化到1 1), , 不断变小最不断变小最 后趋于后趋于 ,同步化能力不断加强。,同步化能力不断加强。结论结论1 1:对于任意给定的耦合强度:对于任意给定的耦合强度 , ,当有足够多的节当有足够多的节点个数点个数 ,只要概率,只要概率 大于一定的阈值,该网大于一定的阈值,该网络就会达
18、到同步。络就会达到同步。 2 2N=200N=500 左图分别给出左图分别给出 和和 的情的情 形下形下, ,具有不同规模的具有不同规模的NWNW小世界网络小世界网络 模型对应的模型对应的第二大特征根第二大特征根 。 对于规模较小最近邻网络对于规模较小最近邻网络, , 近似为近似为0 0,此时网络的同步,此时网络的同步 化能力很低。化能力很低。 在此基础上不断地增加规模,在此基础上不断地增加规模, 不断变小,同步化能力不断加强。不断变小,同步化能力不断加强。结论结论2 2:在加边概率相同的情况下,规模越大的:在加边概率相同的情况下,规模越大的NWNW小世界网络的同步化能力越强。小世界网络的同步
19、化能力越强。 2 2p=0.05p=0.13.3.无标度网络的完全同步无标度网络的完全同步1 1)无标度网络的完全同步)无标度网络的完全同步 考虑考虑BABA无标度拓扑的连续时间耦合动态网络式无标度拓扑的连续时间耦合动态网络式(1)(1)的同步化能力。这里同样只讨论类型的同步化能力。这里同样只讨论类型网络。网络。 BA BA无标度网络的生成规则:无标度网络的生成规则:a. a. 增长:从一个具有增长:从一个具有 个节点的网络开始,每次引个节点的网络开始,每次引入一个新的节点,并且连到入一个新的节点,并且连到 个已存在的节点上,个已存在的节点上,b. b. 优先连接:一个新节点与一个已经存在节点
20、优先连接:一个新节点与一个已经存在节点 相连相连接的概率接的概率 与节点与节点 的度的度 、节点、节点 的度的度 之间满足如之间满足如下关系:下关系: 构造构造BABA无标度网络时,令无标度网络时,令 耦合矩阵为耦合矩阵为 , , 是是 其第二大特征根。通过仿真发现:其第二大特征根。通过仿真发现: 随着随着 的增加而下降,并且当的增加而下降,并且当 趋趋 于无穷时,于无穷时, 趋于一个负常趋于一个负常 数,左图是对不同的数,左图是对不同的 和和 ,计算,计算 模拟相应的模拟相应的 。当当 时,对应有:时,对应有:结论:在网络规模结论:在网络规模 比较大时,继续增加新的节点不会比较大时,继续增加
21、新的节点不会使使BABA网络的同步化能力下降。网络的同步化能力下降。22)2)同步最优网络同步最优网络由上可知:在几种规则网络、由上可知:在几种规则网络、NWNW小世界网络和小世界网络和BABA无标度无标度网络中,全局耦合网络的同步化能力最强,但要构成网络中,全局耦合网络的同步化能力最强,但要构成的边数却要最多。的边数却要最多。问题:问题:如果对于边数相同的网络,什么样拓扑结构的网络同步如果对于边数相同的网络,什么样拓扑结构的网络同步化能力最强?化能力最强?BABA无标度网络是不是同步化性能最佳的增长网络模型?无标度网络是不是同步化性能最佳的增长网络模型?有没有一个增长网络模型的同步化性能比它
22、还好?有没有一个增长网络模型的同步化性能比它还好? 因此提出了一个新的网络增长模型因此提出了一个新的网络增长模型-同步最优网络同步最优网络模型。模型。同步最优网络模型的生成规则如下:同步最优网络模型的生成规则如下:增长:增长:从一个具有从一个具有 个节点的网络开始,每次引入个节点的网络开始,每次引入一个新的节点,并将其连接到一个新的节点,并将其连接到 个已存在的个已存在的节点上。节点上。同步最优连接:新节点与已存在的节点同步最优连接:新节点与已存在的节点 相连接时,相连接时,要使得构成的新网络的同步化性能最优,即要使得要使得构成的新网络的同步化性能最优,即要使得新网络耦合矩阵的第二大特征根最小
23、。新网络耦合矩阵的第二大特征根最小。 这样,经过这样,经过 步后,产生一个具有步后,产生一个具有 个节点,个节点, 条边的同步网络。这个网络在其生长过程中,条边的同步网络。这个网络在其生长过程中,每一步都达到同步化性能最优。每一步都达到同步化性能最优。同步最优网络模型分析:同步最优网络模型分析: 优点:与优点:与BABA无标度网络相比,同步最优网络模型的无标度网络相比,同步最优网络模型的第二大特征根有显著的下降,即:同步化性能有了明第二大特征根有显著的下降,即:同步化性能有了明显的提高。显的提高。如:当如:当 时,对应有:时,对应有:缺点:分析同步最优网络的节点度分布时还发现,同缺点:分析同步
24、最优网络的节点度分布时还发现,同步最优网络的拓扑结构类似于多中心网络模型:有极步最优网络的拓扑结构类似于多中心网络模型:有极少量的节点与大量节点连接,而大部分节点的连接度少量的节点与大量节点连接,而大部分节点的连接度很小。这使得虽然同步最优网络的同步化性能要比很小。这使得虽然同步最优网络的同步化性能要比BABA无标度网络的同步化性能强,但由于存在极少量的无标度网络的同步化性能强,但由于存在极少量的“集散集散”点(远小于点(远小于BABA无标度网络中的无标度网络中的“集散集散”点的个点的个数),这样,在恶意攻击下它要比数),这样,在恶意攻击下它要比BABA无标度网络更容无标度网络更容易崩溃,对抗
25、恶意攻击更为脆弱。易崩溃,对抗恶意攻击更为脆弱。3)3)同步优先网络同步优先网络虽然同步最优网络模型的同步化能力有了很大提高,虽然同步最优网络模型的同步化能力有了很大提高,但是对于恶意攻击非常脆弱。一种改进的模型是对于但是对于恶意攻击非常脆弱。一种改进的模型是对于随机去节点和恶意攻击都很鲁棒的同步优先网络模型随机去节点和恶意攻击都很鲁棒的同步优先网络模型, ,基于增长和同步优先两种机制生成。基于增长和同步优先两种机制生成。同步优先网络的生成规则如下:同步优先网络的生成规则如下:增长:初始时有增长:初始时有 个节点,在每一时间步内加入一个节点,在每一时间步内加入一个新的节点个新的节点, ,并将其
26、连接到并将其连接到 个已存在的节点上;个已存在的节点上;同步优先连接:新节点与原有节点同步优先连接:新节点与原有节点 相连的概率相连的概率 和和新节点与第新节点与第 个节点连接后构成的新网络同步化能力有个节点连接后构成的新网络同步化能力有关关. .即:即: 这样,经过这样,经过 步后,产生一个具有步后,产生一个具有 个节点,个节点, 条边的同步优先网络模型。对于特定的条边的同步优先网络模型。对于特定的 值,当值,当 趋于无穷时,网络的第二大特征值也趋于趋于无穷时,网络的第二大特征值也趋于一个负常数一个负常数 。例如:当例如:当 时,对应的时,对应的三种网络同步化能力的比较:三种网络同步化能力的
27、比较: 无标度网络与无标度网络与同步优先网络的同步化能同步优先网络的同步化能力非常类似,后者稍逊色力非常类似,后者稍逊色于前者。于前者。 同步最优网络的同步化同步最优网络的同步化能力最强。能力最强。4)4)无标度网络的鲁棒性和脆弱性无标度网络的鲁棒性和脆弱性 当网络发生随机故障时,相当于从网络中随机去除当网络发生随机故障时,相当于从网络中随机去除部分节点,由于无标度网络的极度不均匀性,此时去部分节点,由于无标度网络的极度不均匀性,此时去除的节点大多数都是度很小的节点。因此,除的节点大多数都是度很小的节点。因此, ,网络的同步化能力基本上保持不变。网络的同步化能力基本上保持不变。当网络受到恶意攻
28、击时,这时被特定去掉的那一部当网络受到恶意攻击时,这时被特定去掉的那一部分都是度很大的节点。因此,整个网络的连通性发生分都是度很大的节点。因此,整个网络的连通性发生了剧烈变化,甚至于网络被分成若干不连通的分支,了剧烈变化,甚至于网络被分成若干不连通的分支,并且并且 ,从而,网络的同步化能力大大地降,从而,网络的同步化能力大大地降低甚至丧失了。低甚至丧失了。4 4、局域世界演化网络模型的完全同步、局域世界演化网络模型的完全同步 局域世界演化模型的生成规则:局域世界演化模型的生成规则:增长:网络初始时有增长:网络初始时有 个节点和个节点和 条边,每次加入条边,每次加入一个节点和附带的一个节点和附带
29、的 条边。条边。局域世界有线连接:随即的从网络已有的节点中选局域世界有线连接:随即的从网络已有的节点中选取取 个节点个节点( ),( ),作为新加入的节点的局域世界。作为新加入的节点的局域世界。新加入的节点根据优先连接概率:新加入的节点根据优先连接概率:来选择局域世界中的来选择局域世界中的m m各节点相连,其中各节点相连,其中LWLW是由新选是由新选的的M M个节点组成。个节点组成。 对于每一个新加入的节点,它的局域世界都是随对于每一个新加入的节点,它的局域世界都是随机的从网络中挑选构成,其连接度决定了网络的非均机的从网络中挑选构成,其连接度决定了网络的非均匀性,并且度分布在指数和幂律之间的过
30、渡。因此,匀性,并且度分布在指数和幂律之间的过渡。因此,在这种局域世界演化网络中,在这种局域世界演化网络中,HubHub节点的数目通常要节点的数目通常要比无标度网络的少,因而度分布也要比无标度网络更比无标度网络的少,因而度分布也要比无标度网络更均匀。因此,当面对随机故障的和恶意攻击时,局域均匀。因此,当面对随机故障的和恶意攻击时,局域世界演化网络的同步鲁棒性和脆弱性也就介于无标度世界演化网络的同步鲁棒性和脆弱性也就介于无标度网络和指数网络之间。网络和指数网络之间。 一般来说,与无标度网络相比,局域世界演化网络一般来说,与无标度网络相比,局域世界演化网络能够在保持鲁棒性的同时,提高网络对恶意攻击
31、的抗能够在保持鲁棒性的同时,提高网络对恶意攻击的抗脆弱性。脆弱性。五、复杂网络中各因子与完全五、复杂网络中各因子与完全同步的关系同步的关系 由前面的分析指导最近邻耦合网络在由前面的分析指导最近邻耦合网络在 时不可时不可能达到同步,但是通过加入少量的长程边将网络的平能达到同步,但是通过加入少量的长程边将网络的平均路径明显缩短,太的同步化能力便会有明显提高。均路径明显缩短,太的同步化能力便会有明显提高。问题:问题: 是不是由于平均路径的缩短提高了复杂网络的同步化是不是由于平均路径的缩短提高了复杂网络的同步化能力呢?能力呢?复杂网络中其他结构特性对网络的同步起到了什么作复杂网络中其他结构特性对网络的
32、同步起到了什么作用?用?究竟是哪些网络基本参数对于提高网络同步化能力起究竟是哪些网络基本参数对于提高网络同步化能力起到了关键性作用?到了关键性作用?。 复杂动态网络有许多基本参数,如特征根及其比率,复杂动态网络有许多基本参数,如特征根及其比率,平均路径长度,节点度及其分布、介数和同类匹配系平均路径长度,节点度及其分布、介数和同类匹配系数等,它们对各种网络的同步化能力都有不同程度的数等,它们对各种网络的同步化能力都有不同程度的影响。这里主要介绍它们对小世界网络和无标度网路影响。这里主要介绍它们对小世界网络和无标度网路同步化能力的影响。同步化能力的影响。 这里只考虑类型这里只考虑类型连续时间动态网
33、络。由类型连续时间动态网络。由类型网络网络的同步判据可知:的同步判据可知: 值越大,网络的同步化能力越值越大,网络的同步化能力越差。差。1.1.连接概率连接概率( )( )和幂律指数和幂律指数( )( )1 1) 和和 对同步化性能的影响对同步化性能的影响 对于小世界网络,当加边或重连概率对于小世界网络,当加边或重连概率 不断变化时,不断变化时,对应地会产生多个具有不同基本特性的小世界模型;同对应地会产生多个具有不同基本特性的小世界模型;同样,对于无标度网络,当幂律指数样,对于无标度网络,当幂律指数 不断变化时,也会不断变化时,也会得到多个不同的无标度网络模型。下面我们就研究由这得到多个不同的
34、无标度网络模型。下面我们就研究由这两个参数两个参数 和和 不断变化而产生的不同网络模型,它们不断变化而产生的不同网络模型,它们的同步化性能与网络基本特性之间的关系。的同步化性能与网络基本特性之间的关系。 小世界网络小世界网络 就小世界网络而言,由前面分析小世界网络的同就小世界网络而言,由前面分析小世界网络的同步化稳定性可以知道,随着网络进行步化稳定性可以知道,随着网络进行“小世界小世界”的操的操作作( (不断的加入长城边或不断重新连边不断的加入长城边或不断重新连边) ),网络的特征,网络的特征根比率会随之减少,即随着加边或重连概率根比率会随之减少,即随着加边或重连概率 的增加,的增加, 随之减
35、少。如图:随之减少。如图: 这说明小世界网络的同步化能这说明小世界网络的同步化能 力随着力随着“小世界小世界”操作(概率操作(概率p p 增加)而增强。增加)而增强。 N=2000 N=2000,100100实验的平均值。实验的平均值。特征根比率随连接概率p的变化曲线N/ 2无标度网络无标度网络 对于度分布为幂律形式对于度分布为幂律形式 的无标度网络,的无标度网络,通过研究具有不同通过研究具有不同 值的无标度网络的同步化值的无标度网络的同步化性能时发现,值越大的网络,其性能时发现,值越大的网络,其 越小。越小。 说明幂律指数说明幂律指数 越大对应越大对应 的无标度网络的同步化能的无标度网络的同
36、步化能 力越强。力越强。2) 2) 和和 对于网络中各基本参数指标的影响对于网络中各基本参数指标的影响 下面分析网络中各基本特性指标随着下面分析网络中各基本特性指标随着 和和 的变化情的变化情况,从而进一步得到网络性能指标对同步化性能的影响。况,从而进一步得到网络性能指标对同步化性能的影响。小世界网络小世界网络 小世界网络模型的一个显小世界网络模型的一个显 著特点是当加边或重连概著特点是当加边或重连概 率率 很小时,网络的平均很小时,网络的平均 路径长度有大幅度的下降路径长度有大幅度的下降 当当 时,平均路径时,平均路径 长度的变化不是很显著。长度的变化不是很显著。 但是随着但是随着 的增加,
37、小世的增加,小世 界网络的平均路径会减少。界网络的平均路径会减少。 虽然相对于具有幂律度分布的无标度网络来说,小虽然相对于具有幂律度分布的无标度网络来说,小世界网络是均匀的,但是其网络中各节点所连接的边世界网络是均匀的,但是其网络中各节点所连接的边数并不是完全相等的。因此,用方差指标:数并不是完全相等的。因此,用方差指标:来表示节点度的分布,则来表示节点度的分布,则 值越大说明网络中节点度值越大说明网络中节点度分布范围越大,并有度较大的节点出现,这时网络的分布范围越大,并有度较大的节点出现,这时网络的度分布变的均匀。由上图的曲线可以看出随着概率度分布变的均匀。由上图的曲线可以看出随着概率 的的
38、增加,网络变的更加非均匀;同时无论是新加入的长增加,网络变的更加非均匀;同时无论是新加入的长程边(程边(NWNW小世界)或是重新连接长程边(小世界)或是重新连接长程边(WSWS小世界),小世界),网络中度的最大值都会增加。网络中度的最大值都会增加。无标度网络无标度网络对于具有幂律分布对于具有幂律分布 的无标度网络模型,用节的无标度网络模型,用节点的标准偏差点的标准偏差 来衡量网络的非均匀性,则来衡量网络的非均匀性,则 值越大值越大 反而下降,说明网络中节点度的分布越均匀。在无标反而下降,说明网络中节点度的分布越均匀。在无标度网络中,少数具有度非常大的节点将大量的度很小度网络中,少数具有度非常大
39、的节点将大量的度很小的节点连接在一起,因此这些度大的节点使得网络的的节点连接在一起,因此这些度大的节点使得网络的平均路径很短。而随着平均路径很短。而随着 值的增大网络度分布变的比值的增大网络度分布变的比较均匀,因此网络的平均路径就会增加,同时平均度较均匀,因此网络的平均路径就会增加,同时平均度变小。变小。 无标度网络的平均路径无标度网络的平均路径D D随随 变化的曲线变化的曲线 小图是网络平均度小图是网络平均度k k随随 变化的曲线变化的曲线 总结:由上述对小世界网络和无标度网络的分析总结:由上述对小世界网络和无标度网络的分析可以看到,小世界网络在最近邻耦合网络的基础上通可以看到,小世界网络在
40、最近邻耦合网络的基础上通过过“小世界操作小世界操作”,使得网络的平均路径长度减小,使得网络的平均路径长度减小,同时也增加了网络节点的度分布的非均匀性以及最大同时也增加了网络节点的度分布的非均匀性以及最大的度,从而同步化能力有了显著提高;而对于无标度的度,从而同步化能力有了显著提高;而对于无标度网络却有了相反的结论,即只有提高网络的均匀性,网络却有了相反的结论,即只有提高网络的均匀性,增大平均路径长度或减小网络的平均度,才能使得无增大平均路径长度或减小网络的平均度,才能使得无标度网络的同步化性能提高。因此,单纯用度的大小标度网络的同步化性能提高。因此,单纯用度的大小、度分布、或平均路径长度等指标
41、都无法统一表征复、度分布、或平均路径长度等指标都无法统一表征复杂网络的同步化能力。杂网络的同步化能力。2.2.介数介数 某个节点的介数越大说明在信息传播过程中的信某个节点的介数越大说明在信息传播过程中的信息量也会越多,于是也就越容易发生信息堵塞。研究息量也会越多,于是也就越容易发生信息堵塞。研究发现,无论是小世界网络还是无标度网络,节点的最发现,无论是小世界网络还是无标度网络,节点的最大介数值都会随着概率大介数值都会随着概率 和参数和参数 的增加而减小。这说的增加而减小。这说明,介数是一个相对能够统一反映网络同步化能力的明,介数是一个相对能够统一反映网络同步化能力的参数。参数。 最大介数最大介
42、数B Bmaxmax随连接概率随连接概率p p的变化图的变化图 假设在两组高度连接的子网络之间只有少数的节假设在两组高度连接的子网络之间只有少数的节点相连,那么这几个少数节点的介数就会很大,会有点相连,那么这几个少数节点的介数就会很大,会有过多的信息经过这几个节点而造成过载从而丢失信息过多的信息经过这几个节点而造成过载从而丢失信息。因此最大介数值变化会降低网络的同步化能力。因此最大介数值变化会降低网络的同步化能力。 为了进一步验证这一结论,现在将小世界网络模为了进一步验证这一结论,现在将小世界网络模型中具有最大介数型中具有最大介数 的节点去掉。这样原本大量从的节点去掉。这样原本大量从该节点经过
43、的同步流形信息会分散到其他的节点上。该节点经过的同步流形信息会分散到其他的节点上。用参数:用参数:来表示去除节点前后网络同步化性能的变化。来表示去除节点前后网络同步化性能的变化。仿真实验表明:无论仿真实验表明:无论 为何值为何值的小世界网络,当具有的小世界网络,当具有 的的节点被去掉以后,特征根比节点被去掉以后,特征根比率均会下降率均会下降( ),( ),从而网络从而网络的同步化性能显著提高;相的同步化性能显著提高;相反,如果随机去除一个节点反,如果随机去除一个节点,特征根的比率前后没有很,特征根的比率前后没有很大变化,说明介数不大的节点对整个网络同步化性能大变化,说明介数不大的节点对整个网络
44、同步化性能的影响不是很大。的影响不是很大。3. 3. 影响网络同步化能力的其他因素影响网络同步化能力的其他因素(1)(1)节点的度分布、平均路径长度以及同类匹配系节点的度分布、平均路径长度以及同类匹配系数这类指标的变化会对小世界网络和无标度网络数这类指标的变化会对小世界网络和无标度网络的同步化性能造成不同的影响,其中具体的原因的同步化性能造成不同的影响,其中具体的原因仍需进一步探讨。仍需进一步探讨。(2)(2)网络的社团结构和同型混合等特征也都可能会网络的社团结构和同型混合等特征也都可能会影响网络的同步化能力。因此,如何进一步从本影响网络的同步化能力。因此,如何进一步从本质上刻画影响网络同步化
45、性能的因素是一个值得质上刻画影响网络同步化性能的因素是一个值得研究的课题。研究的课题。六、网络模体的同步六、网络模体的同步 上面讨论的是整个网络的同步,下面研究网络模体的上面讨论的是整个网络的同步,下面研究网络模体的同步。同步。模体:网络中出现频率较高的子图。模体:网络中出现频率较高的子图。( (和同一网络的完和同一网络的完全随机化形式相比较而言全随机化形式相比较而言) )随着耦合强度随着耦合强度c c的增加,产生同步的概率的增加,产生同步的概率P Psyncsync也随着增也随着增加。加。定义参数定义参数c* c* :c*c*为当为当P Psyncsync 1/21/2时的时的c c值。值。
46、显然显然: :不同模体对应的不同模体对应的c*c*也不相同。模体的也不相同。模体的c*c*越小,说越小,说明它越容易达到同步。明它越容易达到同步。当模体的规模固定时,不同的连接方式决定了不同模体当模体的规模固定时,不同的连接方式决定了不同模体结构的不同同步阈值。(见图和表)结构的不同同步阈值。(见图和表)5种不同模体结构同步的概率值重复1000次5455对于模体4,6,9,它们都是由四个节点构成, 但连接节点的方式不同,结果是它们的c*差别很大。 模体内部的连接越多,c*值就越小c*模体469不同模体结构对应的概率Psync1/2,模体同步的耦合强度值55 表示网络的拓扑结构,当表示网络的拓扑
47、结构,当 表示一个无权无向简单图表示一个无权无向简单图的拓扑结构时,具体定义如下:的拓扑结构时,具体定义如下:如果节点如果节点 和和 之间存在连接,则之间存在连接,则 ,否则,否则 。耗散耦合表示为:。耗散耦合表示为: 其中,其中, 为节点为节点 的度数。的度数。矩阵矩阵 的一些特殊性质:的一些特殊性质:1.1.是实对称矩阵,且满足每行元素之和为零。每行元素是实对称矩阵,且满足每行元素之和为零。每行元素之和为零这一性质也成为耗散性,具有耗散性的矩阵称之和为零这一性质也成为耗散性,具有耗散性的矩阵称为耗散矩阵。为耗散矩阵。2.2.矩阵的对角元素为负数,非对角元素为非负数。矩阵的对角元素为负数,非
48、对角元素为非负数。3.3.只有一个特征值为只有一个特征值为0 0,其他特征值都为负数。,其他特征值都为负数。 变分法是处理函数的函数的数学领域,和处理数变分法是处理函数的函数的数学领域,和处理数的函数的微积分是相对的。的函数的微积分是相对的。 对于一个对于一个n n个变量的动力系统。选一个点,并取一个变量的动力系统。选一个点,并取一个中心在该点的一个小的个中心在该点的一个小的n n维的球,随着时间的增加,维的球,随着时间的增加,球将变形成为一个近似椭球;在球的半径趋于零的球将变形成为一个近似椭球;在球的半径趋于零的极限情况下,映象保持与椭球相同的时间将趋向于极限情况下,映象保持与椭球相同的时间
49、将趋向于无穷大。无穷大。 在一次迭代中(对于映射来说)或一个单位时在一次迭代中(对于映射来说)或一个单位时间中(对于流来说)椭球的轴长增加的倍数的长期间中(对于流来说)椭球的轴长增加的倍数的长期平均值,称为平均值,称为LyapunovLyapunov数,其对数称为数,其对数称为LyapunovLyapunov指指数。一个正数。一个正LyapunovLyapunov指数意味着在系统相空间中,指数意味着在系统相空间中,无论初始的两条轨线的间距多么小,其差别会随着无论初始的两条轨线的间距多么小,其差别会随着时间的演化而成指数率的增加,以致达到无法预测,时间的演化而成指数率的增加,以致达到无法预测,这就是混沌现象。这就是混沌现象。