复杂网络上疾病传播与免疫及动力学ppt课件.ppt

《复杂网络上疾病传播与免疫及动力学ppt课件.ppt》由会员分享，可在线阅读，更多相关《复杂网络上疾病传播与免疫及动力学ppt课件.ppt（91页珍藏版）》请在三一办公上搜索。

1、复杂网络的传播机理与动力学分析张玉林2010.11.28,复杂网络中疾病传播与免疫复杂网络的传播临界值理论复杂网络的免疫策略与技术,主要内容:1. 疾病传播的基本知识2. SIS和SIR传播模型3. 均匀网络中的SIS模型, WS模型为例进行解析4.无标度网络中的SIS模型, BA模型为例进行解析,复杂网络的传播临界值理论,1. 疾病传播,I. 传染病：数理学家在研究传播行为时，往往并不区别研究对象，他们把可以在网络中传播开来的东西叫做传染病。II. 在传播过程中，个体处于三个基本状态：(1) S(susceptible)易感状态：不会传染他人，可能被传染（也就是健康状态）(2) I(infe

2、cted) 感染状态：已患病，具有传染性(3) R(removed) 免疫状态：被治愈，具有免疫能力，不具有传染能力，不会再次被感染（移除状态）,. 传染病模型 科学家通过用基本状态之间的相互转换来建立不同的传播模型： SIS模型：易染个体被感染后，可以被治愈但无免疫力（还可以再被感染）（感冒等）SIR模型：易染个体被感染后，可以被治愈且有免疫力（不会被感染，也不会感染其它节点，相当于已经从传播网络中被清除了）（天花等）SI模型：易染个体被感染后，不能被治愈（艾滋病等） SIRS模型：易染个体被感染后，可以被治愈且有免疫力，但免疫期是有限的，还会再次回到易染状态。（乙肝？）,疾病传播模型的描述

3、,. 模型的传播规则： 初始时随机选择网络中一个或若干节点为染病节点（I），其余为健康节点（S） 在每一个时间步t： 如果一个健康节点具有染病邻居，则它依某个事先设定的概率变成染病节点，这一概率叫做染病概率（）；同时每一个染病节点都依某个事先设定的痊愈概率（）变成健康节点。 在每个时间步，这些演化规则在整个网络中被并行地执行。染病概率越大，痊愈概率越小，疾病就越有可能感染更多的人，因此，定义染病概率和痊愈概率的比值为有效传播率 并用这个参数综合地衡量疾病自身特征。, 感染密度（感染水平或者波及范围）(t) (t)：传播过程中,感染节点总数占总节点数的比例。：传播到稳态时（ ）感染密度的值,称为

4、稳态感染密度。 有效传播率(=/) 非常小（很小，很大），传播达稳态时，所有节点都会变成健康节点，这种情况下就认为疾病没有在网络上传播开来，并记该疾病的稳态感染密度 =0。 反之，当足够大时，疾病将一直在网络中存在而不会完全消失，只是染病节点的数目有时多有时少，这时稳态感染水平（波及范围） 0。把稳态感染密度从零向正实数变化的那个点所对应的有效传播率称作传播阈值（临界值） c。它是衡量网络上的传播行为最重要的参量之一。,. 传播模型研究的主要参量,SIS模型传播方程设s,i分别表示群体中S,I个体所占的比例，则SIS传播的微分方程组为： SIR模型传播方程 设s,i,r分别表示群体中S,I,R

5、个体所占的比例，则疾病传播的动力微分方程组为：注: (1) 传播网络是完全图，但实际网络中，只有接触才能被感染 (2) 并不是对每个节点都一致，而是服从分布 ， Newman对其进行了研究。,. 模型传播动力学方程,3. 均匀网络中的SIS模型,. 均匀网络： . 解析模型三个假设： 均匀混合假设：感染强度和感染个体密度 成比例。即： 和为常数（均匀混合）。不失一般性，可假设=1，因为这只影响疾病传播的时间尺度； 均匀性假设：均匀网络中，每个节点的度都等于网络的平均度； 规模不变假设：假设病毒的时间尺度远小于个体的生命周期，即不考虑个体的出生和自然死亡,运用平均场的方法可得：被感染个体密度(t

6、)的变化率 被感染节点以单位速率恢复健康单个感染节点产生的新感染节点的平均密度，它与有效传播率、节点的平均度k，健康节点相连概率1-(t)成比例，（其他的高阶校正项忽略了）。,当传播达到稳态时，变化率为0，所以令上式右端为0； 即：-+1-=0 （1-+）=0； （- ）=0；当 时，- 必大于0，所以=0；当 时，= ；所以， 即为临界传播值，记 = 。,结论：在均匀网络中存在一个有限的正的传播临界值c。如果有效传播率 c，则病毒可以在网络中传播开来，并最终稳定于 ,此时称网络处于激活相态；如果有效传播率c，病毒感染个体数呈指数衰减，无法大范围传播，最终将不能传播,此时网络称为吸收相态。,4

7、.无标度网络中的疾病传播,. 无标度网络：具有幂律度分布的网络，即： ； 网络中节点的度没有明显的特征长度. 解析模型无标度网络的度分布是呈幂律分布，因而度具有很大的波动性，定义一个相对感染密度 ：度数为k的感染节点数占总节点数的比例。当t趋于无穷大时，相对稳态感染密度记为 。平均感染密度：稳态平均感染密度：,同样我们能采用MF理论来求 的变化率得:度为k的节点相对感染密度的变化方程为：被感染个体以单位速率恢复健康 ：任意一条给定的边与一个被感染节点相连的概率单个感染节点产生的新感染节点的密度,根据稳态条件 ，可得：传播达稳态时， 记为 :给定一条边，这条边指向一个已感染节点的概率此概率值不依

8、赖于出发点的度，而仅于 有关；并且趋于稳态时， 又是的函数，因此趋于稳态时 可以表示为 。节点的度越高，被感染的概率越高,下面我们计算 ：给定端点的一条边，其另一个端点为染病节点的概率时，必须考虑到网络的非均匀性。任意一条给定边指向度为k的节点的概率为 （与度为k节点关联的边数与总边数的比值）则任意一条给定边指向度为k的感染节点的概率为从而， （将 的值代入）,回忆：传播临界值 必须满足的条件：当 时，可以得到 的一个零解。当 时，可以得到 的一个非零解。 有一个平凡解如果该方程要存在一个非零稳定解 ，需要满足如下条件：即有：,结论：对于SF（无标度）网络，节点度数具有很大的浮动性，当 ,导致

9、 ，从而特别地，作为SF网络的一个典型例子，考虑BA无标度网络。,BA无标度网络的传播临界值,BA无标度网络：(1) 增长特性，(2) 优先连接特性（富者更富，或马太效应）度分布 ，平均度 其中m是网络最小度将平均度 ，度分布 ，以及 带入 ，可得：,又因为,化简后得：当=0时，有 当0时，有结论： BA无标度网络在SIS模型下的 只要有效传播率0，病毒就能传播开来，并将达到一个稳定感染水平 ，这反映了无标度网络对抵抗病毒的脆弱性,BA网络中，疾病传播的时间演化 N=106，从下至上从0.05到0.065,WS网络与BA网络的比较,总结,1. SIS模型在均匀网络中，存在一个传播临界值 。当时

10、，疾病在时间演化过程中逐渐衰减，最终被灭；当时，疾病在时间演化过程中传播开来，并稳定于某一值（稳态感染密度）： 2. SIS模型在SF网络中，传播临界值：只要有效传播率0，病毒就能传播开来，并将达到一稳定感染水平 值： ，这反映了无标度网络对抵抗病毒的脆弱性。,复杂网络的传播临界值理论复杂网络的免疫策略与技术,报告内容,主要内容1. 随机免疫与集中接种2.目标免疫与优先免疫3. 熟人免疫与环状接种,免疫策略与技术,随机免疫与集中接种：将所有可能感染的种群集中起来，按照某种概率随机选择种群中的个体进行接种。 （度大节点和度小节点是平等对待）1992年，Anderson和May人类传染病， Oxf

11、ord University Press SIS传播方式说明随机免疫,1. 随机免疫（均匀免疫）,引入免疫参数g：初始网络中免疫节点数占节点总数的比例在平均场理论下可以通系数（1-g）来影响有效传播率，即用（1-g）来替换代入前面的变换率方程中 （均匀网络，WS） （SF网络，BA）,均匀网络（以WS为例）令上式为0，得：,即：我们需要的免役临界值 显然 ，才有意义。 情况下，如果不加免疫，疾病将传播开来，并稳定于某一值(0)；如果加免疫后，只要免疫值 满足：疾病将不能传播开来，即达到稳态时，0。,. SF网络（以BA为例） SF网络的免疫临界值可由公式 给出，即：,结论： 在均匀网络中：只要

12、 ，就可保证疾病不在网络中传播开来；SF网络中：免疫临界值约为，即任给定一值，都需要对网络中的所有个体进行免疫才能使疾病不传播开来。说明随机免疫只对均匀网络有效（有较小的),而对SF网络效果很差（ =1）。原因： 这是由于SF网络是异质网络，节点度呈两极分化，采用随机免疫，哪些最容易传播病毒的节点（度大的节点）不一定获得免疫。所以，如果对SF网络采取随机免疫的策略，需要对网络中几乎所有的节点都实施免疫才能保证最终消灭病毒传染。 因此对SF网络这样的异质网络，普遍认为：随机免疫策略对于无标度网络是无效的！,目标免疫：选取少量度最大的节点进行免疫。（而一旦这些节点被免疫后，就意味着他们所连的边可以

13、从网络中去除，使得病毒传播的可能途径大大减少。）假设对度kkt的节点进行免疫，即有： 引入定义（免疫平均度，免疫二阶矩）：p(g)：任给一条边，该边指向一个免疫节点的概率。且有： （免疫节点的平均度） （平均度）,2.目标免疫（选择免疫）,将比例为g的免疫节点看作已从网络中移除，且从这些节点出发的边也被删除了。则新的度分布： （指向非免疫节点的概率）,在SF网络中，有：,特别地，在BA网络情况下：,同样，将 代入t及t 得：将、代入 式中。对代入后的方程求得一个近似解： 上式表明：即使有效传播率在很大的范围内取值，都可以得到较小的免疫临界值 (对少量的节点进行免疫,即可消除病毒扩散)。,环状接

14、种：隔离或免疫染病个体的所有(距离为k)邻居禽流感等熟人免疫：从群体中以比例p随机选择个体,再随机选择该个体的一个相邻个体进行免疫接触追踪：对与有传染性个体的接触者进行跟踪，然后以一定的概率进行免疫 非典病等 例子 (Huerta和TSimring) T：被监控态 T：被追踪的强度 r：被检查的强度,3. 其他免疫,现实中计算机病毒免疫的例子,以Internet为例，用户不断地安装一些更新的反病毒软件，但计算机病毒的生命期还是很长。原因就在于反病毒软件的更新过程实际上是一种随机免疫过程。从个体来看，这种措施是有效的；但是从全局范围看，由Internet的无标度特性，就算随机选取大量节点进行免疫

15、，也不能根除计算机病毒的传播。,显示了SIS模型在一部分Internet映像中随机免疫（大图）和目标免疫（小图）的情况。（0.25）,复杂网络的传播动力学1.d维NW小世界网络的线性传播方程2.小世界网络传播动力方程的分形、混沌和分岔3.小世界网络的广义传播动力方程及其分岔4.复杂网络传染动力方程的分岔与震荡5.复杂网络中的其他传播现象,在一个有着少量长程连接(捷径)的小世界模型网络中研究了传播和最短路径。类似的传播比如森林火灾和传染病。用很简单的规则：每一步，从已经被感染的节点向所有邻接的未被感染的节点传播。关注于通过随机长程连接的直接反应，在系统中并没有考虑到时滞因素。Newman,Mou

16、karzel提出的模型是，随机的添加长程连接，而不破坏原来的连接，观察小的概率值P对于小世界网络特性的影响。并将每个特性的分析结果与仿真结果进行比较。,如下图所示，假设从最初的感染节点A开始，病毒以常速v=1开始传播。NW小世界网络中捷径端点的密度为 ，这里p是小世界网络模型中添加新捷径的概率参数。不妨假设这个传播过程是连续的。因此网络中节点的感染量V(t)是一个从A开始的以t为半径的球体 ， 这里 是d维小世界网络中的超球体常数。感染源在传播过程中碰到捷径端点的概率为 ，并因此而产生新的感染球体为 。,平均的总感染量V(t)由下面形式的积分方程得到：对上式做标度变换 化为对所得方程微分得,显

17、然，这个方程的解是随着时间t的增大而发散的。,对先前模型的改进,Yang认为NW小世界网络的感染量V(t)中，由于现实中存在的等待时间，新引发的病毒感染或者火灾发生相比而言都有一个时滞（远程连接而言），因此，相应的线性时滞传播方程为：解为：,计算分形维数D,本模型是对先前模型的一个扩展，去探求有时滞的小世界模型的分形维数和一些其他网络特性，因为求出差分方程的解并不是很容易，所以很有必要做数字模拟，主要关注一维和二维网络。这里利用解析方法，然后和数字模拟的结果进行比较。计算分形维数D，从图中可以看出分析结果和实际数据拟合还是不错的。时滞参数对于分形维数D和其他诸如速度等的特性影响是很大。结论：如

18、果足够的时滞引入的话，一个小世界网络可以变的更大，另一方面，要使一个大世界网络转变为小世界网络，需要一个稍微大的长程连接概率P。,按式： 计算上式的分形维数D后发现 决定着NW小世界网络的分形维数。,进一步讲，在病毒、火灾以及Internet和通信网络中信息流的传播和扩散过程中存在的非线性摩擦等障碍因素，都会对传播过程产生不可忽视的影响。因此还应加入非线性摩擦项。从而有：经过标度代换和微分d次后得到如下的非线性传播方程：其中：,如果将上式写成离散形式，令d=1，则一维离散小世界网络的传播方程为： 变量代换得到,当 时，系统出现混沌； 当 时，系统趋于稳定的不动点；当 时，系统出现倍周期分岔的传

19、播过。,对于非线性传播方程式，只考虑d=1的一维情形，即：以为分岔参数，如果，那么上述方程在处出现Hopf分岔。,Li C G,Chen G.Local stability and Hopf bifurcation in small-world delayed networks.Chaos,Solitons and Fractals,2004,20:353-361.,3 小世界网络的广义传播动力方程及其分岔,前面的NW小世界网络传播方程都是经过一系列标度和时间变换得到的，这些变换都与NW小世界网络模型的概率参数p有关，因此，当p变化时所带来的网络结构演化，在传播方程中被标度变换式掩盖而无法显现

20、出来。此外，p=0时的最近邻网络是NW小世界网络的一个特例，然而上述方程却不能包含这一特定的网络结构，因为p=0时，方程没有意义。本文提出一个非线性病毒传播模型，来描述增加新连接概率P在NW小世界网络模型中的拓扑转化中的影响。在所有类型的病毒传播中都纯在Hopf分岔。P不仅决定了NW小世界网络模型的拓扑转变，在网络的稳定性方面也主导作用。,Li X,Chen G,Li C G.Stability and bifurcation of disease spreading in complex networks.Int.J.of Systems Science,2004,35:527-536,改进

21、后的模型，定义新的摩擦项，带入此时方程被推广为：这样不做任何标度变换而直接微分上面的方程，就得到了NW小世界网络的更广义的非线性传播方程：,定义了一些变量，经计算可得相应的分岔周期解的方向、稳定性和周期等性质。,计算发现，在不同的时滞作用下，分岔参数表现出来的对小世界网络模型参数P的依赖性是截然不同的。,4 复杂网络传染动力方程的分岔与震荡,考察在无尺度网络（由真实的电子邮件网络中估计而来的）中通过邮件传播的计算机病毒的传播动态特性，我们认为一个增长的网络，有一个新的使用者加进来，都会导致从一个近乎灭绝的状态中恢复过来。首先考虑一个无尺度网络中真实的传染病模型，为了更好的理解这种震荡的传染行为

22、，分析了一个可以用确定性方程描述的简化增长模型。,简化模型（同质的SIR模型）,用微分或者差分方程描述的传染过程中的不动点稳定性以及分岔等震荡行为也受到了关注。SIRS模型的动力方程可以用下面的微分方程表示：将上面的SIRS模型推广得到SIRS模型的差分方程形式如下：,Ramani A,Carstea A S,Willox R,Grammations B.Oscillating epidemics:a discrete-time model.Physica A,2004,333:278-292,确定性模型分析结果发现，这个SISR过程并不是简单地趋于一个稳定的不动点，它在某些相对的痊愈/感染条

23、件下会出现震荡的传染行为。Hayashi等也利用均匀网络和非均匀网络的SIR模型来研究计算机病毒的传播过程。 (a)震荡情形 (b)收敛情形,Hayashi Y,Minoura M,Matsukubo J.Oscillatory epidemic prevalence in growing scale-free networks.Phys.Rev.E,2004,69:016112,5 计算机病毒在Internet上的传播 4.5.1 红色代码蠕虫的随机常数传播模型(RCS) 4.5.2 蠕虫的间隔模型 4.5.3 电子邮件病毒的传播模型 4.5.4 电子邮件病毒传播的仿真模拟,5 计算机病毒在

24、Internet上的传播,纵观计算机病毒的发展史，20世纪90年代初，绝大多数病毒的传播途径是磁盘，因而这一时期的病毒破坏力大多局限于某个局部的范围，传播的速度也相对较慢，随着Internet的飞速发展，计算机病毒的传播方式和速度也不段升级。本节，主要介绍计算机病毒在Internet上传播的一些模型和研究结果。通过电子邮件方式传播病毒已成为Internet上病毒传播的一种新的主要形式，所以本节对电子邮件病毒传播的研究予以比较详细的介绍。,4.5.1 红色代码蠕虫的随机常数传播模型(RCS),用随机常数传播模型来模拟红色代码蠕虫的爆发过程。该模型作了三个近似假设：一是忽略了系统可能被打补丁、关闭

25、或切断连接；二是认为易攻击的目标数在这一模型中是常数；三是把Internet看作一个无向完全连接图。令K为平均初始感染率，即每轮开始的时候，被感染主机在单位时间内攻击易染主机的数目。假设K为常数，N为网络中的易染主机数，a为时刻t已被感染的主机的比例（设a为一常数），那么时刻t被感染的主机数为Na，这些主机在单位时间内以速率K扫描其他易染主机。,Staniford S,Paxson V,Weaver N.How to own the Internet in your spare time.Proceedings of the 11th USENIX Security Symposium,Aug

26、ust 2002,149-167,由于比例为a的主机已经被感染，所以每个感染主机每单位时间内会使 个新的主机被感染。因此可以得到在下一时间段dt内将被新感染的主机数n的表达式：设两个不同的蠕虫在同一时刻攻击同一目标的可能性很小，忽略不计。在N为常数的假设下， ，带入上式，得到如下的Logistic微分方程： 其解为Logistic曲线：,T表示病毒传播事件发生的固定时点，即被感染数最快速增长的时刻，意味着病毒开始爆发。当时刻t远早于时刻T时，a呈指数增长；当时刻t远晚于T时，a趋向于1，即所有的易染主机都被感染了。感染速率仅依赖于K而与主机总数无关，这说明，像红色代码蠕虫这样的病毒在Inter

27、net上有可能相当迅速地感染所有易染主机。本文提出一个非常简单的模型，对红色病毒进行理论建模，并与实际数据进行比较。,下图为红色代码蠕虫第二轮再次爆发时，美国化学文摘服务社80端口被探测扫描的实际数据与RCS模型预测的结果比较，从中可以看出RCS模型对红色代码蠕虫的预测还是相当准确的。,4.5.2 蠕虫的间隔模型,Serazzi认为可靠性强的病毒传播模型是非常有用的，可以预测未来威胁，也可以用来开发新的的防御措施。这他的文章中，分析了最常用的病毒传播模型的优点与不足，并提出了自己的新的模型，并与实际数据进行比较。他认为大多数传统的计算机病毒模型不适合用来分析被称为“flash”等的蠕虫病毒。理

28、论上而言RCS（随机常数传播模型）模型应该使用于Slammer病毒，但模型数据和实际数据之间出现了很大差异，如下图所示。,Serazzi G,Zanero S.Computer virus propagation models.2003,Available on URL:http:/www.elet.polimi.it/upload/zanero/papers/zanero-serazzi-virus.pdf,Slammer与红色代码是基于不同的网络协议进行传播的，红色代码是基于TCP，需要先建立连接，完成TCP的三次握手过程，等待应答，这属于时延限制。Slammer是能更否已全速传播取决于网

29、络的带宽，这是一种网络限制。为了更好的分析这种传播受带宽限制的计算机病毒，Serazzi考虑了节点之间带宽的因素，从而在RCS模型基础上提出一种基于Internet自治层的间隔模型。,下图为Slammer蠕虫扫描增长过程与RCS模型理论估计值的对比示意图：,上图显示的是计算机病毒进行扫描的总次数，在大约3分钟时，蠕虫达到了它的最大扫描速率，每秒钟500多万次。这一时刻之后，增长的速率减慢。对次现象常见的解释为：网络的很大以部分无法保证蠕虫全速传播时所需要的足够带宽。也就是说在被感染主机数量饱和之前带宽已经先饱和了。由于网络性能的瓶颈在于AS内部连接。,间隔模型是RCS模型的延伸和扩展，正是因为

30、网络中的流量过载引起的Internet中的连边无法正常传输数据包，这一模型较好地解释了攻击（扫描）不断增加，然后又突然停止的现象。,4.5.3 电子邮件病毒的传播模型,Zou等人将人们相互之间的电子邮件联系看作一种无向图，并提出了相应的电子邮件病毒传播模型。模型中主要考虑到两个对电子邮件病毒传播有影响的人为因素：一个是电子邮件检查时间 ，即用户i检查电子邮件的时间间隔。其中|V|是电子邮件用户总数。另一个因素是附件打开概率 ,表示用户i打开一个病毒附件的概率。假定各用户之间的行为是独立的。用户的电子邮件检查时间是一个随机变量，基于平均邮件检查时间 呈指数分布，假设 本身也是一个随机变量，定义为

31、T。,Zou C C,Towsley D,Gong W B.Email virus propagation modeling and analysis.Technical Report TR-CSE-03-04,University of Massachusettes,Amherst 2003,用户i检查任一病毒邮件时打开病毒附件的概率为 ，再定义P为 产生的随机变量，即平均概率。用户一旦打开带病毒的附件就称为被感染。定义 为病毒传播开始时已被感染的用户数，他们将向所有的邻居发送病毒邮件。变量 定义为病毒传播过程中t时刻被感染的用户数。病毒邮件从发出到接收需要一定的时间，但是通常这段时间相对于

32、用户检查邮件的时间来说小得多，因此该模型中忽略了邮件传送的时间。模型的不足：用户打开附件的概率P，对每个 用户是固定的，而且和时间有关。,4.5.4 电子邮件病毒传播的仿真模拟,假定网络有100000个节点，服从幂律分布，仿真实验设定幂律指数 =1.7。模型中其他参数设定为： 整个实验关注在不同的感染次数、初始感染节点、网络拓扑结果和电子邮件检查时间等情形下，电子邮件病毒在t时刻感染的用户平均数 。 是经过100次随机仿真后得到的平均结果。,Zou C C,Towsley D,Gong W B.Email virus propagation modeling and analysis.Tech

33、nical Report TR-CSE-03-04,University of Massachusettes,Amherst 2003,1、重复感染和非重复感染的对比,重复感染（reinfection）是指只要用户打开病毒附件就会向外发出病毒邮件的副本，因此一个接受者可以重复的地接收来自同一中毒用户的病毒邮件。而非重复感染（non-reinfection）是指感染用户仅向外发送一次病毒邮件副本，以后不再发送同样的病毒邮件。下图为平均感染的用户数和时间t的关系图：,很显然，在重复传播情况下有更多的用户被感染。,右图，在100次模拟中的每一次都得到最大值，平均值和最小值。观察到最初病毒传播的状态决

34、定了整个的传播速度。纵坐标表示的是时刻t被感染的用户数。,2、初始感染度大的节点和度小的节点的对比,如图显示：初始感染节点的“身份”（以度的大小衡量）在稀疏的（平均度为8）网络中比密集的（平均度为20）网络中影响更大。,3、拓扑结构的影响：随机网络、小世界网络和无标度网络,研究拓扑结构是如何影响病毒传播的。分别在无尺度网络、小世界网络和随机网络中运行我们的仿真。这三个网络具有相同的平均度8，都有100000个节点。下图显示了平均感染用户数与时间t的关系。正如图中显示：小世界网络和随机网络中病毒传播非常类似。二者具有相近的平均路径长度，但小世界网络的聚集系数要比随机网络的更大。在无尺度网络中病毒

35、传播更快，原因之一是无尺度网络的平均最短路径相对小世界和随机图网络要更短。另一个原因是无尺度网络中节点度相差很大，一旦病毒感染到度很大的节点，传播速度就会被“放大”。,实验发现，小世界网络和随机网络上的传播行为十分相似，这说明影响邮件病毒传播率的是平均路径长度而非聚类系数。而对于幂律分布的无标度网络，病毒的传播率更快。 每个节点被传染的概率是和度成正比的。虽然这三个网络具有相同平均度，但是在无尺度网络中，度小的节点数要比另两个多，所以，无尺度网络中更多的节点在病毒传播的后期没有被感染。,上图中很清晰的显示出病毒在无尺度网络上传播分两个阶段，开始的时候病毒会感染连接最多的节点(most high

36、ly connected nodes)，之后就是度小一些的节点被感染。在小世界网络和随机网络中都没有出现这种情况。,4、 幂律指数的影响,幂律指数越小，度分布变化幅度越大。在之前的仿真中，我们设定幂律指数为1.7，拥有100000个节点的无尺度网络。这个网络度最大度节点度为1833，最小的3，对应着邮件地址簿的大小。Internet AS层幂律拓扑的幂律指数为1.1475，最大度为28000，最小度为1.由于不知道真实的邮件网络的幂律指数值，为了研究幂律指数对于病毒传播的影响，作者比较了节点数相同，平均度均为8，幂律指数为1.7和1.1475的两个网络。下图为实验结果。,对于具有幂律度分布的网

37、络，不同的幂律指数对电子邮件病毒传播的影响也不相同。幂律指数大的网络病毒传播刚开始较快，稍后变慢。幂律指数小的网络中，少量的节点聚集了大量的连接。它们一旦被感染，网络中就会有更多的病毒副本。这些度很大的节点就好像是网络的“病毒放大器”。感染了度很大的节点之后，就到了第二个阶段，主要是感染那些度小的节点。幂律指数大的网络中，度小的节点数量较多，所以在第二个阶段传播更快一些。,5、电子邮件检查时间的波动产生的影响,病毒模型中，我们假设用户检查邮件时间是服从指数分布的，而检查时间有可能是服从其他分布的。下图比较了在电子邮件检查时间分别服从三种不同分布时的传播行为。来研究邮件检查时间对于病毒传播的影响

38、。这里假设三种分布具有相同的平均邮件检查时间L。第一种分布是基于平均值L的指数分布；第二种是基于平均值L的三阶Erlang分布；第三种情况是所有用户的电子邮件检查时间均为常数L。,病毒传播的速度不仅由平均传播时间决定，而且被传播时间波动影响当邮件检查时间波动越大的时候，病毒邮件传播也就越快。,4.5.5 计算机病毒传播对网络拓扑结构的影响,网络的拓扑结构影响着病毒传播行为。另一方面，当计算机病毒在网络中传播时，网络的拓扑结构也不是一成不变的。在许多情况下，网络的拓扑结构取决于病毒复制的机制，即病毒利用不同的途径和不同的方式进行传播，其传播所依赖的媒介网络的拓扑结构也会发生改变。考虑以下四种网络

39、：计算机之间通过IP协议相连构成的网络；台式机管理员帐户共享网络；电子邮件地址簿网络；用户之间传送电子邮件的网络。,下图为这四种网络的度分布。IP网络中所有的节点具有相同的度，所有图中对应于一个尖峰。帐户共享网络度分布包括四个离散的尖峰，对应于不同类型的计算机、管理员或是管理策略。后两种邮件网络则具有更为连续的分布，右图为它们的累积度分布。尽管这两种网络都不具有幂律度分布，但其分布都具有相当长的“尾巴”。这表明两张电子邮件具有一定非均匀性。,上述四种网络表明，不同的病毒复制和传播策略有可能导致不同的网络拓扑，因此需要有一种不受网络拓扑变化影响，并且不需要在病毒爆发之前知道传染机制的控制策略。,

40、Balthrop J,Forrest S,Newman M E J,Williamson M M.Technological networks and the spread of computer viruses.Science,2004,304:527-529.,4.6 复杂网络中的其他传播现象 4.6.1 谣言在复杂网络中的传播 4.6.2 传播蔓延现象的推广模型与普遍行为,4.6.1 谣言在复杂网络中的传播,谣言在人际关系中的散布与病毒传播和扩散很相似。也可类似地用SIR模型来描述。Zanette研究了谣言在小世界网络中的传播情况。把人群分为3类： 、 和 分别对应谣言易染（没有听过谣言

41、）、感染（听到谣言）、免疫（对该谣言不再相信）的人群数量。Zanette简化了谣言传播的复杂机制，认为易染者一旦和感染者接触就被感染，而感染者与免疫者或感染者接触则变为免疫者。模型描述：每一步，随机的从被感染人群里选出个体i，这个个体和它的邻居j进行交互，如果j是易染状态，i把谣言传递给j，j变成感染状态。如果j已经是感染或者免疫状态，i对谣言也失去兴趣，变成免疫状态。,Zanette D H.Dynamics of rumor propagation on small-world networks.Phys.Rev.E,2002,65:041908,在进化的第一个阶段，被感染个体增加，免疫个

42、体以一个较小的速率增加。结果是，被感染个体之间以及与免疫个体之间的联系变得更加频繁。最后，被感染个体开始减少直至小时，演化也就停止。随着谣言在人群中的散播，人们最后分化为两部分：一部分是听过谣言而后免疫的人群，另一部分是从未听过谣言的易染人群。结论：当处于比较小的数值区域内时， 与 、 以及灭绝时间T的相关性是服从幂律分布的；当 处于很大的数值区域时，如果p增大，T减少， 和 都增大，这说明整个传播过程变得非常有效率。,4.6.2 传播蔓延现象的推广模型与普遍行为,Dotts和Watts认为，无论是社会网络还是生物、信息网络中的传播与蔓延现象，相应的模型都可以归结为两类：泊松模型和临界值模型。

43、这两张模型都不考虑各传染个体之间暴露的相关性，因此，提出了一个推广模型：假设种群中有N个个体，而各个体的状态是易染S、感染I或移除R状态中的一种。在每一时刻t，个体i随机地与个体j相连（接触）。如果个体i是易染状态，而个体j是感染状态，则个体i以概率p得到一个正的剂量 ，这里每个 都服从分布函数 。每个个体都保留着过去T时期中所接受的总的剂量：,Dodds P S,Watts D J.Universal behavior in a generalized model of contagion.Phys.Rev.Lett.,2004,92:218701,当 时，处于易染状态的个体i则被感染。在T时期内，易染个体与K( )个感染个体接触而因此被感染的概率为：其中T时刻内接收到k次剂量而感染的个体平均为：这里 是剂量阈值 的分布函数， 是k个剂量之和超过相应阈值的概率。,