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

1、復(fù)雜網(wǎng)絡(luò)的免疫策略第1頁，共41頁，2022年，5月20日，13點27分，星期二大綱基本的復(fù)雜網(wǎng)絡(luò)免疫策略改變假設(shè)條件：局域搜索免疫改變免疫對象：刪除邊的免疫改變免疫原則：多重圖形剖分免疫對于有向網(wǎng)絡(luò)免疫的思考第2頁，共41頁，2022年，5月20日，13點27分，星期二基本的免疫策略 目標(biāo)：通過對部分人接種而有效地控制疾病的傳播 基于局域信息 免疫uniform immunization(均勻免疫) acquaintance immunization（熟人免疫） 基于全局信息 targeted immunization（目標(biāo)免疫） 第3頁，共41頁，2022年，5月20日，13點27分，星期

2、二均勻免疫均勻免疫，顧名思義完全隨機(jī)的從網(wǎng)絡(luò)中選擇一部分節(jié)點進(jìn)行免疫。它對于度數(shù)大的節(jié)點和度數(shù)小的節(jié)點平等對待 在無標(biāo)度網(wǎng)絡(luò)中對應(yīng)的免疫臨界值 第4頁，共41頁，2022年，5月20日，13點27分，星期二均勻免疫第5頁，共41頁，2022年，5月20日，13點27分，星期二熟人免疫隨機(jī)選擇比例為p的節(jié)點，然后再從這些選擇的節(jié)點中隨機(jī)選擇一個鄰居節(jié)點進(jìn)行免疫 由于度數(shù)大的節(jié)點也就意味著有更多的節(jié)點與之相連，所以熟人免疫比均勻免疫的效率要好得多第6頁，共41頁，2022年，5月20日，13點27分，星期二熟人免疫第7頁，共41頁，2022年，5月20日，13點27分，星期二目標(biāo)免疫根據(jù)無標(biāo)度網(wǎng)絡(luò)

3、的不均勻特性，可以進(jìn)行有選擇的目標(biāo)免疫，即選取度數(shù)大的節(jié)點進(jìn)行免疫 在BA無標(biāo)度網(wǎng)絡(luò)中，目標(biāo)免疫對應(yīng)的免疫臨界值為 第8頁，共41頁，2022年，5月20日，13點27分，星期二目標(biāo)免疫第9頁，共41頁，2022年，5月20日，13點27分，星期二不同免疫策略的比較在網(wǎng)絡(luò)規(guī)模為106，冪率指數(shù) 在2-3.5之間變化的無標(biāo)度網(wǎng)絡(luò)中不同策略對應(yīng)的免疫臨界值均勻免疫(空心圓)熟人免疫（空心三角形）目標(biāo)免疫（空心正方形）圖1（參考文獻(xiàn)3）第10頁，共41頁，2022年，5月20日，13點27分，星期二局域搜索免疫熟人免疫假設(shè)條件為已知當(dāng)前節(jié)點的度目標(biāo)免疫假設(shè)條件為已知所有節(jié)點的度假設(shè)已知鄰居節(jié)點的度信

4、息，怎樣進(jìn)行免疫呢？第11頁，共41頁，2022年，5月20日，13點27分，星期二1967年，哈佛大學(xué)的社會心理學(xué)家Stanley Milgram就設(shè)計了一個連鎖信件實驗4。他將一套連鎖信件隨機(jī)發(fā)送給居住在內(nèi)布拉斯加州 奧馬哈的160個人，信中放了一個波士頓股票經(jīng)紀(jì)人的名字，信中要求每個收信人將這套信寄給自己認(rèn)為是比較接近那個股票經(jīng)紀(jì)人的朋友。朋友收信后照此辦理。最終大部分信在經(jīng)過五、六個步驟后都抵達(dá)了該股票經(jīng)紀(jì)人。 第12頁，共41頁，2022年，5月20日，13點27分，星期二Six degrees of separation成功傳遞信件的前提是 已知朋友中成功傳遞信件的程度 類似于該實

5、驗過程，提出了局域搜索免疫(local search immunization strategy) 第13頁，共41頁，2022年，5月20日，13點27分，星期二第14頁，共41頁，2022年，5月20日，13點27分，星期二局域搜索免疫第15頁，共41頁，2022年，5月20日，13點27分，星期二在模型中實驗圖2實驗采用SIS病毒傳播模型，在ER隨機(jī)網(wǎng)絡(luò)(a: N為104,=4)，BA無標(biāo)度網(wǎng)絡(luò)模型(b：N= 104,m0=8,m=4；c：N= 104,m0=8,m=6)中進(jìn)行仿真。F為感染節(jié)點的密度，q為免疫節(jié)點的比例。第16頁，共41頁，2022年，5月20日，13點27分，星期二在

6、現(xiàn)實網(wǎng)絡(luò)中實驗圖3實驗采用SIS病毒傳播模型在(autonomous system)AS層面的Internet 網(wǎng)絡(luò)和High Energy Physics-Theory (HEP-Th)網(wǎng)絡(luò)中測試局域搜索免疫的性能。F為感染節(jié)點的密度，q為免疫節(jié)點的比例第17頁，共41頁，2022年，5月20日，13點27分，星期二該免疫與聚類系數(shù)之間的關(guān)系由于局域搜索免疫是通過搜索鄰居節(jié)點中度數(shù)最大的節(jié)點進(jìn)行免疫，直觀來講該免疫的性能與網(wǎng)絡(luò)的聚類系數(shù)有著某些聯(lián)系 Assortative wiring 算法5能在保持節(jié)點度分布不變的前提下，增加網(wǎng)絡(luò)的聚類系數(shù)。任意選擇兩條邊，對兩條邊對應(yīng)的四個頂點重新連接：

7、用一條邊連接兩個度數(shù)比較大的節(jié)點，另一條邊連接兩個度數(shù)比較小的節(jié)點。第18頁，共41頁，2022年，5月20日，13點27分，星期二圖4 在BA無標(biāo)度網(wǎng)絡(luò)中，聚類系數(shù)與局域搜索免疫性能之間的關(guān)系。F為算法的免疫臨界值，c為網(wǎng)絡(luò)的聚類系數(shù)對BA無標(biāo)度網(wǎng)絡(luò)（N=104,m0=8,m=4）使用assortative wiring 算法對網(wǎng)絡(luò)增加聚類系數(shù)第19頁，共41頁，2022年，5月20日，13點27分，星期二對于局域搜索免疫的改進(jìn)局域免疫算法是隨機(jī)選擇一個節(jié)點，然后按照一定要求搜索。如果一個網(wǎng)絡(luò)是由幾個小的不連通的網(wǎng)絡(luò)組成，那么這種策略就有可能一直在一個小的網(wǎng)絡(luò)中進(jìn)行循環(huán)搜索。解決方案：n種局

8、域搜索免疫同時進(jìn)行 第20頁，共41頁，2022年，5月20日，13點27分，星期二改進(jìn)的局域搜索免疫問題:n=?第21頁，共41頁，2022年，5月20日，13點27分，星期二刪除邊的免疫無論是熟人免疫還是目標(biāo)免疫，基本思想都是找到度數(shù)大的節(jié)點進(jìn)行免疫，也就相當(dāng)于對度數(shù)大節(jié)點的所有的邊進(jìn)行刪除，但是并不是所有的邊都有必要刪除的。比如節(jié)點i的度數(shù)很大，而節(jié)點j的度數(shù)很小，因為度數(shù)小的節(jié)點在疾病傳播過程中起的作用很小，所以邊E(i,j)也就沒有必要刪除。如果是通過物理的方式對網(wǎng)絡(luò)進(jìn)行免疫，那么對節(jié)點進(jìn)行免疫，就極大的破壞了網(wǎng)絡(luò)的連通度。第22頁，共41頁，2022年，5月20日，13點27分，星

9、期二連通度指的是兩個隨機(jī)選擇的個體之間存在路徑相連接的概率，其決定了網(wǎng)絡(luò)的活躍性，可以通過寬度優(yōu)先搜索算法6來計算。寬度優(yōu)先搜索算法是一種圖形搜索策略，從一個源節(jié)點開始搜索其鄰居節(jié)點，然后搜索與鄰居節(jié)點最近的節(jié)點，直到滿足條件為止。第23頁，共41頁，2022年，5月20日，13點27分，星期二為了有效地降低感染節(jié)點的密度，并且提高網(wǎng)絡(luò)的連通度，我們提出了刪除邊的免疫策略(Edges Cut Immunization Strategy, EC免疫策略)。首先是按照節(jié)點的度數(shù)進(jìn)行排序，從高到低選擇一定數(shù)目的節(jié)點，刪除節(jié)點與節(jié)點直接相連的邊。為了降低病毒在度數(shù)大節(jié)點之間的傳播，也要刪除邊E(i,j

10、)，如果其余節(jié)點i具有多于一條邊連接到給定數(shù)目節(jié)點j。 第24頁，共41頁，2022年，5月20日，13點27分，星期二第25頁，共41頁，2022年，5月20日，13點27分，星期二刪除邊的免疫第26頁，共41頁，2022年，5月20日，13點27分，星期二在模型中測試免疫策略性能圖5實驗采用SIS病毒傳播模型，在ER隨機(jī)網(wǎng)絡(luò)(圖a: N為104,=4)，BA無標(biāo)度網(wǎng)絡(luò) (圖b：N= 104,m0=8,m=4；圖c：N= 104,m0=8,m=6)中進(jìn)行仿真。F為感染節(jié)點的密度，q為免疫邊的比例。第27頁，共41頁，2022年，5月20日，13點27分，星期二在模型中測試連通度圖6 研究目標(biāo)

11、免疫和EC免疫策略對網(wǎng)絡(luò)模型連通度C的影響。其中q為免疫邊的比例第28頁，共41頁，2022年，5月20日，13點27分，星期二在現(xiàn)實網(wǎng)絡(luò)中測試免疫的性能圖7基于SIS病毒傳播模型，分別采用目標(biāo)免疫和EC策略對于(a)AS網(wǎng)絡(luò),(b)HEP-Th網(wǎng)絡(luò)和(c)PGP網(wǎng)絡(luò)，進(jìn)行免疫，根據(jù)刪除邊的比例q的變化研究感染節(jié)點概率F的變化。第29頁，共41頁，2022年，5月20日，13點27分，星期二在現(xiàn)實網(wǎng)絡(luò)中測試連通度圖8研究目標(biāo)免疫和EC免疫策略對現(xiàn)實網(wǎng)絡(luò)連通度C的影響。其中q為免疫邊的比例第30頁，共41頁，2022年，5月20日，13點27分，星期二對于EC免疫策略的思考 EC免疫是從全局角度

12、來對邊進(jìn)行免疫，也同樣可以從局部信息的角度來處理。關(guān)于邊的免疫，一直感覺不是很切實際，畢竟在現(xiàn)實生活中，都是對整個節(jié)點進(jìn)行免疫，比如某人患有H1N1，就把他完全隔離，并沒有要求這個人只能見某些人或不能見某些人，所以對于EC免疫策略的實用性方面一直存在疑惑。第31頁，共41頁，2022年，5月20日，13點27分，星期二多重圖形剖分免疫以往的免疫策略的免疫原則為：根據(jù)度數(shù)或者介數(shù)，對重要的節(jié)點進(jìn)行免疫。Yiping Chen 通過對目標(biāo)免疫分析發(fā)現(xiàn)：目標(biāo)免疫策略把網(wǎng)絡(luò)分成好幾種小的網(wǎng)絡(luò)。小的網(wǎng)絡(luò)在病毒傳播過程中起的作用很小，所以把網(wǎng)絡(luò)分成好幾個小的網(wǎng)絡(luò)實際上浪費了代價。Yiping 通過嵌入分割

13、算法（nested dissection algorithm）8把網(wǎng)絡(luò)分成幾個近似大小的網(wǎng)絡(luò)，然后對分割集團(tuán)進(jìn)行免疫，提出了EGP策（equal graph partitioning immunization strategy）。 第32頁，共41頁，2022年，5月20日，13點27分，星期二EGP免疫策略可以比目標(biāo)免疫少用5%-50%的免疫劑量，達(dá)到相同的感染密度。原則是 免疫一組節(jié)點(separator group)，節(jié)點把網(wǎng)絡(luò)分成幾個相似大小的集團(tuán)。 圖9來自文獻(xiàn)7第33頁，共41頁，2022年，5月20日，13點27分，星期二類似于EGP算法的策略，可以同樣采用嵌入式分割算法，用邊對

14、網(wǎng)絡(luò)進(jìn)行劃分，提出了多重圖形剖分算法。 圖10 Nested dissection 的執(zhí)行過程（取自文獻(xiàn)8）第34頁，共41頁，2022年，5月20日，13點27分，星期二在linux環(huán)境下通過metis軟件中的kmetis和pmetis程序來對網(wǎng)絡(luò)劃分，結(jié)果是把每個頂點對應(yīng)的集團(tuán)編號存放在文本中，然后對于不同集團(tuán)之間的邊進(jìn)行免疫。實驗如圖11：圖11第35頁，共41頁，2022年，5月20日，13點27分，星期二對于有向網(wǎng)絡(luò)免疫的思考M. E. J. Newman的 Email networks and the spread of computer viruses9文章，對email有向網(wǎng)絡(luò)

15、進(jìn)行分析免疫，首先是把Email網(wǎng)絡(luò)進(jìn)行分析圖12 Email的分析來自文獻(xiàn)9第36頁，共41頁，2022年，5月20日，13點27分，星期二然后根據(jù)出度對于Email網(wǎng)絡(luò)進(jìn)行目標(biāo)免疫圖13 對Email網(wǎng)絡(luò)進(jìn)行免疫來自文獻(xiàn)9第37頁，共41頁，2022年，5月20日，13點27分，星期二 針對有向網(wǎng)絡(luò)的免疫，我思考的是使用類似于pagerank 算法來求解。 Pagerank的思想是對網(wǎng)頁進(jìn)行打分，原理：網(wǎng)頁A指向網(wǎng)頁B，則B=A的分值/A的出度+。針對SIS病毒傳播模型，比如節(jié)點B,C,D三個節(jié)點指向節(jié)點A，那么節(jié)點A感染病毒的概率為至少有一個鄰居節(jié)點為感染節(jié)點A=1-(1-B)(1-C)

16、(1-D)所以針對有向無權(quán)網(wǎng)絡(luò)使用SIS病毒傳播模型： 如果n與i有邊連接, E(n,i)=1，否則為0。value(i)為節(jié)點i感染疾病的可能性問題：大型稀疏矩陣的求解第38頁，共41頁，2022年，5月20日，13點27分，星期二參考文獻(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,

17、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. report SAND93-1301, Sandia National