復雜網絡的免疫策略ppt課件

1、復雜網絡的免疫戰(zhàn)略 紀鵬導師 葛洪偉江南大學信息工程學院大綱根本的復雜網絡免疫戰(zhàn)略改動假設條件：局域搜索免疫改動免疫對象：刪除邊的免疫改動免疫原那么：多重圖形剖分免疫對于有向網絡免疫的思索根本的免疫戰(zhàn)略 目的：經過對部分人接種而有效地控制疾病的傳播 基于局域信息 免疫uniform immunization(均勻免疫) acquaintance immunization熟人免疫 基于全局信息 targeted immunization目的免疫 均勻免疫均勻免疫，顧名思義完全隨機的從網絡中選擇一部分節(jié)點進展免疫。它對于度數大的節(jié)點和度數小的節(jié)點平等對待 在無標度網絡中對應的免疫臨界值 均勻免疫熟

2、人免疫隨機選擇比例為p的節(jié)點，然后再從這些選擇的節(jié)點中隨機選擇一個鄰居節(jié)點進展免疫 由于度數大的節(jié)點也就意味著有更多的節(jié)點與之相連，所以熟人免疫比均勻免疫的效率要好得多熟人免疫目的免疫根據無標度網絡的不均勻特性，可以進展有選擇的目的免疫，即選取度數大的節(jié)點進展免疫 在BA無標度網絡中，目的免疫對應的免疫臨界值為 目的免疫不同免疫戰(zhàn)略的比較在網絡規(guī)模為106，冪率指數 在2-3.5之間變化的無標度網絡中不同戰(zhàn)略對應的免疫臨界值均勻免疫(空心圓)熟人免疫空心三角形目的免疫空心正方形圖1參考文獻3局域搜索免疫熟人免疫假設條件為知當前節(jié)點的度目的免疫假設條件為知一切節(jié)點的度假設知鄰居節(jié)點的度信息，怎樣

3、進展免疫呢？1967年，哈佛大學的社會心思學家Stanley Milgram就設計了一個連鎖信件實驗4。他將一套連鎖信件隨機發(fā)送給居住在內布拉斯加州 奧馬哈的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為感染節(jié)點的密度，q為免疫節(jié)點的比例。在現實網絡中實驗圖3實驗采用SIS病毒傳播模型在(autonomous system)AS層面的Internet 網絡和High Energy Physics-Theory (HEP-Th)網絡中測試局域搜索免疫的性能。F為感染節(jié)點的密度，q為免疫節(jié)點的比例該免疫與聚類系數之間的關系由于局域搜索免疫是經過搜索鄰居節(jié)點中度數最大的節(jié)點進展免疫，直觀來講該免疫的性能與網絡的聚類系數有著某些聯(lián)絡 A

5、ssortative wiring 算法5能在堅持節(jié)點度分布不變的前提下，添加網絡的聚類系數。恣意選擇兩條邊，對兩條邊對應的四個頂點重新銜接：用一條邊銜接兩個度數比較大的節(jié)點，另一條邊銜接兩個度數比較小的節(jié)點。圖4 在BA無標度網絡中，聚類系數與局域搜索免疫性能之間的關系。F為算法的免疫臨界值，c為網絡的聚類系數對BA無標度網絡N=104,m0=8,m=4運用assortative wiring 算法對網絡添加聚類系數對于局域搜索免疫的改良局域免疫算法是隨機選擇一個節(jié)點，然后按照一定要求搜索。假設一個網絡是由幾個小的不連通的網絡組成，那么這種戰(zhàn)略就有能夠不斷在一個小的網絡中進展循環(huán)搜索。處理方

6、案：n種局域搜索免疫同時進展 改良的局域搜索免疫問題:n=?刪除邊的免疫無論是熟人免疫還是目的免疫，根本思想都是找到度數大的節(jié)點進展免疫，也就相當于對度數大節(jié)點的一切的邊進展刪除，但是并不是一切的邊都有必要刪除的。比如節(jié)點i的度數很大，而節(jié)點j的度數很小，由于度數小的節(jié)點在疾病傳播過程中起的作用很小，所以邊E(i,j)也就沒有必要刪除。假設是經過物理的方式對網絡進展免疫，那么對節(jié)點進展免疫，就極大的破壞了網絡的連通度。連通度指的是兩個隨機選擇的個體之間存在途徑相銜接的概率，其決議了網絡的活潑性，可以經過寬度優(yōu)先搜索算法6來計算。寬度優(yōu)先搜索算法是一種圖形搜索戰(zhàn)略，從一個源節(jié)點開場搜索其鄰居節(jié)點

7、，然后搜索與鄰居節(jié)點最近的節(jié)點，直到滿足條件為止。為了有效地降低感染節(jié)點的密度，并且提高網絡的連通度，我們提出了刪除邊的免疫戰(zhàn)略(Edges Cut Immunization Strategy, EC免疫戰(zhàn)略)。首先是按照節(jié)點的度數進展排序，從高到低選擇一定數目的節(jié)點，刪除節(jié)點與節(jié)點直接相連的邊。為了降低病毒在度數大節(jié)點之間的傳播，也要刪除邊E(i,j)，假設其他節(jié)點i具有多于一條邊銜接到給定數目節(jié)點j。 刪除邊的免疫在模型中測試免疫戰(zhàn)略性能圖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為感染節(jié)點的密度，q為免疫邊的比例。在模型中測試連通度圖6 研討目的免疫和EC免疫戰(zhàn)略對網絡模型連通度C的影響。其中q為免疫邊的比例在現實網絡中測試免疫的性能圖7基于SIS病毒傳播模型，分別采用目的免疫和EC戰(zhàn)略對于(a)AS網絡,(b)HEP-Th網絡和(c)PGP網絡，進展免疫，根據刪除邊的比例q的變化研討感染節(jié)點概率F的變化。在現實網絡中測試連通度圖8研討目的免疫和EC免疫戰(zhàn)略對現實網絡連通度C的影響。其中q為免疫邊的比例對于EC免疫戰(zhàn)略的思索 EC免疫是從全局角度來對邊進展免疫，也同樣可以從部分信息的角度來處置。關于邊的免疫，不斷覺得不是很真實踐，畢竟在現

9、實生活中，都是對整個節(jié)點進展免疫，比如某人患有H1N1，就把他完全隔離，并沒有要求這個人只能見某些人或不能見某些人，所以對于EC免疫戰(zhàn)略的適用性方面不斷存在疑惑。多重圖形剖分免疫以往的免疫戰(zhàn)略的免疫原那么為：根據度數或者介數，對重要的節(jié)點進展免疫。Yiping Chen 經過對目的免疫分析發(fā)現：目的免疫戰(zhàn)略把網絡分成好幾種小的網絡。小的網絡在病毒傳播過程中起的作用很小，所以把網絡分成好幾個小的網絡實踐上浪費了代價。Yiping 經過嵌入分割算法nested dissection algorithm8把網絡分成幾個近似大小的網絡，然后對分割集團進展免疫，提出了EGP策equal graph pa

10、rtitioning immunization strategy。 EGP免疫戰(zhàn)略可以比目的免疫少用5%-50%的免疫劑量，到達一樣的感染密度。原那么是 免疫一組節(jié)點(separator group)，節(jié)點把網絡分成幾個類似大小的集團。 圖9來自文獻7類似于EGP算法的戰(zhàn)略，可以同樣采用嵌入式分割算法，用邊對網絡進展劃分，提出了多重圖形剖分算法。 圖10 Nested dissection 的執(zhí)行過程取自文獻8在linux環(huán)境下經過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病毒傳播模型，比如節(jié)點B,C,D三個節(jié)點指向節(jié)點A，那么節(jié)點A感染病毒的概率為至少有一個鄰居節(jié)

12、點為感染節(jié)點A=1-(1-B)(1-C)(1-D)所以針對有向無權網絡運用SIS病毒傳播模型： 假設n與i有邊銜接, E(n,i)=1，否那么為0。value(i)為節(jié)點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