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

《復(fù)雜網(wǎng)絡(luò)的免疫策略》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、復(fù)雜網(wǎng)絡(luò)的免疫策略紀(jì)鵬導(dǎo)師葛洪偉江南大學(xué)信息工程學(xué)院大綱基本的復(fù)雜網(wǎng)絡(luò)免疫策略改變假設(shè)條件：局域搜索免疫改變免疫對象：刪除邊的免疫改變免疫原則：多重圖形剖分免疫對于有向網(wǎng)絡(luò)免疫的思考基本的免疫策略目標(biāo)：通過對部分人接種而有效地控制疾病的傳播基于局域信息免疫uniformimmunization(均勻免疫)acquaintanceimmunization（熟人免疫）基于全局信息targetedimmunization（目標(biāo)免疫）均勻免疫均勻免疫，顧名思義完全隨機(jī)的從網(wǎng)絡(luò)中選擇一部分節(jié)點(diǎn)進(jìn)行免疫。它對于度數(shù)大的節(jié)點(diǎn)和度數(shù)小

2、的節(jié)點(diǎn)平等對待在無標(biāo)度網(wǎng)絡(luò)中對應(yīng)的免疫臨界值均勻免疫熟人免疫隨機(jī)選擇比例為p的節(jié)點(diǎn)，然后再從這些選擇的節(jié)點(diǎn)中隨機(jī)選擇一個鄰居節(jié)點(diǎn)進(jìn)行免疫由于度數(shù)大的節(jié)點(diǎn)也就意味著有更多的節(jié)點(diǎn)與之相連，所以熟人免疫比均勻免疫的效率要好得多熟人免疫目標(biāo)免疫根據(jù)無標(biāo)度網(wǎng)絡(luò)的不均勻特性，可以進(jìn)行有選擇的目標(biāo)免疫，即選取度數(shù)大的節(jié)點(diǎn)進(jìn)行免疫在BA無標(biāo)度網(wǎng)絡(luò)中，目標(biāo)免疫對應(yīng)的免疫臨界值為目標(biāo)免疫不同免疫策略的比較在網(wǎng)絡(luò)規(guī)模為106，冪率指數(shù)在2-3.5之間變化的無標(biāo)度網(wǎng)絡(luò)中不同策略對應(yīng)的免疫臨界值均勻免疫(空心圓)熟人免疫（空心三角形）目標(biāo)免疫（

3、空心正方形）圖1（參考文獻(xiàn)[3]）局域搜索免疫熟人免疫假設(shè)條件為已知當(dāng)前節(jié)點(diǎn)的度目標(biāo)免疫假設(shè)條件為已知所有節(jié)點(diǎn)的度假設(shè)已知鄰居節(jié)點(diǎn)的度信息，怎樣進(jìn)行免疫呢？1967年，哈佛大學(xué)的社會心理學(xué)家StanleyMilgram就設(shè)計(jì)了一個連鎖信件實(shí)驗(yàn)[4]。他將一套連鎖信件隨機(jī)發(fā)送給居住在內(nèi)布拉斯加州奧馬哈的160個人，信中放了一個波士頓股票經(jīng)紀(jì)人的名字，信中要求每個收信人將這套信寄給自己認(rèn)為是比較接近那個股票經(jīng)紀(jì)人的朋友。朋友收信后照此辦理。最終大部分信在經(jīng)過五、六個步驟后都抵達(dá)了該股票經(jīng)紀(jì)人。Sixdegreesofsep

4、aration成功傳遞信件的前提是已知朋友中成功傳遞信件的程度類似于該實(shí)驗(yàn)過程，提出了局域搜索免疫(localsearchimmunizationstrategy)局域搜索免疫在模型中實(shí)驗(yàn)圖2實(shí)驗(yàn)采用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é)點(diǎn)的密度，q為免疫節(jié)點(diǎn)的比例。在現(xiàn)實(shí)網(wǎng)絡(luò)中實(shí)驗(yàn)圖3實(shí)驗(yàn)采用SIS病毒傳播模型在(autonomoussystem)AS層面的Internet網(wǎng)絡(luò)和H

5、ighEnergyPhysics-Theory(HEP-Th)網(wǎng)絡(luò)中測試局域搜索免疫的性能。F為感染節(jié)點(diǎn)的密度，q為免疫節(jié)點(diǎn)的比例該免疫與聚類系數(shù)之間的關(guān)系由于局域搜索免疫是通過搜索鄰居節(jié)點(diǎn)中度數(shù)最大的節(jié)點(diǎn)進(jìn)行免疫，直觀來講該免疫的性能與網(wǎng)絡(luò)的聚類系數(shù)有著某些聯(lián)系A(chǔ)ssortativewiring算法[5]能在保持節(jié)點(diǎn)度分布不變的前提下，增加網(wǎng)絡(luò)的聚類系數(shù)。任意選擇兩條邊，對兩條邊對應(yīng)的四個頂點(diǎn)重新連接：用一條邊連接兩個度數(shù)比較大的節(jié)點(diǎn)，另一條邊連接兩個度數(shù)比較小的節(jié)點(diǎn)。圖4在BA無標(biāo)度網(wǎng)絡(luò)中，聚類系數(shù)與局域搜索免疫性

6、能之間的關(guān)系。F為算法的免疫臨界值，c為網(wǎng)絡(luò)的聚類系數(shù)對BA無標(biāo)度網(wǎng)絡(luò)（N=104,m0=8,m=4）使用assortativewiring算法對網(wǎng)絡(luò)增加聚類系數(shù)對于局域搜索免疫的改進(jìn)局域免疫算法是隨機(jī)選擇一個節(jié)點(diǎn)，然后按照一定要求搜索。如果一個網(wǎng)絡(luò)是由幾個小的不連通的網(wǎng)絡(luò)組成，那么這種策略就有可能一直在一個小的網(wǎng)絡(luò)中進(jìn)行循環(huán)搜索。解決方案：n種局域搜索免疫同時進(jìn)行改進(jìn)的局域搜索免疫問題:n=?刪除邊的免疫無論是熟人免疫還是目標(biāo)免疫，基本思想都是找到度數(shù)大的節(jié)點(diǎn)進(jìn)行免疫，也就相當(dāng)于對度數(shù)大節(jié)點(diǎn)的所有的邊進(jìn)行刪除，但是并

7、不是所有的邊都有必要刪除的。比如節(jié)點(diǎn)i的度數(shù)很大，而節(jié)點(diǎn)j的度數(shù)很小，因?yàn)槎葦?shù)小的節(jié)點(diǎn)在疾病傳播過程中起的作用很小，所以邊E(i,j)也就沒有必要刪除。如果是通過物理的方式對網(wǎng)絡(luò)進(jìn)行免疫，那么對節(jié)點(diǎn)進(jìn)行免疫，就極大的破壞了網(wǎng)絡(luò)的連通度。連通度指的是兩個隨機(jī)選擇的個體之間存在路徑相連接的概率，其決定了網(wǎng)絡(luò)的活躍性，可以通過寬度優(yōu)先搜索算法[6]來計(jì)算。寬度優(yōu)先搜索算法是一種圖形搜索策略，從一個源節(jié)點(diǎn)開始搜索其鄰居節(jié)點(diǎn)，然后搜索與鄰居節(jié)點(diǎn)最近的節(jié)點(diǎn)，直到滿足條件為止。為了有效地降低感染節(jié)點(diǎn)的密度，并且提高網(wǎng)絡(luò)的連通度，我們

8、提出了刪除邊的免疫策略(EdgesCutImmunizationStrategy,EC免疫策略)。首先是按照節(jié)點(diǎn)的度數(shù)進(jìn)行排序，從高到低選擇一定數(shù)目的節(jié)點(diǎn)，刪除節(jié)點(diǎn)與節(jié)點(diǎn)直接相連的邊。為了降低病毒在度數(shù)大節(jié)點(diǎn)之間的傳播，也要刪除邊E(i,j)，如果其余節(jié)點(diǎn)i具有多于一條邊連接到給定數(shù)目節(jié)點(diǎn)j。刪除邊的免疫在模型中測試免疫策略性能圖