复杂网络的同步能力与传播动力学性态

1、傅新楚，朱杰傅新楚，朱杰 （上海大学理学院，上海（上海大学理学院，上海 200444） 2010第六届全国复杂网络学术会议第六届全国复杂网络学术会议 ，苏州大学，苏州大学，2010年年10月月15-18日日 摘摘 要要 本文首先从无标度网络构造方式的区别开始，讨论了本文首先从无标度网络构造方式的区别开始，讨论了 网络在不同结构下的同步性和鲁棒性；随后，讨论了网络在不同结构下的同步性和鲁棒性；随后，讨论了 传染病在无标度网络上的传染病阈值，以及在各种不传染病在无标度网络上的传染病阈值，以及在各种不 同免疫的条件下阈值的变化情况，并描述了在网络同同免疫的条件下阈值的变化情况，并描述了在网络同 步的

2、情况下传染病的传播动力学性态。该文还步的情况下传染病的传播动力学性态。该文还重点解重点解 决决了了Physical Review E, 77 (2008) 036113一文中的一文中的 两个遗留数学问题，严格证明了不同免疫条件下阈值两个遗留数学问题，严格证明了不同免疫条件下阈值 比较的两个不等式。比较的两个不等式。 关键词：关键词：无标度网络，网络同步，传染病阈值，免疫控制，同步传播无标度网络，网络同步，传染病阈值，免疫控制，同步传播 Xinchu Fu, Jie Zhu （College of Sciences, Shanghai University, Shanghai 200444, C

3、hina） ABSTRACT: This paper discusses the different constructions of scale-free networks, then considers synchronization and robustness for networks with different topology structures. It then estimates epidemic thresholds for disease spreading on scale-free networks, and their variance under differe

4、nt immunization strategies. Finally, the interaction between spreading behavior of diseases and network synchronization is studied. And it also focus on solving two mathematical problems left behind in Physical Review E, 77 (2008) 036113 by proving the related two inequalities for the comparison of

5、epidemic thresholds. Key words: Scale-free networks; network synchronization; epidemic thresholds; immunization; spreading. 网络分类网络分类 v规则网络规则网络: 规则网络具有很强规则性，例如全连接网络，规则网络具有很强规则性，例如全连接网络， 环形，链形，星形网络以及格点和分形图等环形，链形，星形网络以及格点和分形图等 v随机网络随机网络:随机网络是指按照某种明确的统计规律生成随机网络是指按照某种明确的统计规律生成 的网络，与规则网络相对应，主要是经典的随机图模型的网络

6、，与规则网络相对应，主要是经典的随机图模型 及其派生出来的相关模型及其派生出来的相关模型 v小世界网络小世界网络: 主要有主要有WS改边小世界网络和改边小世界网络和NW加边小世加边小世 界网络界网络 v无标度网络无标度网络：BA无标度网络是第一个无标度网络。我无标度网络是第一个无标度网络。我 们将主要讨论此类网络上的同步与传播问题们将主要讨论此类网络上的同步与传播问题 v可导航网络可导航网络 网络同步与传播动力学网络同步与传播动力学 复杂网络动力学的特点：复杂网络动力学的特点： v网络规模大，结构复杂网络规模大，结构复杂; v节点之间的连接方式多样，如，方向可以不节点之间的连接方式多样，如，方

7、向可以不 同，权重也可以不同同，权重也可以不同; v网络具有时空复杂性，节点之间的复杂相互网络具有时空复杂性，节点之间的复杂相互 作用可导致同步、复杂的传播行为等作用可导致同步、复杂的传播行为等; v复杂网络科学有着广阔的应用前景。复杂网络科学有着广阔的应用前景。 两种同步网络的构造两种同步网络的构造 v同步最优网络：同步最优网络： 新加入节点的连接方式与网络中节点的度新加入节点的连接方式与网络中节点的度 有关，需要注意的是，在同步最优网络生成的过程中，只是有关，需要注意的是，在同步最优网络生成的过程中，只是 在每条新边加入时网络的同步化性能达到最优，并不能保证在每条新边加入时网络的同步化性能

8、达到最优，并不能保证 最终得到的整个网络的同步特性达到全局最优。这种同步最最终得到的整个网络的同步特性达到全局最优。这种同步最 优网络有极少量的节点与大量节点相连接，而其余大部分节优网络有极少量的节点与大量节点相连接，而其余大部分节 点的连接度数则很低。因此该网络同步化性能比无标度网络点的连接度数则很低。因此该网络同步化性能比无标度网络 强，但在恶意攻击下容易被破坏。强，但在恶意攻击下容易被破坏。 v同步优先网络：新节点连接概率与得到的网络的同步化性能同步优先网络：新节点连接概率与得到的网络的同步化性能 成正比，它的连接度分布既不服从幂律分布又不服从指数分成正比，它的连接度分布既不服从幂律分布

9、又不服从指数分 布，具有很强的鲁棒性。布，具有很强的鲁棒性。 v理论分析理论分析 传播动力学传播动力学 v在在SIS传染病模型中存在一个传染病阈值传染病模型中存在一个传染病阈值 ,当传染当传染 率大于该值时，感染个体能够将病毒传播扩散并使得率大于该值时，感染个体能够将病毒传播扩散并使得 整个网络感染个体总数最终稳定于某一平稳状态，此整个网络感染个体总数最终稳定于某一平稳状态，此 时称网络处于激活相态时称网络处于激活相态 ；如果有效传播率低于此临；如果有效传播率低于此临 界值，则感染个体数呈指数衰减，无法大范围传播，界值，则感染个体数呈指数衰减，无法大范围传播， 网络此时处于吸收相态。网络此时处

10、于吸收相态。 v传染病阈值的大小决定了传染病在网络中传播的结果，传染病阈值的大小决定了传染病在网络中传播的结果， 是传播动力学中的一个重要的参数。是传播动力学中的一个重要的参数。 v不同的网络特性以及免疫方式对传染病阈值的影响也不同的网络特性以及免疫方式对传染病阈值的影响也 不同。不同。 c 非零阈值的存在性非零阈值的存在性 v具有分片线性传染力的网络存在正的阈值。具有分片线性传染力的网络存在正的阈值。 可以假设传染力函数为：可以假设传染力函数为： v免疫前的阈值为：免疫前的阈值为： ( )min(,)kk A 1 1 m cA A m kdk kdkAkdk 随机免疫随机免疫 v若在网络中对

11、节点随机进行概率为若在网络中对节点随机进行概率为 的免疫，则阈值的免疫，则阈值 变为：变为： 可以看出免疫是有效的，但是，免疫具有随机性，并没有考可以看出免疫是有效的，但是，免疫具有随机性，并没有考 虑到复杂网络中节点的度对网络传播的影响，而且当传染病虑到复杂网络中节点的度对网络传播的影响，而且当传染病 阈值趋于足够大时，免疫率也要趋近于阈值趋于足够大时，免疫率也要趋近于1，理论上要对所有，理论上要对所有 节点免疫才能够消除传染病，效率偏低。节点免疫才能够消除传染病，效率偏低。 (0,1) ( ) 11 1( ) ( )1 k cc k kP k kk P k 目标免疫目标免疫 v在目标免疫中

12、，定义一个整数在目标免疫中，定义一个整数 ，当节点的度大于它时，当节点的度大于它时 进行免疫，度小于它时，不进行免疫，等于它时，以一定进行免疫，度小于它时，不进行免疫，等于它时，以一定 的概率进行免疫。的概率进行免疫。 v在计算过程中，在计算过程中， 的正负性用于描述的正负性用于描述 目标免疫相对与随机免疫的有效性，经过分析和数值模拟，目标免疫相对与随机免疫的有效性，经过分析和数值模拟， 可以得到，它可以得到，它总大于零总大于零，那就说明了当免疫率相等时，目，那就说明了当免疫率相等时，目 标免疫比随机免疫更有效标免疫比随机免疫更有效。 v目标免疫的流行病阈值：目标免疫的流行病阈值： cov(,

13、() k kk (1)( ) c k kk 1 c 熟人免疫熟人免疫 v该方法不需要知道整个网络的度分布，比较实用。该方法不需要知道整个网络的度分布，比较实用。 v该免疫的传染病阈值为该免疫的传染病阈值为 为关于为关于 的函数，经过计算，对于较小的的函数，经过计算，对于较小的 ，熟人免疫，熟人免疫 的有效性不如目标免疫，但是，当的有效性不如目标免疫，但是，当 大于一个常数时，大于一个常数时， 熟人免疫的有效性超过了目标免疫，并且当熟人免疫的有效性超过了目标免疫，并且当 时，时， 有：有： 具体的分析过程见下页。具体的分析过程见下页。 (1)() ()() cc c kk p kkkk Ck 2

14、 ln1 1 ln1() 26 A m AmA mm 主动免疫（略）主动免疫（略） 当当 时，目标免疫更有效，时，目标免疫更有效， 下面讨论下面讨论 与与 之间的关系：之间的关系： ( )( )0 kk kkk 11 1 11 1111 1 1111 ( )( ) ()( ) 1 1 ()() ) 11 4 () (1)(1) kk kkk ACC kk CC AAAA Cm CA Cm A 从而当从而当时，时，。 0 与与 的的分分析析： A 1 121 2 1 22 ( )( ) (ln1)(ln1) 2 () 2(ln1)ln1 2 kk kkk CAA CC m AA CC m 当当

15、： 无法直接判断无法直接判断的符号。在上式中对的符号。在上式中对求偏导：求偏导： 时，时， 1 212 ()(ln1)0 A CC m A 0 因此，当因此，当时，也有时，也有 。 ( ,)m 0 综上所述：对于任意的综上所述：对于任意的，总有，总有 所以，在平均免疫率相等的情况下，目标免疫比随机免疫更有效。所以，在平均免疫率相等的情况下，目标免疫比随机免疫更有效。 2 ln (1)( ) 0 1 ( )( )ln1() 26 kk m pAm A kkkk C kmm 2 lnln 1 11 ln1()ln1 262 AA mm Am AA mmmm 当当 A 时：时： A 当当 时：时：

16、1 2 ln1 (1)( ) 0 1 ( )( )ln1() 26 AA kk m pAm A kkkk C kmm 2 ln1ln1 11 ln1()ln1 262 AA mm Am AA mmmm 无法直接确定无法直接确定 的范围，的范围， 1 但是，可以确定但是，可以确定 与与成正比，因此令成正比，因此令 1 2 ln1 1 1 ln1() 26 AA m Am A mm 解得解得 1131 0 1 ()() 26 Am A m 0 ( ,)m1 0 (,) 1 0 1 综上所述：当综上所述：当时，时，； 时，时， 当当 时，时， 。 当当 ； 网络同步能力对传播动力学的影响网络同步能力

17、对传播动力学的影响 v传染病在网络中同步传播的能力与网络中个体交流的密切程传染病在网络中同步传播的能力与网络中个体交流的密切程 度有着很大的关系，当交流频繁时，传染病就容易在网络中度有着很大的关系，当交流频繁时，传染病就容易在网络中 同步传播。同步传播。 v网络上传染病同步流行的控制变为对网络中耦合强度的控制，网络上传染病同步流行的控制变为对网络中耦合强度的控制， 当出现传染病时，若网络中的耦合强度足够大，传染病就容当出现传染病时，若网络中的耦合强度足够大，传染病就容 易在网络中同步传播；降低网络耦合强度，就能够有效地降易在网络中同步传播；降低网络耦合强度，就能够有效地降 低网络同步能力（不管

18、是类型低网络同步能力（不管是类型I还是类型还是类型II网络）网络）,从而有效抑从而有效抑 制传染病的传播。制传染病的传播。 v根据实际传播网络的自适应性建立起不同类型的传播同步模根据实际传播网络的自适应性建立起不同类型的传播同步模 型，即可研究网络传播率与同步稳定性之间的关系，数值分型，即可研究网络传播率与同步稳定性之间的关系，数值分 析结果进一步表明，如果传播网络越容易爆发，那么传播同析结果进一步表明，如果传播网络越容易爆发，那么传播同 步就越容易出现。步就越容易出现。 该项研究将揭示网络拓扑结构、网络同该项研究将揭示网络拓扑结构、网络同 步动力学和网络传播动力学这三者之间相互依赖关系步动力

19、学和网络传播动力学这三者之间相互依赖关系 (Ongoing research.)。 主要结果：主要结果： 图图 示：示： 参考文献参考文献 Watts D J. Annual Review of Socialogy,2004 30: 243-270. 方锦清，汪小帆等，一门崭新的交叉科学方锦清，汪小帆等，一门崭新的交叉科学-网络科学上篇，网络科学上篇，2007，246-247. 陈关荣，复杂网络及其新近研究进展简介，力学进展陈关荣，复杂网络及其新近研究进展简介，力学进展, Vol.38, No.6 2008, 653-662. Bollobsi B. Random Graphs. New Yo

20、rk: Academic Press, 2001. Barabasi A L, Ravasz E, Vicsek T. Physica A, 2001, 299: 559-564 .Zhang Z. Z., Comellas F., Fertin G, et al. J. Phys. A: Math. and Gen., 2006, 39 (8): 1811- 1818. Boccaletti S, Latora V, Moreno Y, et al. Physics Reports, 2006, 424: 175-308. Gong B, Yang L, Yang K. Phys. Rev. E, 2005, 72: 037101. 陈关荣，汪小帆等，复杂网络：理论及其应用，清华大学出版社，陈关荣，汪小帆等，复杂网络：理论及其应用，清华大学出版社，2006. Li X，Chen G. Physica A，2003，328: 274-286. 方锦清，汪小帆等，一门崭新的交叉科学方锦清，汪小帆等，一门崭新的交叉科学-网络科学上篇网络科学上篇,200