复杂网络的免疫策略ppt课件

1、复杂网络的免疫战略 纪鹏导师 葛洪伟江南大学信息工程学院大纲根本的复杂网络免疫战略改动假设条件：局域搜索免疫改动免疫对象：删除边的免疫改动免疫原那么：多重图形剖分免疫对于有向网络免疫的思索根本的免疫战略 目的：经过对部分人接种而有效地控制疾病的传播 基于局域信息 免疫uniform immunization(均匀免疫) acquaintance immunization熟人免疫 基于全局信息 targeted immunization目的免疫 均匀免疫均匀免疫，顾名思义完全随机的从网络中选择一部分节点进展免疫。它对于度数大的节点和度数小的节点平等对待 在无标度网络中对应的免疫临界值 均匀免疫熟

2、人免疫随机选择比例为p的节点，然后再从这些选择的节点中随机选择一个邻居节点进展免疫 由于度数大的节点也就意味着有更多的节点与之相连，所以熟人免疫比均匀免疫的效率要好得多熟人免疫目的免疫根据无标度网络的不均匀特性，可以进展有选择的目的免疫，即选取度数大的节点进展免疫 在BA无标度网络中，目的免疫对应的免疫临界值为 目的免疫不同免疫战略的比较在网络规模为106，幂率指数 在2-3.5之间变化的无标度网络中不同战略对应的免疫临界值均匀免疫(空心圆)熟人免疫空心三角形目的免疫空心正方形图1参考文献3局域搜索免疫熟人免疫假设条件为知当前节点的度目的免疫假设条件为知一切节点的度假设知邻居节点的度信息，怎样

3、进展免疫呢？1967年，哈佛大学的社会心思学家Stanley Milgram就设计了一个连锁信件实验4。他将一套连锁信件随机发送给居住在内布拉斯加州 奥马哈的160个人，信中放了一个波士顿股票经纪人的名字，信中要求每个收信人将这套信寄给本人以为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终大部分信在经过五、六个步骤后都抵达了该股票经纪人。 Six degrees of separation胜利传送信件的前提是 知朋友中胜利传送信件的程度 类似于该实验过程，提出了局域搜索免疫(local search immunization strategy) 局域搜索免疫在模型中实验图2实验采用S

4、IS病毒传播模型，在ER随机网络(a: N为104,=4)，BA无标度网络模型(b：N= 104,m0=8,m=4；c：N= 104,m0=8,m=6)中进展仿真。F为感染节点的密度，q为免疫节点的比例。在现实网络中实验图3实验采用SIS病毒传播模型在(autonomous system)AS层面的Internet 网络和High Energy Physics-Theory (HEP-Th)网络中测试局域搜索免疫的性能。F为感染节点的密度，q为免疫节点的比例该免疫与聚类系数之间的关系由于局域搜索免疫是经过搜索邻居节点中度数最大的节点进展免疫，直观来讲该免疫的性能与网络的聚类系数有着某些联络 A

5、ssortative wiring 算法5能在坚持节点度分布不变的前提下，添加网络的聚类系数。恣意选择两条边，对两条边对应的四个顶点重新衔接：用一条边衔接两个度数比较大的节点，另一条边衔接两个度数比较小的节点。图4 在BA无标度网络中，聚类系数与局域搜索免疫性能之间的关系。F为算法的免疫临界值，c为网络的聚类系数对BA无标度网络N=104,m0=8,m=4运用assortative wiring 算法对网络添加聚类系数对于局域搜索免疫的改良局域免疫算法是随机选择一个节点，然后按照一定要求搜索。假设一个网络是由几个小的不连通的网络组成，那么这种战略就有能够不断在一个小的网络中进展循环搜索。处理方

6、案：n种局域搜索免疫同时进展 改良的局域搜索免疫问题:n=?删除边的免疫无论是熟人免疫还是目的免疫，根本思想都是找到度数大的节点进展免疫，也就相当于对度数大节点的一切的边进展删除，但是并不是一切的边都有必要删除的。比如节点i的度数很大，而节点j的度数很小，由于度数小的节点在疾病传播过程中起的作用很小，所以边E(i,j)也就没有必要删除。假设是经过物理的方式对网络进展免疫，那么对节点进展免疫，就极大的破坏了网络的连通度。连通度指的是两个随机选择的个体之间存在途径相衔接的概率，其决议了网络的活泼性，可以经过宽度优先搜索算法6来计算。宽度优先搜索算法是一种图形搜索战略，从一个源节点开场搜索其邻居节点

7、，然后搜索与邻居节点最近的节点，直到满足条件为止。为了有效地降低感染节点的密度，并且提高网络的连通度，我们提出了删除边的免疫战略(Edges Cut Immunization Strategy, EC免疫战略)。首先是按照节点的度数进展排序，从高到低选择一定数目的节点，删除节点与节点直接相连的边。为了降低病毒在度数大节点之间的传播，也要删除边E(i,j)，假设其他节点i具有多于一条边衔接到给定数目节点j。 删除边的免疫在模型中测试免疫战略性能图5实验采用SIS病毒传播模型，在ER随机网络(图a: N为104,=4)，BA无标度网络 (图b：N= 104,m0=8,m=4；图c：N= 104,m

8、0=8,m=6)中进展仿真。F为感染节点的密度，q为免疫边的比例。在模型中测试连通度图6 研讨目的免疫和EC免疫战略对网络模型连通度C的影响。其中q为免疫边的比例在现实网络中测试免疫的性能图7基于SIS病毒传播模型，分别采用目的免疫和EC战略对于(a)AS网络,(b)HEP-Th网络和(c)PGP网络，进展免疫，根据删除边的比例q的变化研讨感染节点概率F的变化。在现实网络中测试连通度图8研讨目的免疫和EC免疫战略对现实网络连通度C的影响。其中q为免疫边的比例对于EC免疫战略的思索 EC免疫是从全局角度来对边进展免疫，也同样可以从部分信息的角度来处置。关于边的免疫，不断觉得不是很真实践，毕竟在现

9、实生活中，都是对整个节点进展免疫，比如某人患有H1N1，就把他完全隔离，并没有要求这个人只能见某些人或不能见某些人，所以对于EC免疫战略的适用性方面不断存在疑惑。多重图形剖分免疫以往的免疫战略的免疫原那么为：根据度数或者介数，对重要的节点进展免疫。Yiping Chen 经过对目的免疫分析发现：目的免疫战略把网络分成好几种小的网络。小的网络在病毒传播过程中起的作用很小，所以把网络分成好几个小的网络实践上浪费了代价。Yiping 经过嵌入分割算法nested dissection algorithm8把网络分成几个近似大小的网络，然后对分割集团进展免疫，提出了EGP策equal graph pa

10、rtitioning immunization strategy。 EGP免疫战略可以比目的免疫少用5%-50%的免疫剂量，到达一样的感染密度。原那么是 免疫一组节点(separator group)，节点把网络分成几个类似大小的集团。 图9来自文献7类似于EGP算法的战略，可以同样采用嵌入式分割算法，用边对网络进展划分，提出了多重图形剖分算法。 图10 Nested dissection 的执行过程取自文献8在linux环境下经过metis软件中的kmetis和pmetis程序来对网络划分，结果是把每个顶点对应的集团编号存放在文本中，然后对于不同集团之间的边进展免疫。实验如图11：图11对于

11、有向网络免疫的思索M. E. J. Newman的 networks and the spread of computer viruses9文章，对email有向网络进展分析免疫，首先是把Email网络进展分析图12 Email的分析来自文献9然后根据出度对于Email网络进展目的免疫图13 对Email网络进展免疫来自文献9 针对有向网络的免疫，我思索的是运用类似于pagerank 算法来求解。 Pagerank的思想是对网页进展打分，原理：网页A指向网页B，那么B=A的分值/A的出度+。针对SIS病毒传播模型，比如节点B,C,D三个节点指向节点A，那么节点A感染病毒的概率为至少有一个邻居节

12、点为感染节点A=1-(1-B)(1-C)(1-D)所以针对有向无权网络运用SIS病毒传播模型： 假设n与i有边衔接, E(n,i)=1，否那么为0。value(i)为节点i感染疾病的能够性问题：大型稀疏矩阵的求解参考文献1 Reuven Cohen, Shlomo Havlin, Daniel ben.Avraham, Phys Rev Lett 91 (2003) 2779012 Pastor-Satorras R, Vespignani A, Phys. Rev. E. 65 (2002) 0361043 Madar, N.; Kalisky, T.; Cohen, R.; Ben-Avr

13、aham, D，etc.Eur.Phys.J.B, 38(2004):269-2764 Stanley Milgram, The Small World Problem, Psychology Today, 1967, Vol. 2, 60-67 5 Shi Zhou, Raul J. Mondragon, New Journal of Physics 9(2007) 1736 Andy Yoo, Edmond Chow, etc,Proceedings of the 2005 ACM/IEEE conference on Supercomputing, 2005.7 Chen Y, Paul G, etc, Phys Rev Lett. 101(2021) 058701.8 Bruce Hendrickson, Robert Leland， A multilevel algorithm for partitioning graphs，Supercomputing，Tech. re