1、流行病和传播网络r决定流行病传播模式的因素：m病原体特性：传染性、传染周期、严重性m接触网络m传染概率r人们关心的问题：m多大范围？是否需要采取措施？（有些传染病会自生自灭，例如季节性传染病）m多长时间？会不会反复？m对患者影响的程度？（生命、损伤、不适）1第2页/共97页流行病传播与行为思想传播r相似点：两者都是通过接触网络在人之间传播，某种程度上思想传播也是一种“社会传染社会传染”r区别：m对于社会性传染，宜采用决策模型m对于疾病传播，宜采用随机模型2第3页/共97页最简单的传染病模型-分支过程r分支过程形成树结构接触网络r最初一个人携带病菌进入人群，以一个独立的概率p传染给遇到的每个人r
2、假设疾病感染期间每个人遇到k个其他人，以同样的概率将疾病传染给所遇到的人3第4页/共97页分支过程r传染过程停止的条件？4第5页/共97页基本再生数r由单一个体引起的新发病例数期望值期望值，记为R0，R0=p*k r疾病在分支过程模型中传播的结果取决于基本再生数是小于1还是大于1r如果R0 1，则疾病持续在每一波以大于0的概率至少传染一个人（证明参见21.8节）5第6页/共97页基本再生数rR0=p*k，当R0接近于1时有一个刀刃刀刃（knife-edge）特性m如果R0略低于1，略微增加传染概率p；结果可能会使R0 高于1，造成一个疾病突然的巨大爆发m如果略微减少疾病的传染性，将导致R0减小
3、到1以下，可以消除疾病大范围流行的风险m同样，稍微改变人群间联系的数目k也会对结果产生很大影响6第7页/共97页基本再生数r结论：当门槛值R0=1附近，社会应该付出加倍的努力减小基本再生数m降低k：如隔离人群m降低p：提倡良好的卫生行为和习惯，减少细菌传播，如戴口罩，勤洗手等7第8页/共97页j表示第n层的不同个体，随机变量Ynj当j受感染时为1，否则为0，则有如果发病率高于痊愈率，则疾病会持续，否则疾病将消失Patching rateContainment strategyCommunications.：单位时间治愈人数在线社会网络中的信息传播可以分析单亲物种的遗传特点受感染节点在感染期内每
4、一步都以概率q恢复健康，其它细节不变Communications.1876-1943 Scottish physician and epidemiologisthow active worms spread22nd Annual Joint线粒体夏娃理论：1987年，Rebecca Cann、Mark Stoneking和Allan Wilson 在Nature 杂志上发表一篇论文引起轰动但不能确定n趋于无穷时qn的走向如果 R0 1，则疾病持续在每一波以大于0的概率至少传染一个人（证明参见21.highly aggressive worms require extremely challen
5、ging reaction times even for content filtering containment systems关注人数为N的大群体中含k个个体的较小样本，分析其聚合为一个共同祖先的时间结论：当门槛值R0=1附近，社会应该付出加倍的努力减小基本再生数节点u在时刻1患有疾病，可能传染给通向节点y的所有节点，包括中间节点v、w分之过程太简化r分支过程模型显然是疾病传播的一个非常简化的模型，没有考虑接触网络中的三角关系、弱连接实际的疾病传播要复杂得多8第9页/共97页SIR流行病模型r1927年用动力学的方法建立 W.O.Kermack,A.G.McKendrick.Contri
6、butions to the mathematical theory of epidemics,part IJ.Proceedings of the Royal Society of London,1927,115:700721(引用 2680)91876-1943 Scottish physician and epidemiologist 1898-1970biochemist and mathematical epidemiologist第10页/共97页SIR流行病模型rSIR模型可以应用于任何网络结构，接触网络中的每个节点在流行病传播过程中经历三个状态m敏感期(Susceptible)
7、：易感者，有可能被一个患病的网络邻居节点感染m感染期(Infectious)：患病者，以一定的概率将疾病传染给处于敏感期的邻居m隔离期(Removed)：痊愈并免疫者，当一个节点经历了完整的感染期，就不再会被传染，也不会再对其他节点造成威胁，相当于从接触网络中移出10第11页/共97页SIR流行病模型rSIR模型流行病的传播进展情况取决于基础网络结构，以及两个量值：p（传染的概率）和 tI（感染期的长度）m最初，一些节点处于感染期 I，所有其他节点处在敏感期 Sm每个进入 I 的节点v在固定的步骤 tI 期间内具有传染性m在 tI的每一步，v 以概率 p 将疾病传染给它的处于易感状态的邻居m经
8、过 tI步后，节点 v 不再具有传染性，也不会再受感染；进入隔离期R，成为接触网络中的无效节点11敏感 S感染 I隔离 R第12页/共97页SIR流行病模型r易感人数、传染人数、移出人数分别为S(t),I(t),R(t)，占比分别为s(t),i(t),r(t)r：个人单位时间与其他人平均有效接触次数r：单位时间治愈人数 rSIR模型描述为：12第13页/共97页SIR流行病模型r给定和的SIR时间曲线r设=1,=0.4,s(at start)=0.99,i(at start)=0.013r疾病什么时候消失呢？r取决于：/。如果发病率高于痊愈率，则疾病会持续，否则疾病将消失第14页/共97页SI
9、R模型示例r接触网络是有向图，tI=1r最初节点y和z感染疾病r粗线边界的阴影节点处于感染状态Ir细线边界的阴影节点处于隔离状态R14第15页/共97页SIR模型扩展r对不同的节点组合采用不同的感染概率p值：m对于有向接触网络中一对节点v、w，v连接到w，设其相应的传播概率为pv,wmpv,w值较高意味着接触密切，容易传染；反之则表示接触比较稀少r可对节点感染期长度的随机性建模m受感染节点在感染期内每一步都以概率q恢复健康，其它细节不变r将状态I进一步分离成若干子状态m感染的早、中、晚期m允许子状态中的传染概率有所不同15第16页/共97页网络结构对疾病传播起不同的作用r网络由每层两个节点组成
10、向右无限伸延，tI=1，传染概率p=2/3，最左边的两个节点是最初传染者rR0是由一个节点造成的新病例数，预期为4/3 1r每条边不传播疾病的概率为1/3，所有四条边都没导致疾病传播的概率为(1/3)4,于是每一层成为最后一层（疾病传染终止层）的概率至少是1/8116第17页/共97页近似处理2：假设在最近的共同祖先前一代（即更接近当代的一代）不存在多于一个的两路世系碰撞。细线边界的阴影节点处于隔离状态RContent filteringDifference in performance because of the difference in path coverage无知者以概率获知信息I
11、Difference in performance because of the difference in path coverage最简单的传染病模型-分支过程Wright-Fisher单亲祖先模型：随着的增加，沉默者的最终比例逐渐下降，这说明度的正相关性减小了信息的传播范围将SIR和SIS结合起来，疾病有暂时免疫特性：受感染节点恢复后短暂地经过R状态，再回到状态SSIRS模型注意：每次运行结果可能不同所有伙伴关系都有时间重叠(分母是N2或更大值的分项)网络中边对应于特定的时期这种建模方法是许多领域的研究专题，包括社会学、流行病学、数学、计算机科学当k适度增大时，合并的预期时间取决于k的程
12、度很弱Conference of the IEEE Computer and经历被传染，持续相同的时间，进入隔离，之后又同时被传染Difference in performance because of the difference in path coverage此类疾病具有双向传染的特性，采用无向边表示疾病可以从一对伙伴的任一方传染给对方highly aggressive worms require extremely challenging reaction times even for content filtering containment systems2005年9月，魔兽世界开
13、放了一些新任务，其中包括杀死一条会传播恶性传染病”Corrupted Blood”的大蛇HakkarSIR的静态图示（渗透模型）r接触网络每条边预先投掷硬币（按照给定传染概率p），投掷硬币成功的边定义为开放边；其余的边定义为阻塞边r利用开放边和阻塞边描述流行病传播过程：最终受感染的节点正是那些能够从最初感染节点沿着在网络中随机选定的开放边达到的节点r注意：每次运行结果可能不同17图中，粗黑线为开放边图中，粗黑线为开放边不是所有开放边都起作不是所有开放边都起作用（比如用（比如wr）第18页/共97页SIS流行病模型rSIR模型只适用于一次患病终身免疫的疾病rSIS模型描述了更一般的情况：节点结束
14、感染状态后便循环回到敏感状态，并具备再次感染的条件。节点在 S 和 I 两种状态中交替，因此得名SIS模型m最初，一些节点处于状态 I，其余节点处于状态 Sm每个进入状态 I 的节点 v 在固定数量的步骤 tI 期间内具有传染性m在 tI期间的每一步，v以概率 p 将疾病传染给其所有处在状态S的邻居m经过 tI 步骤后，节点v不再具有传染性，返回状态S18敏感 S感染 I第19页/共97页Address blacklistingj表示第n层的不同个体，随机变量Ynj当j受感染时为1，否则为0，则有1-qn=(1-pqn-1)k对于原网络中v连接到w的边，在扩展网络中创建 t 时刻 v 的副本到
15、 t+1时刻w的副本的边The Epidemiological model uses a continuous time differential equation,while the AAWP model is based on a discrete time model能否说明这些边最终将汇聚到一点？22nd Annual Joint幂指数越小，网络非均匀性越大，信息传播范围越广Effect of Hitlist Size and Patching Rate并行模式却使得带病节点可以将疾病传播到网络任何其他节点22nd Annual Joint2003,3:1901-1910.节点u在之前
16、可以将疾病一直传染到节点y，对换后，w-y的伙伴关系在u可能将疾病传染给w时就已经结束了在线社会网络中的信息传播对于原网络中v连接到w的边，在扩展网络中创建 t 时刻 v 的副本到 t+1时刻w的副本的边如果R0 1，则疾病将在有限的疫情波后以概率1消失。SIS模型描述了更一般的情况：节点结束感染状态后便循环回到敏感状态，并具备再次感染的条件。Difference in performance because of the difference in path coverageSIR的静态图示（渗透模型）时间自上向下展开，最底层表示当前有N个个体可以证明，对于特定类型的接触网络，存在特定传染概
17、率p，在p的门槛值附近，SIS传染病在一边表现为“快速消失”，在另一边则会“持续一个很长的时间”SIS流行病模型rSIS模型描述为：19第20页/共97页SIS流行病模型rSIS模型的例子：接触网络由3个节点组成，tI=1。可以想象是3个人居住的公寓，或三口之家。观察节点v感染、恢复、再次感染的过程20第21页/共97页SIS模型特点rSIS模型下的传染病的流行周期比SIR模型的要长r具有“刀刃”特点m可以证明，对于特定类型的接触网络，存在特定传染概率p，在p的门槛值附近，SIS传染病在一边表现为“快速消失”，在另一边则会“持续一个很长的时间”m该传染概率门槛值以非常微妙的方式依赖于网络结构2
18、1第22页/共97页SIR与SIS的关系rSIS模型的一些基本变体可视为SIR模型的特例r设 tI=1，将节点v在每一个时间步骤视为“不同的个体”，可以将SIS模型表示为SIR模型r在每个时间点t=0、1、2、3，为每个节点分别创建一个节点副本，形成的网络称为时间扩展时间扩展接触网络接触网络。对于原网络中v连接到w的边，在扩展网络中创建 t 时刻 v 的副本到 t+1时刻w的副本的边22第23页/共97页SIR与SIS的关系23第24页/共97页SIRS流行病模型r将SIR和SIS结合起来，疾病有暂时免疫特性：受感染节点恢复后短暂地经过R状态，再回到状态SSIRS模型m开始某些节点在 I 状态
19、，其他在S状态m进入 I 状态的节点v在固定步骤数 tI 内具有传染性m在 tI期间每个步骤，节点v将疾病传播给敏感邻居的概率为pm经过 tI 步骤后，v不再具有传染性，进入状态R并在固定步骤数tR期间维持在该状态。在R状态 tR步骤后，节点v回到S状态24第25页/共97页SIRS流行病模型r疾病传播过程受量值 p、tI 以及暂时免疫长度tR的影响，同时受到网络结构的影响25感染I敏感StItR隔离RrSIRS模型描述为：第26页/共97页SIRS模型下的同步振荡效应26STUVWXSISSSS.RI.SRI.SRI.SRII.RI.SRI.SRI.SRI.SRITSUWXV第27页/共97
20、页幂指数越小，网络非均匀性越大，信息传播范围越广22nd Annual Joint受感染的宠物 VS 感染禽流感但无明显症状的禽类网络结构对疾病传播起不同的作用感染了疾病的玩家通过“心灵传输”的方式突破隔离区进入城市5，弱连接打破了有序的聚集区域，刚刚痊愈的个体可能又通过一个弱连接被再次感染。可以想象是3个人居住的公寓，或三口之家。网络中边对应于特定的时期这种建模方法是许多领域的研究专题，包括社会学、流行病学、数学、计算机科学将SIR和SIS结合起来，疾病有暂时免疫特性：受感染节点恢复后短暂地经过R状态，再回到状态SSIRS模型(分母是N2或更大值的分项)The time required t
21、o activate any containment strategy once this information has been receivedqn=1-(1-pqn-1)k最初节点y和z感染疾病每个染色体上有1个DNA分子（复制前）线粒体夏娃理论：1987年，Rebecca Cann、Mark Stoneking和Allan Wilson 在Nature 杂志上发表一篇论文引起轰动Wright-Fisher单亲祖先模型：在 tI期间的每一步，v以概率 p 将疾病传染给其所有处在状态S的邻居最后，虽然采用了近似处理，但估算结果非常接近于通过复杂分析得到的结果最初节点y和z感染疾病SIRS
22、模型下的同步振荡效应rWatts和Strogatz论述了小世界特性与同步性的关联，Kuperman和Abramson展示了这种关联自然地导致流行病的同步和振荡rMarcelo Kuperman,Guillermo Abramson Small world effect in an epidemiological model.Physical Review Letters,2001,86(13):2909-291227第28页/共97页SIRS模型下的同步振荡效应rtI=4，tR=9rNinf(0)=0.1r模拟c=0.01,0.2,0.9三种情况28结论：当弱连接（远程）边占比例比较高时，所有
23、节点被传染的周期趋于同步。经历被传染，持续相同的时间，进入隔离，之后又同时被传染第29页/共97页如果R0 1，则疾病将在有限的疫情波后以概率1消失。The AAWP model又所有节点都不发生该过程的概率也为1-qn，则有Small world effect in an epidemiological model.在线社会网络中的信息传播All cases are for 1,000,000 vulnerable machines,a scanning rate of 100 scans/second,and a death rate of 0.近似2意味着，如果一代中j个现有世系不能保持
24、完全不变，则必然是恰好因为其中两个世系选择了共同的父母，使得世系数从j减少到j-1SIS模型的例子：接触网络由3个节点组成，tI=1。从底部开始，任何一个个体都可以沿着向上的边追溯他她的单亲血统对于原网络中v连接到w的边，在扩展网络中创建 t 时刻 v 的副本到 t+1时刻w的副本的边001/second这样，就可以构造一个网络，节点是个体，代际分层，边代表单亲关系1876-1943 Scottish physician and epidemiologist并发(concurrency)是特别被关注和担忧的时序模式qn=1-(1-pqn-1)kThis paper present a mode
25、l,referred to as the Analytical Active Worm Propagation(AAWP)model,which characterizes the propagation of active worms(分母是N2或更大值的分项)SIS模型描述了更一般的情况：节点结束感染状态后便循环回到敏感状态，并具备再次感染的条件。Chen Z,Gao L,Kwiat K.Deployment scenarios利用前面的近似可知，Wj接近于一个更简单的随机变量，其中X分解成的多项之和，可以让我们了解合并到一个共同祖先主要时间消耗在哪里Containment strateg
26、y又所有节点都不发生该过程的概率也为1-qn，则有All cases are for 1,000,000 vulnerable machines,a scanning rate of 100 scans/second,and a death rate of 0.被感染的个体遇到k个其他人，并以概率p传染结果可能会使R0 高于1，造成一个疾病突然的巨大爆发如果R0 0.5，弱连接打破了有序的聚集区域，刚刚痊愈的个体可能又通过一个弱连接被再次感染。因此整个网络呈现同步状态29第30页/共97页接触与并发r前面讨论的模型都是以一个相对静态静态的接触网络为基础，其中所有的连接在整个流行病传播过程都存在
27、。这对于传染性较高且传染速度较快的流行病是一个合理的简化假设r这些假设是否适用于那些需要很长时间在人群中传播的疾病？如艾滋病等30第31页/共97页接触与并发r对于这类疾病，重要的是要考虑到接触是短暂短暂的这一事实r将接触网络的每条边注明其存在的时段r此类疾病具有双向传染的特性，采用无向边表示疾病可以从一对伙伴的任一方传染给对方31第32页/共97页接触与并发r短暂接触的影响m节点u在时刻1患有疾病，可能传染给通向节点y的所有节点，包括中间节点v、wm节点u不能将疾病传染给节点x：u将疾病传染到w时，w与x的伙伴关系已经结束32uvwxy1,57,112,612,16第33页/共97页接触与并
28、发r短暂接触的影响m将w-v和w-y伙伴关系的时间参数对换m节点u在之前可以将疾病一直传染到节点y，对换后，w-y的伙伴关系在u可能将疾病传染给w时就已经结束了33uvwxy1,57,112,612,16第34页/共97页接触与并发r短暂接触m只掌握接触网络的结构信息是不够的，关系的时序时序信息信息也相当重要m网络中边对应于特定的时期这种建模方法是许多领域的研究专题，包括社会学、流行病学、数学、计算机科学r不同的接触时机不只是潜在地影响到谁会将疾病传染给谁，这种时序模式还可以影响流行病整体的严重性r并发并发(concurrency)是特别被关注和担忧的时序模式r并发性研究是发现接触网络中的关系
29、对应的时间对特定类型模型的影响34第35页/共97页接触与并发r并发伙伴关系：一个人与多个人有伙伴关系，并且有时间重叠r串行模式通过时间效应把网络不同区域隔开；并行模式却使得带病节点可以将疾病传播到网络任何其他节点35uvw1,56,10uvw1,52,6串行伙伴关系并行伙伴关系第36页/共97页接触与并发r在较大规模网络中，并发效应对疾病的传播作用尤其突出36vwxy1,57,112,612,16uvwxy1,51,52,63,7u任何节点没有并行伙伴关系所有伙伴关系都有时间重叠第37页/共97页一个生物学基因遗传的研究r线粒体夏娃理论：1987年，Rebecca Cann、Mark Sto
30、neking和Allan Wilson 在Nature 杂志上发表一篇论文引起轰动 Mitochondrial DNA and human evolution Nature 325,31-36(01 January 1987)m线粒体DNA严格按照母系遗传m现代全人类的线粒体DNA基本相同r每个人都有一条母系祖先的线索，称为母亲的血统。所有这些血统源自10万至20万年前（14万年）的一个单一女子，很可能是在非洲，她是我们当代所有人的母系祖先37第38页/共97页相关生物遗传知识38脱氧核苷酸a基因bDNAc染色体d染色质特定的脱氧核苷酸序列代表遗传信息，每个基因含多个脱氧核苷酸具有遗传效应的D
31、NA片段，每个DNA分子含多个基因主要载体，每条染色体含有1或2个DNA分子解旋高度螺旋化缩短变粗基因在染色体上呈直线排列基本单位abcd第39页/共97页相关生物遗传知识39染色体DNA基因脱氧核苷酸染色体是DNA的主要载体每个染色体上有1个DNA分子（复制前）主要遗传物质基因是有遗传效应的DNA片段每个DNA分子含有许多基因遗传物质的结构功能单位基因中脱氧核苷酸的排列顺序代表遗传信息每个基因中含有许多脱氧核苷酸第40页/共97页相关生物遗传知识40第41页/共97页线粒体遗传的网络结构动力学解释rWright-Fisher单亲祖先模型：m每一代的人口数量保持在固定的Nm当前一代N个个体产生
32、新一代的N个个体m每个后代由一个单亲产生，从当前一代中独立地均匀随机选择，这样，当前一代的一个个体可能会有多个孩子 r这样，就可以构造一个网络，节点是个体，代际分层，边代表单亲关系41第42页/共97页线粒体遗传的网络结构动力学解释r每个个体都向上连接到自己的母亲r时间自上向下展开，最底层表示当前有N个个体r从底部开始，任何一个个体都可以沿着向上的边追溯他她的单亲血统r能否说明这些边最终将汇聚到一点？42第43页/共97页线粒体遗传的网络结构动力学解释r简单的概率分析，可以发现当前给定数量的个体在向上追溯单亲祖先的过程中会不断发生汇聚（发现同一个母亲），于是独立的线索越来越少，最终汇聚到一点r
33、这个距当代最近的汇聚点就是线粒体夏娃线粒体夏娃43第44页/共97页Figures are in log-log scale如果这个过程从x=1开始，则这个过程收敛于y=f(x)与y=x的交点。感染期(Infectious)：患病者，以一定的概率将疾病传染给处于敏感期的邻居感染期(Infectious)：患病者，以一定的概率将疾病传染给处于敏感期的邻居SIS模型的一些基本变体可视为SIR模型的特例(分母是N2或更大值的分项)细线边界的阴影节点处于隔离状态R新泽西拉特格斯大学的Eric Lofgren和波士顿塔夫茨大学教授Nina Fefferman001/second并发性研究是发现接触网络中
34、的关系对应的时间对特定类型模型的影响如果略微减少疾病的传染性，将导致R0减小到1以下，可以消除疾病大范围流行的风险Content filteringbiochemist and mathematical epidemiologist根据设计者的本意，只有较高级别的玩家才可能感染瘟疫，而这种玩家一般都实力强大，能够痊愈Deployment Scenarios并行模式却使得带病节点可以将疾病传播到网络任何其他节点R0是由一个节点造成的新病例数，预期为4/3 1the number of infected machines at the beginning of the spread of acti
35、ve wormsBackground并发伙伴关系：一个人与多个人有伙伴关系，并且有时间重叠在 tI期间每个步骤，节点v将疾病传播给敏感邻居的概率为pSIR的静态图示（渗透模型）基因遗传学的解释r当时肯定同时生活着许多女人（以及男人），只不过她们的线粒体基因没有遗传到现在r不仅是线粒体基因存在这种情形，人的任何一种基因，只要把它们的突变过程追溯得足够远，总能找到一个共同祖先，这些祖先生活的时间可能各不相同，甚至未必是人，有的可能要追溯到人进化出来之前的某个生物44第45页/共97页Wright-Fisher单亲祖先模型的意义r可以分析单亲物种的遗传特点r可以分析双亲物种中那些只由单亲遗传的现象，
36、如线粒体DNAr分析社会继承行为（包括学术继承等）r45第46页/共97页Wright-Fisher单亲祖先模型的意义r上溯到第十代，有多少不同的人是与你有血缘关系的祖辈？46第47页/共97页魔兽世界中的病毒传播r魔兽世界（World of Warcraft、WoW）是游戏公司Blizzard Entertainment所制作的一款大型多人在线角色扮演游戏，2005年6月6日正式商业化运营r2005年9月，魔兽世界开放了一些新任务，其中包括杀死一条会传播恶性传染病”Corrupted Blood”的大蛇Hakkar47第48页/共97页魔兽世界中的病毒传播r根据设计者的本意，只有较高级别的玩
37、家才可能感染瘟疫，而这种玩家一般都实力强大，能够痊愈r由于管理人员的失误，病毒扩散到人口密集的“大城市”内，引发大规模混乱，有大约400万名玩家感染，大量玩家染疾“死亡”48第49页/共97页魔兽世界中的病毒传播49被疫病感染的铁炉堡第50页/共97页魔兽世界中的病毒传播r新泽西拉特格斯大学的Eric Lofgren和波士顿塔夫茨大学教授Nina Fefferman The untapped potential of virtual game worlds to shed light on real world epidemics.The Lancet infectious diseases,
38、2007,7(9):625-629.50第51页/共97页魔兽世界中的病毒传播r传染病流行的原因：m感染了疾病的玩家通过“心灵传输”的方式突破隔离区进入城市m玩家拥有的宠物魔兽也在传播瘟疫中起到了重要作用m有一些玩家在好奇心驱使下偷偷进入“疾病隔离区”，结果自己也染上病毒51第52页/共97页魔兽世界中的病毒传播r对现实世界的启示：m研究游戏中的瘟疫蔓延很有现实意义，它无疑是一个提供标本和经验的绝佳场所m“心灵传输”和宠物存在于虚拟世界，但游戏中事态的发展趋势也与真实世界有类似之处 心灵传输 VS 全球交通系统 受感染的宠物 VS 感染禽流感但无明显症状的禽类 病毒在不同物种之间传播m研究游戏
39、中的瘟疫蔓延，有助于深入解析流行病学所涉及的复杂社会因素 预测人们面对恶性传染病时的行为 预测恶性传染病的传播速度、传播模式 公共疫情应对策略52第53页/共97页互联网病毒传播1rModeling the spread of active worms.Chen Z,Gao L,Kwiat K.INFOCOM 2003.22nd Annual Joint Conference of the IEEE Computer and Communications.2003,3:1890-1900.53第54页/共97页互联网病毒传播1rModeling the spread of active wor
40、ms can help us understand mhow active worms spreadmhow we can monitor,detect and defend against the propagation of worms effectivelyrThis paper present a model,referred to as the Analytical Active Worm Propagation(AAWP)model,which characterizes the propagation of active worms54第55页/共97页在线社会网络G=(V,E)
41、，其中为V用户集合，E为用户的好友关系集合To include the time necessary for detection of malicious activity隔离期(Removed)：痊愈并免疫者，当一个节点经历了完整的感染期，就不再会被传染，也不会再对其他节点造成威胁，相当于从接触网络中移出每个个体都向上连接到自己的母亲the average number of machines scanned by an infected machine per unit time可以证明，对于特定类型的接触网络，存在特定传染概率p，在p的门槛值附近，SIS传染病在一边表现为“快速消失”，在
42、另一边则会“持续一个很长的时间”最初节点y和z感染疾病病毒在不同物种之间传播the relationship be-tween containment effectiveness and worm aggressiveness2005年9月，魔兽世界开放了一些新任务，其中包括杀死一条会传播恶性传染病”Corrupted Blood”的大蛇Hakkar接触网络每条边预先投掷硬币（按照给定传染概率p），投掷硬币成功的边定义为开放边；Wright-Fisher单亲祖先模型：节点u在之前可以将疾病一直传染到节点y，对换后，w-y的伙伴关系在u可能将疾病传染给w时就已经结束了并发性研究是发现接触网络中的
43、关系对应的时间对特定类型模型的影响McKendrick.Address blacklisting考虑一组j个被跟踪的不同世系1876-1943 Scottish physician and epidemiologist节点以独立概率p传播疾病，则EYnj=pn，则用户分为3类:无知者i,传播者s,沉默者o和r，其密度分别为i(t),s(t),o(t),r(t)All cases are for 1,000,000 vulnerable machines,a scanning rate of 100 scans/second,and a death rate of 0.介绍了传染病模型在生物遗传
44、中的应用互联网病毒传播1rParameters in AAWP55ParametersNotationExplanation#of vulnerable machinesNthe number of vulnerable machinesSize of hitlisththe number of infected machines at the beginning of the spread of active wormsScanning ratesthe average number of machines scanned by an infected machine per unit ti
45、meDeath ratedthe rate at which an infection is detected on a machine and eliminated without patchingPatching ratepthe rate at which an infected or vulnerable machine becomes invulnerable第56页/共97页互联网病毒传播1rThe AAWP modelmIf there are mi vulnerable machines(including the infected ones),and ni infected
46、computers,then on average,the next time tick will have newly infected machines,where s is the scanning rate,m0=N,n0=hmGiven death rate d and patching rate p,on the next time tick the number of total infected machines will be56第57页/共97页互联网病毒传播1rEffect of Hitlist Size and Patching Rate57All cases are
47、for 1,000,000 vulnerable machines,a scanning rate of 100 scans/second,and a death rate of 0.001/second第58页/共97页互联网病毒传播1rThe differences between AAWP and Epidemiological modelmThe Epidemiological model uses a continuous time differential equation,while the AAWP model is based on a discrete time model
48、mThe Epidemiological model neither considers the patching rate nor the time that it takes the worm to infect a machine,while the AAWP model doesmThe AAWP model considers the case that the worm can infect the same destination at the same time,while the Epidemiological model ignores the case58第59页/共97
49、页互联网病毒传播1rComparing the AAWP Model to the Epidemiological model59第60页/共97页互联网病毒传播1rSimulating the Code Red v2 Worm60第61页/共97页互联网病毒传播1rConclusionmThe AAWP model used deterministic approximation and gives more realistic resultsmAn address space of 224(at least 220)IP addresses is large enough to obtai
50、n realistic resultsmthe AAWP model is used to evaluate the performance of a simple sensor detection systemmthe AAWP model is used to evaluate the performance of the LaBrea tool defense system61第62页/共97页互联网病毒传播2rInternet quarantine:Requirements for containing self-propagating code.Moore D,Shannon C,V
