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

复杂网络的传播机理与动力学分析

张玉林2010.11.28♦复杂网络中疾病传播与免疫复杂网络的传播临界值理论复杂网络的免疫策略与技术主要内容:1.疾病传播的基本知识2.SIS和SIR传播模型3.

均匀网络中的SIS模型,

WS模型为例进行解析4.无标度网络中的SIS模型,

BA模型为例进行解析复杂网络的传播临界值理论1.疾病传播I.

传染病：数理学家在研究传播行为时，往往并不区别研究对象，他们把可以在网络中传播开来的东西叫做传染病。II.在传播过程中，个体处于三个基本状态：(1)S(susceptible)—易感状态：不会传染他人，可能被传染（也就是健康状态）(2)I(infected)—感染状态：已患病，具有传染性(3)

R(removed)—免疫状态：被治愈，具有免疫能力，不具有传染能力，不会再次被感染（移除状态）Ⅲ.传染病模型科学家通过用基本状态之间的相互转换来建立不同的传播模型：

SIS模型：易染个体被感染后，可以被治愈但无免疫力（还可以再被感染）（感冒等）SIR模型：易染个体被感染后，可以被治愈且有免疫力（不会被感染，也不会感染其它节点，相当于已经从传播网络中被清除了）（天花等）SI模型：易染个体被感染后，不能被治愈（艾滋病等）

SIRS模型：易染个体被感染后，可以被治愈且有免疫力，但免疫期是有限的，还会再次回到易染状态。（乙肝？）

疾病传播模型的描述Ⅰ.模型的传播规则：①初始时随机选择网络中一个或若干节点为染病节点（I），其余为健康节点（S）②在每一个时间步t：如果一个健康节点具有染病邻居，则它依某个事先设定的概率变成染病节点，这一概率叫做染病概率（β）；同时每一个染病节点都依某个事先设定的痊愈概率（γ）变成健康节点。③

在每个时间步，这些演化规则在整个网络中被并行地执行。染病概率越大，痊愈概率越小，疾病就越有可能感染更多的人，因此，定义染病概率和痊愈概率的比值为有效传播率并用这个参数综合地衡量疾病自身特征。①感染密度（感染水平或者波及范围）ρ(t)

ρ(t)：传播过程中,感染节点总数占总节点数的比例。ρ：传播到稳态时（）感染密度的值,称为稳态感染密度。②有效传播率λ(=

/

)

λ非常小（

很小，

很大），传播达稳态时，所有节点都会变成健康节点，这种情况下就认为疾病没有在网络上传播开来，并记该疾病的稳态感染密度ρ

=0。反之，当λ足够大时，疾病将一直在网络中存在而不会完全消失，只是染病节点的数目有时多有时少，这时稳态感染水平（波及范围）

ρ

0。把稳态感染密度从零向正实数变化的那个点所对应的有效传播率称作传播阈值（临界值）λc。它是衡量网络上的传播行为最重要的参量之一。Ⅱ.传播模型研究的主要参量

SIS模型传播方程设s,i分别表示群体中S,I个体所占

的比例，则SIS传播的微分方程组为：

SIR模型传播方程设s,i,r分别表示群体中S,I,R个体所占的比例，则疾病传播的动力微分方程组为：注:

(1)传播网络是完全图，但实际网络中，只有接触才能被感染(2)并不是对每个节点都一致，而是服从分布，Newman对其进行了研究。

Ⅲ.模型传播动力学方程3.均匀网络中的SIS模型Ⅰ.均匀网络：

Ⅱ.解析模型三个假设：①均匀混合假设：感染强度和感染个体密度成比例。即：

和

为常数（均匀混合）。不失一般性，可假设

=1，因为这只影响疾病传播的时间尺度；②均匀性假设：均匀网络中，每个节点的度都等于网络的平均度<k>；③规模不变假设：假设病毒的时间尺度远小于个体的生命周期，即不考虑个体的出生和自然死亡

运用平均场的方法可得：被感染个体密度ρ(t)的变化率被感染节点以单位速率恢复健康单个感染节点产生的新感染节点的平均密度，它与有效传播率

、节点的平均度〈k〉，健康节点相连概率1-ρ(t)成比例，（其他的高阶校正项忽略了）。当传播达到稳态时，变化率为0，所以令上式右端为0；

即：-ρ+

<k>ρ[1-ρ]=0ρ（1-λ<k>+λ<k>ρ）=0；

ρ（ρ-）=0；当λ<时，ρ-必大于0，所以ρ=0；当λ

时，ρ=；所以，即为临界传播值，记=。结论：在均匀网络中存在一个有限的正的传播临界值λc。如果有效传播率λ

λc，则病毒可以在网络中传播开来，并最终稳定于

,此时称网络处于激活相态；如果有效传播率λ<λc，病毒感染个体数呈指数衰减，无法大范围传播，最终将不能传播,此时网络称为吸收相态。4.无标度网络中的疾病传播Ⅰ.

无标度网络：具有幂律度分布的网络，即：；

网络中节点的度没有明显的特征长度Ⅱ.解析模型无标度网络的度分布是呈幂律分布，因而度具有很大的波动性，定义一个相对感染密度：度数为k的感染节点数占总节点数的比例。当t趋于无穷大时，相对稳态感染密度记为。平均感染密度：稳态平均感染密度：∝同样我们能采用MF理论来求的变化率得:度为k的节点相对感染密度的变化方程为：被感染个体以单位速率恢复健康

：任意一条给定的边与一个被感染节点相连的概率单个感染节点产生的新感染节点的密度

根据稳态条件，可得：传播达稳态时，记为

:给定一条边，这条边指向一个已感染节点的概率此概率值不依赖于出发点的度，而仅于有关；并且趋于稳态时，又是λ的函数，因此趋于稳态时可以表示为。节点的度越高，被感染的概率越高下面我们计算：给定端点的一条边，其另一个端点为染病节点的概率时，必须考虑到网络的非均匀性。任意一条给定边指向度为k的节点的概率为（与度为k节点关联的边数与总边数的比值）则任意一条给定边指向度为k的感染节点的概率为从而，（将的值代入）回忆：传播临界值必须满足的条件：当时，可以得到的一个零解。当时，可以得到的一个非零解。有一个平凡解如果该方程要存在一个非零稳定解，需要满足如下条件：即有：结论：对于SF（无标度）网络，节点度数具有很大的浮动性，当,导致，从而特别地，作为SF网络的一个典型例子，考虑BA无标度网络。BA无标度网络的传播临界值BA无标度网络：(1)增长特性，(2)优先连接特性（富者更富，或马太效应）度分布，平均度其中m是网络最小度

将平均度，度分布，以及带入

，可得：

又因为化简后得：当λ=0时，有当λ>0时，有结论：

BA无标度网络在SIS模型下的只要有效传播率λ>0，病毒就能传播开来，并将达到一个稳定感染水平，这反映了无标度网络对抵抗病毒的脆弱性BA网络中，疾病传播的时间演化

N=106，从下至上λ从0.05到0.065WS网络与BA网络的比较总结1.

SIS模型在均匀网络中，存在一个传播临界值。当时，疾病在时间演化过程中逐渐衰减，最终被灭；当时，疾病在时间演化过程中传播开来，并稳定于某一值（稳态感染密度）：

2.

SIS模型在SF网络中，传播临界值：只要有效传播率λ>0，病毒就能传播开来，并将达到一稳定感染水平值：，这反映了无标度网络对抵抗病毒的脆弱性。

复杂网络的传播临界值理论复杂网络的免疫策略与技术报告内容主要内容1.随机免疫与集中接种2.目标免疫与优先免疫3.熟人免疫与环状接种免疫策略与技术随机免疫与集中接种：将所有可能感染的种群集中起来，按照某种概率随机选择种群中的个体进行接种。

（度大节点和度小节点是平等对待）1992年，Anderson和May《人类传染病》，

OxfordUniversityPress

SIS传播方式说明随机免疫1.随机免疫（均匀免疫）引入免疫参数g：初始网络中免疫节点数占节点总数的比例在平均场理论下可以通系数（1-g）来影响有效传播率λ，即用（1-g）λ来替换λ代入前面的ρ变换率方程中（均匀网络，WS）

（SF网络，BA）Ⅰ．均匀网络（以WS为例）令上式为0，得：

即：我们需要的免役临界值．显然，才有意义。情况下，如果不加免疫，疾病将传播开来，并稳定于某一ρ值(ρ≠0)；如果加免疫后，只要免疫值满足：疾病将不能传播开来，即达到稳态时，ρ＝0。Ⅱ.

SF网络（以BA为例）

SF网络的免疫临界值可由公式给出，即：结论：

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

2.目标免疫（选择免疫）将比例为g的免疫节点看作已从网络中移除，且从这些节点出发的边也被删除了。则新的度分布：（指向非免疫节点的概率）在SF网络中，有：特别地，在BA网络情况下：①同样，将代入<k>t及<k2>t得：将①、②代入式中。对代入后的方程求得一个近似解：上式表明：即使有效传播率

在很大的范围内取值，都可以得到较小的免疫临界值(对少量的节点进行免疫,即可消除病毒扩散)。②环状接种：隔离或免疫染病个体的所有(距离为k)邻居禽流感等熟人免疫：从群体中以比例p随机选择个体,再随机选择该个体的一个相邻个体进行免疫接触追踪：对与有传染性个体的接触者进行跟踪，然后以一定的概率进行免疫

非典病等例子

(Huerta和TSimring)

T：被监控态

T：被追踪的强度

r：被检查的强度

3.其他免疫现实中计算机病毒免疫的例子以Internet为例，用户不断地安装一些更新的反病毒软件，但计算机病毒的生命期还是很长。原因就在于反病毒软件的更新过程实际上是一种随机免疫过程。从个体来看，这种措施是有效的；但是从全局范围看，由Internet的无标度特性，就算随机选取大量节点进行免疫，也不能根除计算机病毒的传播。显示了SIS模型在一部分Internet映像中随机免疫（大图）和目标免疫（小图）的情况。（λ＝0.25）复杂网络的传播动力学1.d维NW小世界网络的线性传播方程2.小世界网络传播动力方程的分形、混沌和分岔3.小世界网络的广义传播动力方程及其分岔4.复杂网络传染动力方程的分岔与震荡5.复杂网络中的其他传播现象在一个有着少量长程连接(捷径)的小世界模型网络中研究了传播和最短路径。类似的传播比如森林火灾和传染病。用很简单的规则：每一步，从已经被感染的节点向所有邻接的未被感染的节点传播。关注于通过随机长程连接的直接反应，在系统中并没有考虑到时滞因素。Newman,Moukarzel提出的模型是，随机的添加长程连接，而不破坏原来的连接，观察小的概率值P对于小世界网络特性的影响。并将每个特性的分析结果与仿真结果进行比较。如下图所示，假设从最初的感染节点A开始，病毒以常速v=1开始传播。NW小世界网络中捷径端点的密度为，这里p是小世界网络模型中添加新捷径的概率参数。不妨假设这个传播过程是连续的。因此网络中节点的感染量V(t)是一个从A开始的以t为半径的球体，这里是d维小世界网络中的超球体常数。感染源在传播过程中碰到捷径端点的概率为，并因此而产生新的感染球体为。平均的总感染量V(t)由下面形式的积分方程得到：对上式做标度变换

化为对所得方程微分得显然，这个方程的解是随着时间t的增大而发散的。对先前模型的改进Yang认为NW小世界网络的感染量V(t)中，由于现实中存在的等待时间，新引发的病毒感染或者火灾发生相比而言都有一个时滞（远程连接而言），因此，相应的线性时滞传播方程为：解为：计算分形维数D本模型是对先前模型的一个扩展，去探求有时滞的小世界模型的分形维数和一些其他网络特性，因为求出差分方程的解并不是很容易，所以很有必要做数字模拟，主要关注一维和二维网络。这里利用解析方法，然后和数字模拟的结果进行比较。计算分形维数D，从图中可以看出分析结果和实际数据拟合还是不错的。时滞参数对于分形维数D和其他诸如速度等的特性影响是很大。结论：如果足够的时滞引入的话，一个小世界网络可以变的更大，另一方面，要使一个大世界网络转变为小世界网络，需要一个稍微大的长程连接概率P。按式：计算上式的分形维数D后发现决定着NW小世界网络的分形维数。进一步讲，在病毒、火灾以及Internet和通信网络中信息流的传播和扩散过程中存在的非线性摩擦等障碍因素，都会对传播过程产生不可忽视的影响。因此还应加入非线性摩擦项。从而有：经过标度代换和微分d次后得到如下的非线性传播方程：其中：如果将上式写成离散形式，令d=1，则一维离散小世界网络的传播方程为：

变量代换得到当时，系统出现混沌；

当时，系统趋于稳定的不动点；当时，系统出现倍周期分岔的传播过。对于非线性传播方程式，只考虑d=1的一维情形，即：以为分岔参数，如果，那么上述方程在处出现Hopf分岔。LiCG,ChenG.LocalstabilityandHopfbifurcationinsmall-worlddelayednetworks.Chaos,SolitonsandFractals,2004,20:353-361.3小世界网络的广义传播动力方程及其分岔前面的NW小世界网络传播方程都是经过一系列标度和时间变换得到的，这些变换都与NW小世界网络模型的概率参数p有关，因此，当p变化时所带来的网络结构演化，在传播方程中被标度变换式掩盖而无法显现出来。此外，p=0时的最近邻网络是NW小世界网络的一个特例，然而上述方程却不能包含这一特定的网络结构，因为p=0时，方程没有意义。本文提出一个非线性病毒传播模型，来描述增加新连接概率P在NW小世界网络模型中的拓扑转化中的影响。在所有类型的病毒传播中都纯在Hopf分岔。P不仅决定了NW小世界网络模型的拓扑转变，在网络的稳定性方面也主导作用。LiX,ChenG,LiCG.Stabilityandbifurcationofdiseasespreadingincomplexnetworks.Int.J.ofSystemsScience,2004,35:527-536改进后的模型，定义新的摩擦项，带入此时方程被推广为：这样不做任何标度变换而直接微分上面的方程，就得到了NW小世界网络的更广义的非线性传播方程：定义了一些变量，经计算可得相应的分岔周期解的方向、稳定性和周期等性质。计算发现，在不同的时滞作用下，分岔参数表现出来的对小世界网络模型参数P的依赖性是截然不同的。4复杂网络传染动力方程的分岔与震荡考察在无尺度网络（由真实的电子邮件网络中估计而来的）中通过邮件传播的计算机病毒的传播动态特性，我们认为一个增长的网络，有一个新的使用者加进来，都会导致从一个近乎灭绝的状态中恢复过来。首先考虑一个无尺度网络中真实的传染病模型，为了更好的理解这种震荡的传染行为，分析了一个可以用确定性方程描述的简化增长模型。简化模型（同质的SIR模型）用微分或者差分方程描述的传染过程中的不动点稳定性以及分岔等震荡行为也受到了关注。SIRS模型的动力方程可以用下面的微分方程表示：将上面的SIRS模型推广得到SIRS模型的差分方程形式如下：RamaniA,CarsteaAS,WilloxR,GrammationsB.Oscillatingepidemics:adiscrete-timemodel.PhysicaA,2004,333:278-292确定性模型分析结果发现，这个SISR过程并不是简单地趋于一个稳定的不动点，它在某些相对的痊愈/感染条件下会出现震荡的传染行为。Hayashi等也利用均匀网络和非均匀网络的SIR模型来研究计算机病毒的传播过程。

(a)震荡情形(b)收敛情形HayashiY,MinouraM,MatsukuboJ.Oscillatoryepidemicprevalenceingrowingscale-freenetworks.Phys.Rev.E,2004,69:0161125计算机病毒在Internet上的传播

4.5.1红色代码蠕虫的随机常数传播模型(RCS)4.5.2蠕虫的间隔模型4.5.3电子邮件病毒的传播模型4.5.4电子邮件病毒传播的仿真模拟5计算机病毒在Internet上的传播纵观计算机病毒的发展史，20世纪90年代初，绝大多数病毒的传播途径是磁盘，因而这一时期的病毒破坏力大多局限于某个局部的范围，传播的速度也相对较慢，随着Internet的飞速发展，计算机病毒的传播方式和速度也不段升级。本节，主要介绍计算机病毒在Internet上传播的一些模型和研究结果。通过电子邮件方式传播病毒已成为Internet上病毒传播的一种新的主要形式，所以本节对电子邮件病毒传播的研究予以比较详细的介绍。4.5.1红色代码蠕虫的随机常数传播模型(RCS)用随机常数传播模型来模拟红色代码蠕虫的爆发过程。该模型作了三个近似假设：一是忽略了系统可能被打补丁、关闭或切断连接；二是认为易攻击的目标数在这一模型中是常数；三是把Internet看作一个无向完全连接图。令K为平均初始感染率，即每轮开始的时候，被感染主机在单位时间内攻击易染主机的数目。假设K为常数，N为网络中的易染主机数，a为时刻t已被感染的主机的比例（设a为一常数），那么时刻t被感染的主机数为Na，这些主机在单位时间内以速率K扫描其他易染主机。StanifordS,PaxsonV,WeaverN.HowtoowntheInternetinyoursparetime.Proceedingsofthe11thUSENIXSecuritySymposium,August2002,149-167由于比例为a的主机已经被感染，所以每个感染主机每单位时间内会使个新的主机被感染。因此可以得到在下一时间段dt内将被新感染的主机数n的表达式：设两个不同的蠕虫在同一时刻攻击同一目标的可能性很小，忽略不计。在N为常数的假设下，

，带入上式，得到如下的Logistic微分方程：

其解为Logistic曲线：T表示病毒传播事件发生的固定时点，即被感染数最快速增长的时刻，意味着病毒开始爆发。当时刻t远早于时刻T时，a呈指数增长；当时刻t远晚于T时，a趋向于1，即所有的易染主机都被感染了。感染速率仅依赖于K而与主机总数无关，这说明，像红色代码蠕虫这样的病毒在Internet上有可能相当迅速地感染所有易染主机。本文提出一个非常简单的模型，对红色病毒进行理论建模，并与实际数据进行比较。下图为红色代码蠕虫第二轮再次爆发时，美国化学文摘服务社80端口被探测扫描的实际数据与RCS模型预测的结果比较，从中可以看出RCS模型对红色代码蠕虫的预测还是相当准确的。4.5.2蠕虫的间隔模型Serazzi认为可靠性强的病毒传播模型是非常有用的，可以预测未来威胁，也可以用来开发新的的防御措施。这他的文章中，分析了最常用的病毒传播模型的优点与不足，并提出了自己的新的模型，并与实际数据进行比较。他认为大多数传统的计算机病毒模型不适合用来分析被称为“flash”等的蠕虫病毒。理论上而言RCS（随机常数传播模型）模型应该使用于Slammer病毒，但模型数据和实际数据之间出现了很大差异，如下图所示。SerazziG,ZaneroS.Computerviruspropagationmodels.2003,AvailableonURL:http://www.elet.polimi.it/upload/