《网络上的病毒传播问题.ppt》由会员分享，可在线阅读，更多相关《网络上的病毒传播问题.ppt（24页珍藏版）》请在三一办公上搜索。
1、网络上的病毒传播问题,温罗生重庆大学数理学院,一、题目,病毒传播问题的研究由来已久，而一再的病毒流行使得这一领域长期以来吸引着人们的注意。在对病毒传播过程的描述各种模型中，“易感感染易感”（SIS）模型是研究者经常的选择。关于SIS模型，可以简单的描述为：一个易感的个体在和一个具有传染性的个体的接触中，在单位时间以一定的概率（）被感染，同时，已感染的个体以概率（）被治愈又重新成为健康（易感）的个体。实际中大量的问题可以利用网络（图）进行描述，比如在传染病问题的描述中，个体（人、动物、计算机等）可以看作网络的节点，当个体之间有可以导致病毒传播的接触时在两个个体之间连边。比如，对于接触性传染病，个
2、体存在两种状态，健康的（易感的）和已感染的；将这些个体作为网络的节点，由于两个个体之间的亲密接触,可能导致病毒的传播，因此可在两者之间进行连边。一个个体所接触的其它个体数量称为该节点的度（边数）。所谓二部网络（图），是网络中的节点可分成两类（比如A类和B类，雄性和雌性等），边仅仅存在于两类节点之间。在经典的传染病学模型中，总是假定病毒赖以传播的网络具有匀质性，即网络中节点有基本相同的度，但一些研究表明，这一假设远远背离实际的情况。因此，发现实际网络的一些特性，并研究这样的网络上的病毒传播问题具有理论和实际的意义。本题主要研究二部网络上的病毒传播问题，附件提供了一个二部网络（由10000个A类节
3、点和10000个B类节点构成）的节点度的数据，如数据的第一行表示A类的1号节点有96条边，B类的1号节点有21条边。试根据数据完成以下的任务：,1，根据附件提供的数据，选择适当的坐标，作出节点连接度和其概率的图形。2，生成上述网络，可以采用如下的机制：先生成一个小型的二部图，随后在A类中加入一个新节点并向B类中的节点连边，该边指向B类中i号节点的概率正比于i号节点当前的连接度，而后在B类中产生新节点，以同样的方式向A类连边，当这两个步骤进行足够多次之后即可得到满足数据文件特点的网络。根据这里所提供的生成机制，发现节点连接度分布的表达式。3，在这类二部网络上考虑“易感感染易感”（SIS）模型，得
4、到较平稳时期的得病数量以及A类和B类的得病比例。(参数0.1,考虑到两类个体的感染率可以不同，分析中假定A类个体的感染率为B个体感染率的2倍，即A=2B，并分别取B类个体的感染率B=0.01,0.015,0.02,0.025)。注意：考虑PC机的计算速度，模拟时网络规模不要太大，可选择10001000的二部网络。4,对问题3的模型进行理论的分析，看看是否和你的模拟结果一致。,二，问题的背景及设计思路,问题来源于本人关于二部网络上病毒传播的研究。性传染病是该问题的一个具体背景，当仅仅考虑异性病毒传播时，性传播网络构成一个二部网络，其上的病毒传播就是异性病毒传播。相对于当前的研究，网络的二部特性是
5、当前研究传染病病毒传播中还不曾研究的问题。传染病模型是大家比较熟悉的模型，可以根据不同的假设得到几种常见的模型：比如SI模型，SIS模型，SIR模型，SIRS模型等等，其中SIS模型经常作为性传染病的模型。一般而言，因为实际情况中两性的感染率不一致，这样使得研究两性的SIS模型有很强的实际意义。这也是考虑二部网络的原因。,最近的一些研究表明，性接触网络往往不满足随机图的假定，也就是网络的节点度不满足Poisson分布，而是和所谓的幂率分布比较接近，幂率指数在2到4之间。和前面提到的情况一起，问题就成为我们题目中所主要研究的二部无标度网络上的病毒传播问题。对于本题的设计思路，从上面的背景可以看出
6、，网络的特点是本题的一个研究重点，还有一个就是二部（也就是异性性传播）的特点，这两者是当前网络上难以找到的也是比较新颖的。前面的两个问主要引导大家解决题目的第一个特点，也就是了解网络的性质。在题目中没有直接提到幂率分布等关键词的原因是让同学们根据对问题研究的加深在网络上找到自己需要的信息。希望在接触实际问题时，既要善于收集已有的资料，也要加强自己对问题本身的理解。,后面的两个问题，则是题目的主要研究问题。如何确定在二部无标度网络上的病毒传播问题，需要理论和实验的结果一起加以说明。同样，理论结果需要考虑网络的拓扑性质，此外，模拟则需要使用前面关于网络生成过程的描述以便产生网络并使用随机模拟的方法
7、进行。当然，这些问题的解决没有非常现现成的东西，需要在理解同类问题的方法的基础上靠自己解决。从同学们所提交的答卷来看，部分同学通过查找资料已经发现所考虑的接触网络不是Poisson分布这一特点，但未能对已有的理论进行自己的加工和研究。而对于后面的两个问题，甚至对题目所给出的信息不管不顾，直接套用现有的一些结果。,三、关于第一问,前面说了，给出数据并根据这些数据得到网络结构上的特点，其目的是为后面的问题做准备。直接对数据进行统计，得到不同度的节点的数目，在将得到的数据反映在图象中即可。值得注意的是，在对数对数坐标下线性的特点比较明显。下面是问题一的图形。,四、关于第二问,之所以安排第一题，是考虑
8、大家直接在第二问的条件下不知道网络的分布特点，这样推导难以得到结果。有了幂率分布的数值结果再推导理论结果应当要简单一些。通过查找资料，可以发现，解决这种问题的方法可以有：平均场理论、主方程方法、率方程方法和马尔可夫方法。下面使用率方程方法进行理论分析。,用Fk(t)表示t时刻k度的A类节点的数目，Mk(t)表示t时刻k度的B类节点的数目，可以得到如下的方程,（1）,对上面方程的解释是：k度节点的变化和k-1度节点数有关，当k-1度节点得到一条连边后就成为k度节点，同时，由于连边，k度节点也会成为k+1度节点。其中A1和B1表示两类节点拥有的边的数目，有,（2）,并用A0和B0表示两类节点的节点
9、数目，有,（3）,根据生成网络的规则，容易得到关系,和,用 代表k度的A类节点占全部A类节点的比例，代表k度B类节点占全部B类节点的比例。,得到方程（1）的解,（4）,简单的计算有,（5）,和,（6）,简单的计算立刻可以得到,（7）,也就是说，B类和A类节点的度分布均近似地满足标度指数为3的幂率分布。,五、关于第四问,根据题意，该传播网络是一个二部网络。每个个体只存在两种不同的状态，也就是“易感的”或者“已感染的”。在每一个时间步，每个易感的A类个体，如果和一个被感染的B类个体有接触，她将以 A的概率被感染；类似的，对于B类感染概率是 B。同时，被感染的节点以的概率被治愈重新成为易感者。用Fk
10、 和Mk 分别代表具有 k 条边的A类和B类的感染密度，利用率方程的方法，能建立下面的方程组,（8）,在两个方程中，右边的第一项表示感染个体治愈的速度，第二项是病毒产生项，考虑了一个具有k 条边的A类（B类）健康的概率1 Fk(1 Mk)，还有通过接触变成感染的概率。后一概率由下面几个因素决定：感染率A(B)，连接数量以及任意一个个体的邻居是感染者的概率 B(A)。即,其中 代表节点的平均度。在平衡状态下，可以得到,（9）,（10）,结合（10），代人 P(k)的具体表达式P(k)=2/k-3（该表达式的计算可以根据密度函数在整个区间上的积分为1得到），可得到,（11）,当A(B)充分小时，可
11、以得到,（12）,B类和A类节点的感染密度可以由下面的表达式给出,（13）,可以得到,（14）,对方程(14)积分，可得,注意到方程(11)，于是方程(14)可化成,（15）,当A(B)充分小时，利用方程(12)和(15)可得,实际上，当A和B充分小时，利用方程(12)可以计算方程组(11)的近似解，有,进而有,六，关于编程的问题,在本题中，要求同学们进行数值的模拟，因此，关于网络的生成过程以及病毒在网络上的传播过程的计算机模拟均要求一定的程序设计能力。考虑到网络是一个稀疏网络，因此在处理中最好使用存储边的方式存储网络。网络的生成过程中用到一个产生随机数的问题，也就是新增加的节点产生一条边指向
12、网络中已经存在的节点，且指向某个节点的概率正比于该节点的度。,%n代表结点的数目，m代表边的总数；A存储第i条边的指向。B代表每个结点的边数。n=10000;m=2*n;A=zeros(m-10,2);B=zeros(n,2);for i=1:10 A(i,:)=i;B(i,:)=1;end for i=1:n-10 A(10+2*i-1,1)=10+i;%开始向女性连边%返回随机数 a=ceil(10+2*i-2)*rand(1);k=1;while a0 a=a-B(k,2);k=k+1;end k=k-1;A(10+2*i-1,2)=k;B(10+i,1)=1;B(k,2)=B(k,2)
13、+1;%女性连边完成 A(10+2*i,2)=10+i;%开始向男性连边%返回随机数 a=ceil(10+2*i-1)*rand(1);k=1;while a0 a=a-B(k,1);k=k+1;end k=k-1;A(10+2*i,1)=k;B(10+i,2)=1;B(k,1)=B(k,1)+1;%男性连边完毕end,下一个问题就是关于在给定的网络上进行病毒传播。基本的方法就是在前面产生的网络上，随机的在网络中产生一定数量的感染者，然后开始随机的传播，以SIS给定的规则进行。进行多次之后，曲线达到比较稳定的状态就可以作为问题的平衡点。,七、进一步的工作,实际上，我出这道题的目的是希望大家对一些结果进行一些验证，也希望在进一步的工作中做一些数值上的模拟。具体的问题如下：1，网络的标度指数是可以变化的量，在实际的研究中发现，比如性接触网络的标度指数不一定是3。如何生成标度指数不等于3的网络。一般而言，生成标度指数小于3的网络可以在生成过程中加入如下的一个步骤就可以，即在每一步除了在新节点和老结点之间连边，还在老结点之间按照节点的度的大小以一定的概率连边。这样可以产生符合要求的网络。2，在具有相同的标度指数的网络上进行病毒传播，其平衡状态下两类节点感染密度的比例如何？理论分析结果和实际模拟结果如何？3，在两类节点的节点标度指数不相等的情况下，传播的情况如何？,
