1、復(fù)雜網(wǎng)絡(luò)的免疫策略 紀(jì)鵬導(dǎo)師 葛洪偉江南大學(xué)信息工程學(xué)院大綱基本的復(fù)雜網(wǎng)絡(luò)免疫策略改變假設(shè)條件：局域搜索免疫改變免疫對(duì)象：刪除邊的免疫改變免疫原則：多重圖形剖分免疫對(duì)于有向網(wǎng)絡(luò)免疫的思考基本的免疫策略 目標(biāo)：通過(guò)對(duì)部分人接種而有效地控制疾病的傳播 基于局域信息 免疫uniform immunization(均勻免疫) acquaintance immunization（熟人免疫） 基于全局信息 targeted immunization（目標(biāo)免疫） 均勻免疫均勻免疫，顧名思義完全隨機(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)與之相連，所以熟人免疫比均勻免疫的效率要好得多熟人免疫目標(biāo)免疫根據(jù)無(wú)標(biāo)度網(wǎng)絡(luò)的不均勻特性，可以進(jìn)行有選擇的目標(biāo)免疫，即選取度數(shù)大的節(jié)點(diǎn)進(jìn)行免疫 在BA無(wú)標(biāo)度網(wǎng)絡(luò)中，目標(biāo)免疫對(duì)應(yīng)的免疫臨界值為 目標(biāo)免疫不同免疫策略的比較在網(wǎng)絡(luò)規(guī)模為106，冪率指數(shù) 在2-3.5之間變化的無(wú)標(biāo)度網(wǎng)絡(luò)中不同策略對(duì)應(yīng)的免疫臨界值均勻免疫(空心圓)熟人免疫（空心三角形）目標(biāo)免疫（空心正方形）圖1（參考文獻(xiàn)3）局域搜索免疫熟人免疫假設(shè)條件為已知當(dāng)前節(jié)點(diǎn)的度目標(biāo)免疫假設(shè)條件為已知所有節(jié)點(diǎn)的度假設(shè)已

3、知鄰居節(jié)點(diǎn)的度信息，怎樣進(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è)收信人將這套信寄給自己認(rèn)為是比較接近那個(gè)股票經(jīng)紀(jì)人的朋友。朋友收信后照此辦理。最終大部分信在經(jīng)過(guò)五、六個(gè)步驟后都抵達(dá)了該股票經(jīng)紀(jì)人。 Six degrees of separation成功傳遞信件的前提是 已知朋友中成功傳遞信件的程度 類似于該實(shí)驗(yàn)過(guò)程，提出了局域搜索免疫(local search immunization strategy) 局域搜索免疫

4、在模型中實(shí)驗(yàn)圖2實(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,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)的比例該免疫與聚類系數(shù)之間的關(guān)系由于局域搜索免疫是通過(guò)搜索鄰居節(jié)點(diǎn)中度數(shù)最大的節(jié)點(diǎn)進(jìn)行免疫，直觀來(lái)講該免疫的性能與網(wǎng)絡(luò)

5、的聚類系數(shù)有著某些聯(lián)系 Assortative wiring 算法5能在保持節(jié)點(diǎn)度分布不變的前提下，增加網(wǎng)絡(luò)的聚類系數(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ò)中，聚類系數(shù)與局域搜索免疫性能之間的關(guān)系。F為算法的免疫臨界值，c為網(wǎng)絡(luò)的聚類系數(shù)對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)（N=104,m0=8,m=4）使用assortative wiring 算法對(duì)網(wǎng)絡(luò)增加聚類系數(shù)對(duì)于局域搜索免疫的改進(jìn)局域免疫算法是隨機(jī)選擇一個(gè)節(jié)點(diǎn)，然后按照一定要求搜索。如果一個(gè)網(wǎng)絡(luò)是由幾個(gè)小的不連通的網(wǎng)絡(luò)組成，那么這種策略就有可能一直在一個(gè)

6、小的網(wǎng)絡(luò)中進(jìn)行循環(huán)搜索。解決方案：n種局域搜索免疫同時(shí)進(jìn)行 改進(jìn)的局域搜索免疫問(wèn)題:n=?刪除邊的免疫無(wú)論是熟人免疫還是目標(biāo)免疫，基本思想都是找到度數(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ù)很小，因?yàn)槎葦?shù)小的節(jié)點(diǎn)在疾病傳播過(guò)程中起的作用很小，所以邊E(i,j)也就沒(méi)有必要?jiǎng)h除。如果是通過(guò)物理的方式對(duì)網(wǎng)絡(luò)進(jìn)行免疫，那么對(duì)節(jié)點(diǎn)進(jìn)行免疫，就極大的破壞了網(wǎng)絡(luò)的連通度。連通度指的是兩個(gè)隨機(jī)選擇的個(gè)體之間存在路徑相連接的概率，其決定了網(wǎng)絡(luò)的活躍性，可以通過(guò)寬度優(yōu)先搜索算法6來(lái)計(jì)算。寬度優(yōu)先搜索算法是一種圖形搜索策略，

7、從一個(gè)源節(jié)點(diǎn)開(kāi)始搜索其鄰居節(jié)點(diǎn)，然后搜索與鄰居節(jié)點(diǎn)最近的節(jié)點(diǎn)，直到滿足條件為止。為了有效地降低感染節(jié)點(diǎn)的密度，并且提高網(wǎng)絡(luò)的連通度，我們提出了刪除邊的免疫策略(Edges Cut Immunization Strategy, EC免疫策略)。首先是按照節(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)，如果其余節(jié)點(diǎn)i具有多于一條邊連接到給定數(shù)目節(jié)點(diǎn)j。 刪除邊的免疫在模型中測(cè)試免疫策略性能圖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,

8、m=4；圖c：N= 104,m0=8,m=6)中進(jìn)行仿真。F為感染節(jié)點(diǎn)的密度，q為免疫邊的比例。在模型中測(cè)試連通度圖6 研究目標(biāo)免疫和EC免疫策略對(duì)網(wǎng)絡(luò)模型連通度C的影響。其中q為免疫邊的比例在現(xiàn)實(shí)網(wǎng)絡(luò)中測(cè)試免疫的性能圖7基于SIS病毒傳播模型，分別采用目標(biāo)免疫和EC策略對(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研究目標(biāo)免疫和EC免疫策略對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)連通度C的影響。其中q為免疫邊的比例對(duì)于EC免疫策略的思考 EC免疫是從全局角度來(lái)對(duì)邊進(jìn)行免疫，也同樣可以從局部信息的角度來(lái)處理。關(guān)于邊的免疫，

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

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

11、的邊進(jìn)行免疫。實(shí)驗(yàn)如圖11：圖11對(duì)于有向網(wǎng)絡(luò)免疫的思考M. E. J. Newman的 Email 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)行目標(biāo)免疫圖13 對(duì)Email網(wǎng)絡(luò)進(jìn)行免疫來(lái)自文獻(xiàn)9 針對(duì)有向網(wǎng)絡(luò)的免疫，我思考的是使用類似于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é)

12、點(diǎn)A，那么節(jié)點(diǎn)A感染病毒的概率為至少有一個(gè)鄰居節(jié)點(diǎn)為感染節(jié)點(diǎn)A=1-(1-B)(1-C)(1-D)所以針對(duì)有向無(wú)權(quán)網(wǎng)絡(luò)使用SIS病毒傳播模型： 如果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,

13、 T.; Cohen, R.; Ben-Avraham, 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(2008) 058701.8 Bruce Hendrickson, Robert Leland， A multilevel algorithm for partitioning graphs，Supercomputing，Tech.