復(fù)雜網(wǎng)絡(luò)的免疫策略ppt課件

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

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

3、進(jìn)展免疫呢？1967年，哈佛大學(xué)的社會(huì)心思學(xué)家Stanley Milgram就設(shè)計(jì)了一個(gè)連鎖信件實(shí)驗(yàn)4。他將一套連鎖信件隨機(jī)發(fā)送給居住在內(nèi)布拉斯加州 奧馬哈的160個(gè)人，信中放了一個(gè)波士頓股票經(jīng)紀(jì)人的名字，信中要求每個(gè)收信人將這套信寄給本人以為是比較接近那個(gè)股票經(jīng)紀(jì)人的朋友。朋友收信后照此辦理。最終大部分信在經(jīng)過(guò)五、六個(gè)步驟后都抵達(dá)了該股票經(jīng)紀(jì)人。 Six degrees of separation勝利傳送信件的前提是 知朋友中勝利傳送信件的程度 類(lèi)似于該實(shí)驗(yàn)過(guò)程，提出了局域搜索免疫(local search immunization strategy) 局域搜索免疫在模型中實(shí)驗(yàn)圖2實(shí)驗(yàn)采用S

4、IS病毒傳播模型，在ER隨機(jī)網(wǎng)絡(luò)(a: N為104,=4)，BA無(wú)標(biāo)度網(wǎng)絡(luò)模型(b：N= 104,m0=8,m=4；c：N= 104,m0=8,m=6)中進(jìn)展仿真。F為感染節(jié)點(diǎn)的密度，q為免疫節(jié)點(diǎn)的比例。在現(xiàn)實(shí)網(wǎng)絡(luò)中實(shí)驗(yàn)圖3實(shí)驗(yàn)采用SIS病毒傳播模型在(autonomous system)AS層面的Internet 網(wǎng)絡(luò)和High Energy Physics-Theory (HEP-Th)網(wǎng)絡(luò)中測(cè)試局域搜索免疫的性能。F為感染節(jié)點(diǎn)的密度，q為免疫節(jié)點(diǎn)的比例該免疫與聚類(lèi)系數(shù)之間的關(guān)系由于局域搜索免疫是經(jīng)過(guò)搜索鄰居節(jié)點(diǎn)中度數(shù)最大的節(jié)點(diǎn)進(jìn)展免疫，直觀來(lái)講該免疫的性能與網(wǎng)絡(luò)的聚類(lèi)系數(shù)有著某些聯(lián)絡(luò) A

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

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

7、，然后搜索與鄰居節(jié)點(diǎn)最近的節(jié)點(diǎn)，直到滿(mǎn)足條件為止。為了有效地降低感染節(jié)點(diǎn)的密度，并且提高網(wǎng)絡(luò)的連通度，我們提出了刪除邊的免疫戰(zhàn)略(Edges Cut Immunization Strategy, EC免疫戰(zhàn)略)。首先是按照節(jié)點(diǎn)的度數(shù)進(jìn)展排序，從高到低選擇一定數(shù)目的節(jié)點(diǎn)，刪除節(jié)點(diǎn)與節(jié)點(diǎn)直接相連的邊。為了降低病毒在度數(shù)大節(jié)點(diǎn)之間的傳播，也要?jiǎng)h除邊E(i,j)，假設(shè)其他節(jié)點(diǎn)i具有多于一條邊銜接到給定數(shù)目節(jié)點(diǎn)j。 刪除邊的免疫在模型中測(cè)試免疫戰(zhàn)略性能圖5實(shí)驗(yàn)采用SIS病毒傳播模型，在ER隨機(jī)網(wǎng)絡(luò)(圖a: N為104,=4)，BA無(wú)標(biāo)度網(wǎng)絡(luò) (圖b：N= 104,m0=8,m=4；圖c：N= 104,m

8、0=8,m=6)中進(jìn)展仿真。F為感染節(jié)點(diǎn)的密度，q為免疫邊的比例。在模型中測(cè)試連通度圖6 研討目的免疫和EC免疫戰(zhàn)略對(duì)網(wǎng)絡(luò)模型連通度C的影響。其中q為免疫邊的比例在現(xiàn)實(shí)網(wǎng)絡(luò)中測(cè)試免疫的性能圖7基于SIS病毒傳播模型，分別采用目的免疫和EC戰(zhàn)略對(duì)于(a)AS網(wǎng)絡(luò),(b)HEP-Th網(wǎng)絡(luò)和(c)PGP網(wǎng)絡(luò)，進(jìn)展免疫，根據(jù)刪除邊的比例q的變化研討感染節(jié)點(diǎn)概率F的變化。在現(xiàn)實(shí)網(wǎng)絡(luò)中測(cè)試連通度圖8研討目的免疫和EC免疫戰(zhàn)略對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)連通度C的影響。其中q為免疫邊的比例對(duì)于EC免疫戰(zhàn)略的思索 EC免疫是從全局角度來(lái)對(duì)邊進(jìn)展免疫，也同樣可以從部分信息的角度來(lái)處置。關(guān)于邊的免疫，不斷覺(jué)得不是很真實(shí)踐，畢竟在現(xiàn)

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

10、rtitioning immunization strategy。 EGP免疫戰(zhàn)略可以比目的免疫少用5%-50%的免疫劑量，到達(dá)一樣的感染密度。原那么是 免疫一組節(jié)點(diǎn)(separator group)，節(jié)點(diǎn)把網(wǎng)絡(luò)分成幾個(gè)類(lèi)似大小的集團(tuán)。 圖9來(lái)自文獻(xiàn)7類(lèi)似于EGP算法的戰(zhàn)略，可以同樣采用嵌入式分割算法，用邊對(duì)網(wǎng)絡(luò)進(jìn)展劃分，提出了多重圖形剖分算法。 圖10 Nested dissection 的執(zhí)行過(guò)程取自文獻(xiàn)8在linux環(huán)境下經(jīng)過(guò)metis軟件中的kmetis和pmetis程序來(lái)對(duì)網(wǎng)絡(luò)劃分，結(jié)果是把每個(gè)頂點(diǎn)對(duì)應(yīng)的集團(tuán)編號(hào)存放在文本中，然后對(duì)于不同集團(tuán)之間的邊進(jìn)展免疫。實(shí)驗(yàn)如圖11：圖11對(duì)于

11、有向網(wǎng)絡(luò)免疫的思索M. E. J. Newman的 networks and the spread of computer viruses9文章，對(duì)email有向網(wǎng)絡(luò)進(jìn)展分析免疫，首先是把Email網(wǎng)絡(luò)進(jìn)展分析圖12 Email的分析來(lái)自文獻(xiàn)9然后根據(jù)出度對(duì)于Email網(wǎng)絡(luò)進(jìn)展目的免疫圖13 對(duì)Email網(wǎng)絡(luò)進(jìn)展免疫來(lái)自文獻(xiàn)9 針對(duì)有向網(wǎng)絡(luò)的免疫，我思索的是運(yùn)用類(lèi)似于pagerank 算法來(lái)求解。 Pagerank的思想是對(duì)網(wǎng)頁(yè)進(jìn)展打分，原理：網(wǎng)頁(yè)A指向網(wǎng)頁(yè)B，那么B=A的分值/A的出度+。針對(duì)SIS病毒傳播模型，比如節(jié)點(diǎn)B,C,D三個(gè)節(jié)點(diǎn)指向節(jié)點(diǎn)A，那么節(jié)點(diǎn)A感染病毒的概率為至少有一個(gè)鄰居節(jié)

12、點(diǎn)為感染節(jié)點(diǎn)A=1-(1-B)(1-C)(1-D)所以針對(duì)有向無(wú)權(quán)網(wǎng)絡(luò)運(yùn)用SIS病毒傳播模型： 假設(shè)n與i有邊銜接, E(n,i)=1，否那么為0。value(i)為節(jié)點(diǎn)i感染疾病的能夠性問(wèn)題：大型稀疏矩陣的求解參考文獻(xiàn)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