复杂网络的免疫策略课件

复杂网络的免疫策略

纪鹏导师葛洪伟江南大学信息工程学院复杂网络的免疫策略纪鹏1大纲基本的复杂网络免疫策略改变假设条件：局域搜索免疫改变免疫对象：删除边的免疫改变免疫原则：多重图形剖分免疫对于有向网络免疫的思考大纲基本的复杂网络免疫策略2基本的免疫策略目标：通过对部分人接种而有效地控制疾病的传播基于局域信息免疫uniformimmunization(均匀免疫)acquaintanceimmunization（熟人免疫）基于全局信息targetedimmunization（目标免疫）基本的免疫策略目标：通过对部分人接种而有效地控制疾病的传3均匀免疫均匀免疫，顾名思义完全随机的从网络中选择一部分节点进行免疫。它对于度数大的节点和度数小的节点平等对待在无标度网络中对应的免疫临界值均匀免疫均匀免疫，顾名思义完全随机的从网络中选择一部分节点进4均匀免疫均匀免疫5熟人免疫随机选择比例为p的节点，然后再从这些选择的节点中随机选择一个邻居节点进行免疫由于度数大的节点也就意味着有更多的节点与之相连，所以熟人免疫比均匀免疫的效率要好得多熟人免疫随机选择比例为p的节点，然后再从这些选择的节点中随机6熟人免疫熟人免疫7目标免疫根据无标度网络的不均匀特性，可以进行有选择的目标免疫，即选取度数大的节点进行免疫在BA无标度网络中，目标免疫对应的免疫临界值为

目标免疫根据无标度网络的不均匀特性，可以进行有选择的目标免疫8目标免疫目标免疫9不同免疫策略的比较在网络规模为106，幂率指数在2-3.5之间变化的无标度网络中不同策略对应的免疫临界值均匀免疫(空心圆)熟人免疫（空心三角形）目标免疫（空心正方形）图1（参考文献[3]）不同免疫策略的比较在网络规模为106，幂率指数在2-310局域搜索免疫熟人免疫假设条件为已知当前节点的度目标免疫假设条件为已知所有节点的度假设已知邻居节点的度信息，怎样进行免疫呢？局域搜索免疫熟人免疫假设条件为已知当前节点的度111967年，哈佛大学的社会心理学家StanleyMilgram就设计了一个连锁信件实验[4]。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人，信中放了一个波士顿股票经纪人的名字，信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终大部分信在经过五、六个步骤后都抵达了该股票经纪人。1967年，哈佛大学的社会心理学家StanleyMilgr12Sixdegreesofseparation成功传递信件的前提是已知朋友中成功传递信件的程度类似于该实验过程，提出了局域搜索免疫(localsearchimmunizationstrategy)

Sixdegreesofseparation成功传递信13复杂网络的免疫策略课件14局域搜索免疫局域搜索免疫15在模型中实验图2实验采用SIS病毒传播模型，在ER随机网络(a:N为104,<k>=4)，BA无标度网络模型(b：N=104,m0=8,m=4；c：N=104,m0=8,m=6)中进行仿真。F为感染节点的密度，q为免疫节点的比例。在模型中实验图2实验采用SIS病毒传播模型，在ER随机网络(16在现实网络中实验图3实验采用SIS病毒传播模型在(autonomoussystem)AS层面的Internet网络和HighEnergyPhysics-Theory(HEP-Th)网络中测试局域搜索免疫的性能。F为感染节点的密度，q为免疫节点的比例在现实网络中实验图3实验采用SIS病毒传播模型在(auton17该免疫与聚类系数之间的关系由于局域搜索免疫是通过搜索邻居节点中度数最大的节点进行免疫，直观来讲该免疫的性能与网络的聚类系数有着某些联系Assortativewiring算法[5]能在保持节点度分布不变的前提下，增加网络的聚类系数。任意选择两条边，对两条边对应的四个顶点重新连接：用一条边连接两个度数比较大的节点，另一条边连接两个度数比较小的节点。该免疫与聚类系数之间的关系由于局域搜索免疫是通过搜索邻居节点18图4在BA无标度网络中，聚类系数与局域搜索免疫性能之间的关系。F为算法的免疫临界值，c为网络的聚类系数对BA无标度网络（N=104,m0=8,m=4）使用assortativewiring算法对网络增加聚类系数图4在BA无标度网络中，聚类系数与局域搜索免疫性能之间的关19对于局域搜索免疫的改进局域免疫算法是随机选择一个节点，然后按照一定要求搜索。如果一个网络是由几个小的不连通的网络组成，那么这种策略就有可能一直在一个小的网络中进行循环搜索。解决方案：n种局域搜索免疫同时进行

对于局域搜索免疫的改进局域免疫算法是随机选择一个节点，然后按20改进的局域搜索免疫问题:n=?改进的局域搜索免疫问题:n=?21删除边的免疫无论是熟人免疫还是目标免疫，基本思想都是找到度数大的节点进行免疫，也就相当于对度数大节点的所有的边进行删除，但是并不是所有的边都有必要删除的。比如节点i的度数很大，而节点j的度数很小，因为度数小的节点在疾病传播过程中起的作用很小，所以边E(i,j)也就没有必要删除。如果是通过物理的方式对网络进行免疫，那么对节点进行免疫，就极大的破坏了网络的连通度。删除边的免疫无论是熟人免疫还是目标免疫，基本思想都是找到度数22连通度指的是两个随机选择的个体之间存在路径相连接的概率，其决定了网络的活跃性，可以通过宽度优先搜索算法[6]来计算。宽度优先搜索算法是一种图形搜索策略，从一个源节点开始搜索其邻居节点，然后搜索与邻居节点最近的节点，直到满足条件为止。连通度指的是两个随机选择的个体之间存在路径相连接的概率，其决23为了有效地降低感染节点的密度，并且提高网络的连通度，我们提出了删除边的免疫策略(EdgesCutImmunizationStrategy,EC免疫策略)。首先是按照节点的度数进行排序，从高到低选择一定数目的节点，删除节点与节点直接相连的边。为了降低病毒在度数大节点之间的传播，也要删除边E(i,j)，如果其余节点i具有多于一条边连接到给定数目节点j。为了有效地降低感染节点的密度，并且提高网络的连通度，我们提出24复杂网络的免疫策略课件25删除边的免疫删除边的免疫26在模型中测试免疫策略性能图5实验采用SIS病毒传播模型，在ER随机网络(图a:N为104,<k>=4)，BA无标度网络(图b：N=104,m0=8,m=4；图c：N=104,m0=8,m=6)中进行仿真。F为感染节点的密度，q为免疫边的比例。在模型中测试免疫策略性能图5实验采用SIS病毒传播模型，在E27在模型中测试连通度图6研究目标免疫和EC免疫策略对网络模型连通度C的影响。其中q为免疫边的比例在模型中测试连通度图6研究目标免疫和EC免疫策略对网络模型28在现实网络中测试免疫的性能图7基于SIS病毒传播模型，分别采用目标免疫和EC策略对于(a)AS网络,(b)HEP-Th网络和(c)PGP网络，进行免疫，根据删除边的比例q的变化研究感染节点概率F的变化。在现实网络中测试免疫的性能图7基于SIS病毒传播模型，分别采29在现实网络中测试连通度图8研究目标免疫和EC免疫策略对现实网络连通度C的影响。其中q为免疫边的比例在现实网络中测试连通度图8研究目标免疫和EC免疫策略对现实网30对于EC免疫策略的思考EC免疫是从全局角度来对边进行免疫，也同样可以从局部信息的角度来处理。关于边的免疫，一直感觉不是很切实际，毕竟在现实生活中，都是对整个节点进行免疫，比如某人患有H1N1，就把他完全隔离，并没有要求这个人只能见某些人或不能见某些人，所以对于EC免疫策略的实用性方面一直存在疑惑。对于EC免疫策略的思考EC免疫是从全局角度来对边进行免疫，31多重图形剖分免疫以往的免疫策略的免疫原则为：根据度数或者介数，对重要的节点进行免疫。YipingChen通过对目标免疫分析发现：目标免疫策略把网络分成好几种小的网络。小的网络在病毒传播过程中起的作用很小，所以把网络分成好几个小的网络实际上浪费了代价。Yiping通过嵌入分割算法（nesteddissectionalgorithm）[8]把网络分成几个近似大小的网络，然后对分割集团进行免疫，提出了EGP策（equalgraphpartitioningimmunizationstrategy）。

多重图形剖分免疫以往的免疫策略的免疫原则为：根据度数或者介数32EGP免疫策略可以比目标免疫少用5%-50%的免疫剂量，达到相同的感染密度。原则是免疫一组节点(separatorgroup)，节点把网络分成几个相似大小的集团。图9来自文献7图933类似于EGP算法的策略，可以同样采用嵌入式分割算法，用边对网络进行划分，提出了多重图形剖分算法。

图10Nesteddissection的执行过程（取自文献8）类似于EGP算法的策略，可以同样采用嵌入式分割算法，用边对网34在linux环境下通过metis软件中的kmetis和pmetis程序来对网络划分，结果是把每个顶点对应的集团编号存放在文本中，然后对于不同集团之间的边进行免疫。实验如图11：图11在linux环境下通过metis软件中的kmetis和pme35对于有向网络免疫的思考M.E.J.Newman的Emailnetworksandthespreadofcomputerviruses[9]文章，对email有向网络进行分析免疫，首先是把Email网络进行分析图12Email的分析来自文献9对于有向网络免疫的思考M.E.J.Newman的Em36然后根据出度对于Email网络进行目标免疫图13对Email网络进行免疫来自文献9然后根据出度对于Email网络进行目标免疫图13对Emai37针对有向网络的免疫，我思考的是使用类似于pagerank算法来求解。Pagerank的思想是对网页进行打分，原理：网页A指向网页B，则B=A的分值/A的出度+……。针对SIS病毒传播模型，比如节点B,C,D三个节点指向节点A，那么节点A感染病毒的概率为至少有一个邻居节点为感染节点A=1-(1-B)(1-C)(1-D)所以针对有向无权网络使用SIS病毒传播模型：

如果n与i有边连接,E(n,i)=1，否则为0。value(i)为节点i感染疾病的可能性问题：大型稀疏矩阵的求解针对有向网络的免疫，我思考的是使用类似于pagerank38参考文献[1]ReuvenCohen,ShlomoHavlin,Danielben.Avraham,PhysRevLett91(2003)277901[2]Pastor-SatorrasR,VespignaniA,Phys.Rev.E.65(2002)036104[3]Madar,N.;Kalisky,T.;Cohen,R.;Ben-Avraham,D，etc.Eur.Phys.J.B,38(2004):269-276[4]StanleyMilgram,"TheSmallWorldProblem",PsychologyToday,1967,Vol.2,60-67[5]ShiZhou,RaulJ.Mondragon,NewJournalofPhysics9(2007)173[6]AndyYoo,EdmondChow,etc,Proceedingsofthe2005ACM/IEEEconferenceonSupercomputing,2005.[7]ChenY,PaulG,etc,PhysRevLett.101(2008)058701.[8]BruceHendrickson,RobertLeland，Amultilevelalgorithmforpartitioninggraphs，Supercomputing，Tech.reportSAND93-1301,SandiaNationalLaboratories,Albuquerque,NM,1993[9]M.E.J.Newman,S.Forrest,andJ.Balthrop,Phys.Rev.E66,035101(2002).参考文献[1]ReuvenCohen,ShlomoH39结语从八月份到现在只是有想法，编程验证。免疫算法对我来说只是一个黑匣子，下一步应该进行”白盒测试”请老师，师兄，师姐批评指正结语从八月份到现在只是有想法，编程验证。免疫算法对我来说只是40谢谢大家复杂网络的免疫策略课件41复杂网络的免疫策略

纪鹏导师葛洪伟江南大学信息工程学院复杂网络的免疫策略纪鹏42大纲基本的复杂网络免疫策略改变假设条件：局域搜索免疫改变免疫对象：删除边的免疫改变免疫原则：多重图形剖分免疫对于有向网络免疫的思考大纲基本的复杂网络免疫策略43基本的免疫策略目标：通过对部分人接种而有效地控制疾病的传播基于局域信息免疫uniformimmunization(均匀免疫)acquaintanceimmunization（熟人免疫）基于全局信息targetedimmunization（目标免疫）基本的免疫策略目标：通过对部分人接种而有效地控制疾病的传44均匀免疫均匀免疫，顾名思义完全随机的从网络中选择一部分节点进行免疫。它对于度数大的节点和度数小的节点平等对待在无标度网络中对应的免疫临界值均匀免疫均匀免疫，顾名思义完全随机的从网络中选择一部分节点进45均匀免疫均匀免疫46熟人免疫随机选择比例为p的节点，然后再从这些选择的节点中随机选择一个邻居节点进行免疫由于度数大的节点也就意味着有更多的节点与之相连，所以熟人免疫比均匀免疫的效率要好得多熟人免疫随机选择比例为p的节点，然后再从这些选择的节点中随机47熟人免疫熟人免疫48目标免疫根据无标度网络的不均匀特性，可以进行有选择的目标免疫，即选取度数大的节点进行免疫在BA无标度网络中，目标免疫对应的免疫临界值为

目标免疫根据无标度网络的不均匀特性，可以进行有选择的目标免疫49目标免疫目标免疫50不同免疫策略的比较在网络规模为106，幂率指数在2-3.5之间变化的无标度网络中不同策略对应的免疫临界值均匀免疫(空心圆)熟人免疫（空心三角形）目标免疫（空心正方形）图1（参考文献[3]）不同免疫策略的比较在网络规模为106，幂率指数在2-351局域搜索免疫熟人免疫假设条件为已知当前节点的度目标免疫假设条件为已知所有节点的度假设已知邻居节点的度信息，怎样进行免疫呢？局域搜索免疫熟人免疫假设条件为已知当前节点的度521967年，哈佛大学的社会心理学家StanleyMilgram就设计了一个连锁信件实验[4]。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人，信中放了一个波士顿股票经纪人的名字，信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终大部分信在经过五、六个步骤后都抵达了该股票经纪人。1967年，哈佛大学的社会心理学家StanleyMilgr53Sixdegreesofseparation成功传递信件的前提是已知朋友中成功传递信件的程度类似于该实验过程，提出了局域搜索免疫(localsearchimmunizationstrategy)

Sixdegreesofseparation成功传递信54复杂网络的免疫策略课件55局域搜索免疫局域搜索免疫56在模型中实验图2实验采用SIS病毒传播模型，在ER随机网络(a:N为104,<k>=4)，BA无标度网络模型(b：N=104,m0=8,m=4；c：N=104,m0=8,m=6)中进行仿真。F为感染节点的密度，q为免疫节点的比例。在模型中实验图2实验采用SIS病毒传播模型，在ER随机网络(57在现实网络中实验图3实验采用SIS病毒传播模型在(autonomoussystem)AS层面的Internet网络和HighEnergyPhysics-Theory(HEP-Th)网络中测试局域搜索免疫的性能。F为感染节点的密度，q为免疫节点的比例在现实网络中实验图3实验采用SIS病毒传播模型在(auton58该免疫与聚类系数之间的关系由于局域搜索免疫是通过搜索邻居节点中度数最大的节点进行免疫，直观来讲该免疫的性能与网络的聚类系数有着某些联系Assortativewiring算法[5]能在保持节点度分布不变的前提下，增加网络的聚类系数。任意选择两条边，对两条边对应的四个顶点重新连接：用一条边连接两个度数比较大的节点，另一条边连接两个度数比较小的节点。该免疫与聚类系数之间的关系由于局域搜索免疫是通过搜索邻居节点59图4在BA无标度网络中，聚类系数与局域搜索免疫性能之间的关系。F为算法的免疫临界值，c为网络的聚类系数对BA无标度网络（N=104,m0=8,m=4）使用assortativewiring算法对网络增加聚类系数图4在BA无标度网络中，聚类系数与局域搜索免疫性能之间的关60对于局域搜索免疫的改进局域免疫算法是随机选择一个节点，然后按照一定要求搜索。如果一个网络是由几个小的不连通的网络组成，那么这种策略就有可能一直在一个小的网络中进行循环搜索。解决方案：n种局域搜索免疫同时进行

对于局域搜索免疫的改进局域免疫算法是随机选择一个节点，然后按61改进的局域搜索免疫问题:n=?改进的局域搜索免疫问题:n=?62删除边的免疫无论是熟人免疫还是目标免疫，基本思想都是找到度数大的节点进行免疫，也就相当于对度数大节点的所有的边进行删除，但是并不是所有的边都有必要删除的。比如节点i的度数很大，而节点j的度数很小，因为度数小的节点在疾病传播过程中起的作用很小，所以边E(i,j)也就没有必要删除。如果是通过物理的方式对网络进行免疫，那么对节点进行免疫，就极大的破坏了网络的连通度。删除边的免疫无论是熟人免疫还是目标免疫，基本思想都是找到度数63连通度指的是两个随机选择的个体之间存在路径相连接的概率，其决定了网络的活跃性，可以通过宽度优先搜索算法[6]来计算。宽度优先搜索算法是一种图形搜索策略，从一个源节点开始搜索其邻居节点，然后搜索与邻居节点最近的节点，直到满足条件为止。连通度指的是两个随机选择的个体之间存在路径相连接的概率，其决64为了有效地降低感染节点的密度，并且提高网络的连通度，我们提出了删除边的免疫策略(EdgesCutImmunizationStrategy,EC免疫策略)。首先是按照节点的度数进行排序，从高到低选择一定数目的节点，删除节点与节点直接相连的边。为了降低病毒在度数大节点之间的传播，也要删除边E(i,j)，如果其余节点i具有多于一条边连接到给定数目节点j。为了有效地降低感染节点的密度，并且提高网络的连通度，我们提出65复杂网络的免疫策略课件66删除边的免疫删除边的免疫67在模型中测试免疫策略性能图5实验采用SIS病毒传播模型，在ER随机网络(图a:N为104,<k>=4)，BA无标度网络(图b：N=104,m0=8,m=4；图c：N=104,m0=8,m=6)中进行仿真。F为感染节点的密度，q为免疫边的比例。在模型中测试免疫策略性能图5实验采用SIS病毒传播模型，在E68在模型中测试连通度图6研究目标免疫和EC免疫策略对网络模型连通度C的影响。其中q为免疫边的比例在模型中测试连通度图6研究目标免疫和EC免疫策略对网络模型69在现实网络中测试免疫的性能图7基于SIS病毒传播模型，分别采用目标免疫和EC策略对于(a)AS网络,(b)HEP-Th网络和(c)PGP网络，进行免疫，根据删除边的比例q的变化研究感染节点概率F的变化。在现实网络中测试免疫的性能图7基于SIS病毒传播模型，分别采70在现实网络中测试连通度图8研究目标免疫和EC免疫策略对现实网络连通度C的影响。其中q为免疫边的比例在现实网络中测试连通度图8研究目标免疫和EC免疫策略对现实网71对于EC免疫策略的思考EC免疫是从全局角度来对边进行免疫，也同样可以从局部信息的角度来处理。关于边的免疫，一直感觉不是很切实际，毕竟在现实生活中，都是对整个节点进行免疫，比如某人患有H1N1，就把他完全隔离，并没有要求这个人只能见某些人或不能见某些人，所以对于EC免疫策略的实用性方面一直存在疑惑。对于EC免疫策略的思考EC免疫是从全局角度来对边进行免疫，72多重图形剖分免疫以往的免疫策略的免疫原则为：根据度数或者介数，对重要的节点进行免疫。YipingChen通过对目标免疫分析发现：目标免疫策略把网络分成好几种小的网络。小的网络在病毒传播过程中起的作用很小，所以把网络分成好几个小的网络实际上浪费了代价。Yiping通过嵌入分割算法（nesteddissectionalgorithm）[8]把网络分成几个近似大小的网络，然后对分割集团进行免疫，提出了EGP策（equalgraphpartitioningimmunizationstrategy）。

多重图形剖分免疫以往的免疫策略的免疫原则为：根据度数或者介数73EGP免疫策略可以比目标免疫少用5%-50%的免疫剂量，达到相同的感染密度。原则是免疫一组节点(separatorgroup)，节点把网络分成几个相似大小的集团。图9来自文献7图974类似于EGP算法的策略，可以同样采用嵌入式分割算法，用边对网络进行划分，提出了多重图形剖分算法。

图10Nesteddissection的执行过程（取自文献8）类似于EGP算法的策略，可以同样采用嵌入式分割算法，用边对网75在linux环境下通过metis软件中的kmetis和pmetis程序来对网络划分，结果是把每个顶点对应的集团编号存放在文本中，然后对于不同集团之间的边进行免疫。实验如图11：图11在linux环境下通过metis软件中的kmetis和pme76对于有向网络免疫的思考M.E.J.Newman的Emailnetworksandthespreadofcomputerviruses[9]文章，对email有向网络进行分析免疫，首先是把Email网络进行分析图12Email的分析来自文献9对于有向网络免疫的思考M.E.J.Newman的Em77然后根据出度对于Email网络进行目标免疫图13对Email网络进行免疫来自文献9然后根据出度对于Email网络进行目标免疫图13对Emai78针对有向网络的免疫，我思考的是使用类似于pagerank算法来求解。Pagerank的思想是对网页进行打分，原理：网页A指向网页B，则B=A的分值/A的出度+……。针对SIS病毒传播模型，比如节点B,C,D三个节点指向节点A，那么节点A感染病毒的概率为至少有一个邻居节点为感染节点A=