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

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

紀鵬導師葛洪偉江南大學信息工程學院大綱基本的復雜網(wǎng)絡(luò)免疫策略改變假設(shè)條件：局域搜索免疫改變免疫對象：刪除邊的免疫改變免疫原則：多重圖形剖分免疫對于有向網(wǎng)絡(luò)免疫的思考基本的免疫策略目標：通過對部分人接種而有效地控制疾病的傳播基于局域信息免疫uniformimmunization(均勻免疫)acquaintanceimmunization（熟人免疫）基于全局信息targetedimmunization（目標免疫）均勻免疫均勻免疫，顧名思義完全隨機的從網(wǎng)絡(luò)中選擇一部分節(jié)點進行免疫。它對于度數(shù)大的節(jié)點和度數(shù)小的節(jié)點平等對待在無標度網(wǎng)絡(luò)中對應的免疫臨界值均勻免疫熟人免疫隨機選擇比例為p的節(jié)點，然后再從這些選擇的節(jié)點中隨機選擇一個鄰居節(jié)點進行免疫由于度數(shù)大的節(jié)點也就意味著有更多的節(jié)點與之相連，所以熟人免疫比均勻免疫的效率要好得多熟人免疫目標免疫根據(jù)無標度網(wǎng)絡(luò)的不均勻特性，可以進行有選擇的目標免疫，即選取度數(shù)大的節(jié)點進行免疫在BA無標度網(wǎng)絡(luò)中，目標免疫對應的免疫臨界值為

目標免疫不同免疫策略的比較在網(wǎng)絡(luò)規(guī)模為106，冪率指數(shù)在2-3.5之間變化的無標度網(wǎng)絡(luò)中不同策略對應的免疫臨界值均勻免疫(空心圓)熟人免疫（空心三角形）目標免疫（空心正方形）圖1（參考文獻[3]）局域搜索索免疫熟人免疫疫假設(shè)條條件為已已知當前前節(jié)點的的度目標免疫疫假設(shè)條條件為已已知所有有節(jié)點的的度假設(shè)已知知鄰居節(jié)節(jié)點的度度信息，，怎樣進進行免疫疫呢？1967年，哈哈佛大學學的社會會心理學學家StanleyMilgram就設(shè)設(shè)計了一一個連鎖鎖信件實實驗[4]。他他將一套套連鎖信信件隨機機發(fā)送給給居住在在內(nèi)布拉拉斯加州州奧馬馬哈的160個個人，信信中放了了一個波波士頓股股票經(jīng)紀紀人的名名字，信信中要求求每個收收信人將將這套信信寄給自自己認為為是比較較接近那那個股票票經(jīng)紀人人的朋友友。朋友友收信后后照此辦辦理。最最終大部部分信在在經(jīng)過五五、六個個步驟后后都抵達達了該股股票經(jīng)紀紀人。Sixdegreesofseparation成功傳傳遞信件件的前提提是已已知朋友友中成功功傳遞信信件的程程度類似于該該實驗過過程，提提出了局局域搜索索免疫(localsearchimmunizationstrategy)局域搜索索免疫在模型中中實驗圖2實驗驗采用SIS病病毒傳播播模型，，在ER隨機網(wǎng)網(wǎng)絡(luò)(a:N為104,<k>=4)，BA無標度度網(wǎng)絡(luò)模模型(b：N=104,m0=8,m=4；；c：N=104,m0=8,m=6)中進行行仿真。。F為感染染節(jié)點的的密度，，q為免免疫節(jié)點點的比例例。在現(xiàn)實網(wǎng)網(wǎng)絡(luò)中實實驗圖3實驗驗采用SIS病病毒傳播播模型在在(autonomoussystem)AS層面的的Internet網(wǎng)網(wǎng)絡(luò)和和HighEnergyPhysics-Theory(HEP-Th)網(wǎng)網(wǎng)絡(luò)中測測試局域域搜索免免疫的性性能。F為感染節(jié)點點的密度，q為免疫節(jié)點點的比例該免疫與聚類類系數(shù)之間的的關(guān)系由于局域搜索索免疫是通過過搜索鄰居節(jié)節(jié)點中度數(shù)最最大的節(jié)點進進行免疫，直直觀來講該免免疫的性能與與網(wǎng)絡(luò)的聚類類系數(shù)有著某某些聯(lián)系A(chǔ)ssortativewiring算法法[5]能在在保持節(jié)點度度分布不變的的前提下，增增加網(wǎng)絡(luò)的聚聚類系數(shù)。任任意選擇兩條條邊，對兩條條邊對應的四四個頂點重新新連接：用一一條邊連接兩兩個度數(shù)比較較大的節(jié)點，，另一條邊連連接兩個度數(shù)數(shù)比較小的節(jié)節(jié)點。圖4在BA無標度網(wǎng)絡(luò)絡(luò)中，聚類系系數(shù)與局域搜搜索免疫性能能之間的關(guān)系系。F為算法的免免疫臨界值，，c為網(wǎng)絡(luò)的的聚類系數(shù)對BA無標度度網(wǎng)絡(luò)（N=104,m0=8,m=4）使使用assortativewiring算算法對網(wǎng)絡(luò)絡(luò)增加聚類系系數(shù)對于局域搜索索免疫的改進進局域免疫算法法是隨機選擇擇一個節(jié)點，，然后按照一一定要求搜索索。如果一個個網(wǎng)絡(luò)是由幾幾個小的不連連通的網(wǎng)絡(luò)組組成，那么這這種策略就有有可能一直在在一個小的網(wǎng)網(wǎng)絡(luò)中進行循循環(huán)搜索。解決方案：n種局域搜索索免疫同時進進行改進的局域搜搜索免疫問題:n=?刪除邊的免疫疫無論是熟人免免疫還是目標標免疫，基本本思想都是找找到度數(shù)大的的節(jié)點進行免免疫，也就相相當于對度數(shù)數(shù)大節(jié)點的所所有的邊進行行刪除，但是是并不是所有有的邊都有必必要刪除的。。比如節(jié)點i的度數(shù)很大大，而節(jié)點j的度數(shù)很小小，因為度數(shù)數(shù)小的節(jié)點在在疾病傳播過過程中起的作作用很小，所所以邊E(i,j)也就就沒有必要刪刪除。如果是是通過物理的的方式對網(wǎng)絡(luò)絡(luò)進行免疫，，那么對節(jié)點點進行免疫，，就極大的破破壞了網(wǎng)絡(luò)的的連通度。連通度指的是是兩個隨機選選擇的個體之之間存在路徑徑相連接的概概率，其決定定了網(wǎng)絡(luò)的活活躍性，可以以通過寬度優(yōu)優(yōu)先搜索算法法[6]來計計算。寬度優(yōu)優(yōu)先搜索算法法是一種圖形形搜索策略，，從一個源節(jié)節(jié)點開始搜索索其鄰居節(jié)點點，然后搜索索與鄰居節(jié)點點最近的節(jié)點點，直到滿足足條件為止。。為了了有有效效地地降降低低感感染染節(jié)節(jié)點點的的密密度度，，并并且且提提高高網(wǎng)網(wǎng)絡(luò)絡(luò)的的連連通通度度，，我我們們提提出出了了刪刪除除邊邊的的免免疫疫策策略略(EdgesCutImmunizationStrategy,EC免免疫疫策策略略)。。首先先是是按按照照節(jié)節(jié)點點的的度度數(shù)數(shù)進進行行排排序序，，從從高高到到低低選選擇擇一一定定數(shù)數(shù)目目的的節(jié)節(jié)點點，，刪刪除除節(jié)節(jié)點點與與節(jié)節(jié)點點直直接接相相連連的的邊邊。。為為了了降降低低病病毒毒在在度度數(shù)數(shù)大大節(jié)節(jié)點點之之間間的的傳傳播播，，也也要要刪刪除除邊邊E(i,j)，，如如果果其其余余節(jié)節(jié)點點i具具有有多多于于一一條條邊邊連連接接到到給給定定數(shù)數(shù)目目節(jié)節(jié)點點j。。刪除除邊邊的的免免疫疫在模模型型中中測測試試免免疫疫策策略略性性能能圖5實實驗驗采采用用SIS病病毒毒傳傳播播模模型型，，在在ER隨隨機機網(wǎng)網(wǎng)絡(luò)絡(luò)(圖圖a:N為為104,<k>=4)，，BA無無標標度度網(wǎng)網(wǎng)絡(luò)絡(luò)(圖圖b：：N=104,m0=8,m=4；；圖圖c：：N=104,m0=8,m=6)中中進進行行仿仿真真。。F為為感感染染節(jié)節(jié)點點的的密密度度，，q為為免免疫疫邊邊的的比比例例。。在模模型型中中測測試試連連通通度度圖6研研究究目目標標免免疫疫和和EC免免疫疫策策略略對對網(wǎng)網(wǎng)絡(luò)絡(luò)模模型型連連通通度度C的的影影響響。。其其中中q為為免免疫疫邊邊的的比比例例在現(xiàn)現(xiàn)實實網(wǎng)網(wǎng)絡(luò)絡(luò)中中測測試試免免疫疫的的性性能能圖7基基于于SIS病病毒毒傳傳播播模模型型，，分分別別采采用用目目標標免免疫疫和和EC策策略略對對于于(a)AS網(wǎng)網(wǎng)絡(luò)絡(luò),(b)HEP-Th網(wǎng)網(wǎng)絡(luò)絡(luò)和和(c)PGP網(wǎng)網(wǎng)絡(luò)絡(luò)，，進進行行免免疫疫，，根根據(jù)據(jù)刪刪除除邊邊的的比比例例q的的變變化化研研究究感感染染節(jié)節(jié)點點概概率率F的的變變化化。。在現(xiàn)實網(wǎng)絡(luò)絡(luò)中測試連連通度圖8研究目目標免疫和和EC免疫疫策略對現(xiàn)現(xiàn)實網(wǎng)絡(luò)連連通度C的的影響。其其中q為免免疫邊的比比例對于EC免免疫策略的的思考EC免疫是是從全局角角度來對邊邊進行免疫疫，也同樣樣可以從局局部信息的的角度來處處理。關(guān)于邊的免免疫，一直直感覺不是是很切實際際，畢竟在在現(xiàn)實生活活中，都是是對整個節(jié)節(jié)點進行免免疫，比如如某人患有有H1N1，就把他他完全隔離離，并沒有有要求這個個人只能見見某些人或或不能見某某些人，所所以對于EC免疫策策略的實用用性方面一一直存在疑疑惑。多重圖形剖剖分免疫以往的免疫疫策略的免免疫原則為為：根據(jù)度度數(shù)或者介介數(shù)，對重重要的節(jié)點點進行免疫疫。YipingChen通通過對目標標免疫分析析發(fā)現(xiàn)：目目標免疫策策略把網(wǎng)絡(luò)絡(luò)分成好幾幾種小的網(wǎng)網(wǎng)絡(luò)。小的的網(wǎng)絡(luò)在病病毒傳播過過程中起的的作用很小小，所以把把網(wǎng)絡(luò)分成成好幾個小小的網(wǎng)絡(luò)實實際上浪費費了代價。。Yiping通通過嵌入分分割算法（（nesteddissectionalgorithm））[8]把把網(wǎng)絡(luò)分成成幾個近似似大小的網(wǎng)網(wǎng)絡(luò)，然后后對分割集集團進行免免疫，提出出了EGP策（equalgraphpartitioningimmunizationstrategy）。EGP免疫疫策略可以以比目標免免疫少用5%-50%的免疫疫劑量，達達到相同的的感染密度度。原則是免免疫一組節(jié)節(jié)點(separatorgroup)，節(jié)節(jié)點把網(wǎng)絡(luò)絡(luò)分成幾個個相似大小小的集團。。圖9來自文獻7類似于EGP算法的的策略，可可以同樣采采用嵌入式式分割算法法，用邊對對網(wǎng)絡(luò)進行行劃分，提提出了多重重圖形剖分分算法。圖10Nesteddissection的執(zhí)行過過程（取自文文獻8）在linux環(huán)境下通過過metis軟件中的kmetis和pmetis程序來來對網(wǎng)絡(luò)劃分分，結(jié)果是把把每個頂點對對應的集團編編號存放在文文本中，然后后對于不同集集團之間的邊邊進行免疫。。實驗如圖11：圖11對于有向網(wǎng)絡(luò)絡(luò)免疫的思考考M.E.J.Newman的的Emailnetworksandthespreadofcomputerviruses[9]文章章，對email有向網(wǎng)網(wǎng)絡(luò)進行分析析免疫，首先先是把Email網(wǎng)絡(luò)進進行分析圖12Email的分分析來自文獻9然后根據(jù)出度度對于Email網(wǎng)絡(luò)進進行目標免疫疫圖13對Email網(wǎng)網(wǎng)絡(luò)進行免疫疫來自文獻9針對有向網(wǎng)絡(luò)絡(luò)的免疫，我我思考的是使使用類似于pagerank算法法來求解。Pagerank的思想想是對網(wǎng)頁進進行打分，原原理：網(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)(1-D)所以針對有向向無權(quán)網(wǎng)絡(luò)使使用SIS病病毒傳播模型型：如果n與i有有邊連接,E(n,i)=1，否否則為0。value(i)為節(jié)點點i感染疾病病的可能性問題：大型稀稀疏矩陣的求求解參考文獻[1]ReuvenCohen,ShlomoHavlin,Danielben.Avraham,PhysRevLett91(2003)277901[2]Pastor-SatorrasR,VespignaniA,Phys.Rev.E.65(2002)036104[3]Madar,N.;Kalisky,T.;Cohen,R.;Ben-Avraham,D，etc.Eur.Phys.J.B,38(2004):269-276[4]StanleyMilgram,"TheSmallWorldProblem",PsychologyToday,1967,Vol.2,60-67[5]ShiZhou,RaulJ.Mondragon,NewJournalofPhysics9(2007)173[6]AndyYoo,EdmondChow,etc,Proceedingsofthe2005ACM/IEEEconferenceonSupercomputing,2005.[7]ChenY,PaulG,etc,PhysRevLett.101(2008)058701.[8]BruceHendrickson,RobertLeland，Amultilevelalgorithmforpartitioninggraphs，Supercomputing，Tech.reportSAND93-1301,SandiaNationalLaboratories,Albuquerque,NM,1993[9]M.E.J.Newman,S.Forrest,andJ.Balthrop,Phys.Rev.E66,035101(2002).結(jié)語語從八八月月份份到到現(xiàn)現(xiàn)在在只只是是有有想想法法，，編編程程驗驗證證。。免免疫疫算算法法對對我我來來說說只只是是一一個個黑黑匣匣子子，，下下一一步步應應該該進進行行””白白盒盒測測試試””請老老師師，，師師兄兄，，師師姐姐批批評評指指正正謝謝謝大大家家9、靜夜四四無鄰，，荒居舊舊業(yè)貧。。。12月-2212月-22Friday,December23,202210、雨中黃葉葉樹，燈下下白頭人。。。07:59:0707:59:0707:5912/23/20227:59:07AM11、以我獨沈久久，愧君相見見頻。。12月-2207:59:0707:59Dec-2223-Dec-2212、故人江海別別，幾度隔山山川。。07:59:0707:59:0707:59Friday,December23,202213、乍見見翻疑疑夢，，相悲悲各問問年。。。12月月-2212月月-2207:59:0707:59:07December23,202214、他鄉(xiāng)生白白發(fā)，舊國國見青山。。。23十二二月20227:59:07上上午07:59:0712月-2215、比不不了得得就不不比，，得不不到的的就不不要。。。。。十二月月227:59上上午午12月月-2207:59December23,202216、行行動動出出成成果果，，工工作作出出財財富富。。。。2022/12/237:59:0707:59:0723December202217、做做前前，，能能夠夠環(huán)環(huán)視視四四周周；；做做時時，，你你只只能能或或者者最最好好沿沿著著以以腳腳為為起起點點的的射射線線向向前前。。。。7:59:07上上午午7:59上上午午07:59:0712月月-229、沒有失失敗，只只有暫時時停止成成功！。。12月-2212月-22Friday,December23,202210、很多事事情努力力了未必必有結(jié)果果，但是是不努力力卻什么么改變也也沒有。。。07:59:0707:59:0707:5912/23/20227:59:07AM11、成功就是是日復一日日那一點點點小小努力力的積累。。。12月-2207:59:0707:59Dec-2223-Dec-2212、世間成事事，不求其其絕對圓滿滿，留一份份不足，可可得無限完完美。。07:59:0707:59:0707:59Friday,December23,202213、不知知香積積寺，，數(shù)里里入云云峰。。。12月月-2212月月-2207:59:0807:59:08December23,202214、意志志堅強強的人人能把把世界界放在在手中中像泥泥塊一一樣任任意揉揉捏。。23十十二二月20227:59:08上上午07:59:0812月月-2215、楚楚塞塞三三湘湘接接，，荊荊門門九九派派通通。。。。。。十二二月月227:59上上午午12月月-2207:59December23,202216、少少年年十十五五二二十十時時，，步步行行奪奪得得胡胡馬馬騎騎。。。。2022/12/237:59:0807:59:0823December202217