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

李向華,王 欣,高 超

(1. 西南大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院,重慶 400715;2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130012)

網(wǎng)絡(luò)免疫技術(shù)通過(guò)保護(hù)網(wǎng)絡(luò)中部分節(jié)點(diǎn)以切斷病毒傳播路徑的方式保護(hù)網(wǎng)絡(luò),是復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)的主要研究?jī)?nèi)容,也是抑制病毒傳播的有效方法之一[1-5]. 高效的免疫策略不僅對(duì)計(jì)算機(jī)網(wǎng)絡(luò)適用,對(duì)人類社會(huì)接觸關(guān)系網(wǎng)絡(luò)中的傳染病傳播和控制也有重要意義[6-7]. 然而,目前對(duì)復(fù)雜網(wǎng)絡(luò)免疫策略的分析都是基于單一網(wǎng)絡(luò)結(jié)構(gòu),即假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)服從單一度分布[8],而異構(gòu)耦合網(wǎng)絡(luò)在現(xiàn)實(shí)世界中廣泛存在,如電網(wǎng)、 交通和通信等系統(tǒng)通常耦合在一起、 互相關(guān)聯(lián),一個(gè)系統(tǒng)的波動(dòng)即會(huì)影響另一個(gè)系統(tǒng)的穩(wěn)定[9]. 如瘧疾[10]和H5N1[11-12]為代表的病毒可同時(shí)在動(dòng)物網(wǎng)絡(luò)(蚊子、 鳥類)和人類接觸網(wǎng)絡(luò)中傳播;同一所學(xué)校內(nèi)不同班級(jí)同學(xué)之間也擁有顯著不同的接觸模式[13]. 因此,研究這類耦合網(wǎng)絡(luò)的抗毀性具有重要意義[9,14-15].

判斷一種網(wǎng)絡(luò)免疫策略是否可在網(wǎng)絡(luò)中有效執(zhí)行,通常從兩方面評(píng)價(jià): 1) 策略對(duì)網(wǎng)絡(luò)的保護(hù)能力,即評(píng)估其對(duì)病毒傳播的抑制能力;2) 策略的可執(zhí)行能力,即策略部署需要的前提條件. 優(yōu)秀的網(wǎng)絡(luò)免疫策略應(yīng)首先能有效地抑制病毒的傳播,保護(hù)網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)不被病毒感染;同時(shí)必須能克服網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)動(dòng)態(tài)性的影響,易于在網(wǎng)絡(luò)中部署.

1 復(fù)雜網(wǎng)絡(luò)免疫策略分類及分析

復(fù)雜網(wǎng)絡(luò)可用圖G=〈V,E〉表示,其中:V表示節(jié)點(diǎn)集合;E表示邊集合. 網(wǎng)絡(luò)免疫策略的主要目的是從節(jié)點(diǎn)集V中選出一些重要節(jié)點(diǎn)注入“疫苗”,阻止該節(jié)點(diǎn)被病毒感染,進(jìn)而阻斷病毒進(jìn)一步傳播的路徑. 這些被選中的免疫節(jié)點(diǎn)用Vp表示,被感染的節(jié)點(diǎn)用Vi表示. 為了兼顧免疫成本和效率,優(yōu)秀的免疫策略應(yīng)使用少量的Vp即可使Vi數(shù)目降到最小. 本文先從計(jì)算角度出發(fā),圍繞免疫節(jié)點(diǎn)發(fā)現(xiàn)過(guò)程,對(duì)比分析現(xiàn)有策略的原理、 特點(diǎn)及問(wèn)題.

按獲取信息程度的不同,目前的網(wǎng)絡(luò)免疫策略可分為全局免疫策略和局部免疫策略;而按選取依據(jù)不同,又可分為基于節(jié)點(diǎn)度數(shù)、 基于網(wǎng)絡(luò)介數(shù)和基于節(jié)點(diǎn)核數(shù)的免疫策略.

1.1 基于網(wǎng)絡(luò)全局信息的免疫策略

節(jié)點(diǎn)度數(shù)反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度,目標(biāo)免疫策略[1-2]作為全局性策略,根據(jù)網(wǎng)絡(luò)拓?fù)湫畔⒅苯舆x擇網(wǎng)絡(luò)中度數(shù)最大的一組節(jié)點(diǎn)作為免疫節(jié)點(diǎn),取得了非常好的免疫效果. 而介數(shù)反映了節(jié)點(diǎn)(邊)在特定網(wǎng)絡(luò)結(jié)構(gòu)中承載的流量,進(jìn)而反映其通信中轉(zhuǎn)能力[16]. 通常介數(shù)大的節(jié)點(diǎn)(邊)是兩個(gè)社團(tuán)的橋梁,如果將節(jié)點(diǎn)(邊兩端的節(jié)點(diǎn))去除,則可將網(wǎng)絡(luò)分割成多個(gè)子網(wǎng)絡(luò),進(jìn)而阻止病毒擴(kuò)散[17]. 因此,基于介數(shù)的免疫策略[17]選取網(wǎng)絡(luò)中中轉(zhuǎn)能力強(qiáng)的中繼節(jié)點(diǎn)抑制病毒傳播. 圖1為不同免疫策略選擇免疫節(jié)點(diǎn)的示意圖. 由圖1可見,基于節(jié)點(diǎn)介數(shù)的免疫策略會(huì)選擇網(wǎng)絡(luò)中節(jié)點(diǎn)介數(shù)最大的V9進(jìn)行免疫；邊介數(shù)免疫策略則從邊介數(shù)最大的邊L1和L2兩端節(jié)點(diǎn)(V5,V7或V9)中隨機(jī)選擇一個(gè)免疫. 通過(guò)免疫介數(shù)大的節(jié)點(diǎn),可將圖1網(wǎng)絡(luò)劃分為兩個(gè)子網(wǎng)絡(luò),如果免疫V5或V9,則該策略還能進(jìn)一步打破上(或下)側(cè)子網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu),不僅阻止病毒在不同子網(wǎng)絡(luò)間的傳播,而且阻止了病毒在子網(wǎng)絡(luò)內(nèi)的傳播. 文獻(xiàn)[17]通過(guò)實(shí)驗(yàn)證明：節(jié)點(diǎn)介數(shù)免疫策略的效率優(yōu)于目標(biāo)免疫. 因此,免疫策略不但要保護(hù)網(wǎng)絡(luò)中的重要節(jié)點(diǎn)(即度大節(jié)點(diǎn)),而且中繼節(jié)點(diǎn)也要進(jìn)行免疫才能更好地控制病毒的傳播.

圖1 不同免疫策略選擇免疫節(jié)點(diǎn)的示意圖Fig.1 Illustration for immunized nodes selected by different immunization strategies

還有些全局免疫策略通過(guò)節(jié)點(diǎn)的核數(shù)(k-shell或k-core)值[18]選擇免疫節(jié)點(diǎn). 當(dāng)網(wǎng)絡(luò)中只有單一病毒傳播源時(shí),基于核數(shù)免疫策略的效率優(yōu)于目標(biāo)免疫策略；但當(dāng)存在多個(gè)病毒傳播源時(shí),則遜于目標(biāo)免疫策略[19]. 這是因?yàn)榛诤藬?shù)免疫策略選擇的節(jié)點(diǎn)大多數(shù)是網(wǎng)絡(luò)的核心,聚集在網(wǎng)絡(luò)的中心位置,而目標(biāo)免疫選擇的節(jié)點(diǎn)可分散在網(wǎng)絡(luò)中的任意位置. 由于本文仿真實(shí)驗(yàn)采用多源攻擊,因此實(shí)驗(yàn)部分并未對(duì)比基于核數(shù)策略與其他策略的性能差別.

綜上所述,雖然全局免疫策略可取得很好的免疫效果,但現(xiàn)實(shí)網(wǎng)絡(luò)大多數(shù)是分布式和離散式的,獲取整個(gè)網(wǎng)絡(luò)拓?fù)湫畔缀鯚o(wú)法實(shí)現(xiàn). 同時(shí),對(duì)于一些缺乏集中管理的大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò),很難獲取整個(gè)網(wǎng)絡(luò)信息,為了在效率和可行性之間取得平衡,人們提出了基于局部信息的免疫策略.

1.2 基于網(wǎng)絡(luò)局部信息的免疫策略

局部免疫策略克服了全局策略需要預(yù)先掌握網(wǎng)絡(luò)拓?fù)涞钠款i,其中隨機(jī)免疫策略[1,3]忽略網(wǎng)絡(luò)節(jié)點(diǎn)屬性差異,以等概率方式選取一定比例的節(jié)點(diǎn)進(jìn)行保護(hù). 雖然該策略對(duì)均勻網(wǎng)絡(luò)的保護(hù)能力較優(yōu),但在無(wú)標(biāo)度網(wǎng)絡(luò)中,該策略幾乎需要免疫所有節(jié)點(diǎn)才可能阻止病毒傳播[1],這在現(xiàn)實(shí)世界很難實(shí)現(xiàn).

為提高局部免疫效率,利用現(xiàn)實(shí)網(wǎng)絡(luò)中廣泛存在的無(wú)標(biāo)度結(jié)構(gòu)特征,研究者們提出了鄰居免疫[4,20-22]和圖覆蓋免疫[5,23-25]策略. 鄰居免疫策略先從網(wǎng)絡(luò)中隨機(jī)選取“種子”節(jié)點(diǎn),再?gòu)倪@些節(jié)點(diǎn)周圍隨機(jī)選擇一個(gè)或多個(gè)直接鄰居進(jìn)行免疫. 因?yàn)樵跓o(wú)標(biāo)度網(wǎng)絡(luò)中,度大的節(jié)點(diǎn)擁有更多鄰居,其被選中的概率遠(yuǎn)高于度小的節(jié)點(diǎn),進(jìn)而能以較低的計(jì)算成本取得遠(yuǎn)好于隨機(jī)免疫的效果,同時(shí)回避了目標(biāo)免疫需要掌握全局信息的瓶頸. 但這種對(duì)所有鄰居不加甄別、 隨機(jī)選取的方式及僅選取直接鄰居的方法,使其效率受到嚴(yán)重制約[23].

基于圖覆蓋的免疫策略將免疫過(guò)程視為一個(gè)圖覆蓋問(wèn)題,即以“種子”節(jié)點(diǎn)為中心,免疫其周圍d步范圍內(nèi)的最大度節(jié)點(diǎn). 該方法利用一定局部拓?fù)渲R(shí),取得明顯優(yōu)于鄰居免疫的效果. 但由于該策略選擇節(jié)點(diǎn)行為固定,受網(wǎng)絡(luò)拓?fù)?特別是社團(tuán)結(jié)構(gòu)的影響較大,常陷入局部最優(yōu)解[26]. 雖然該方法適合于分布式網(wǎng)絡(luò),但其計(jì)算復(fù)雜性隨覆蓋距離的增加而指數(shù)級(jí)增大,且在實(shí)際應(yīng)用中,用戶很難獲得間接鄰居信息. 同時(shí),該策略并未考慮任何與應(yīng)用領(lǐng)域相關(guān)的啟發(fā)信息,也未回答針對(duì)不同網(wǎng)絡(luò),d值如何選取,因此具有一定的局限性.

為了能僅利用局部信息獲得與目標(biāo)免疫策略近似、 甚至更優(yōu)的免疫效果,文獻(xiàn)[27]從計(jì)算角度將網(wǎng)絡(luò)免疫問(wèn)題轉(zhuǎn)化成分布式約束優(yōu)化問(wèn)題[28],將自組織和正反饋機(jī)制融入到分布式約束搜索算法中,提出一種基于AOC的分布式免疫策略. 該策略通過(guò)在網(wǎng)絡(luò)中布置一群具有自治行為的計(jì)算體(entity)實(shí)現(xiàn)對(duì)一組最大度節(jié)點(diǎn)的搜索. 與已有方法相比,該方法從群體智能中的激發(fā)工作機(jī)制入手,通過(guò)自組織計(jì)算提高搜索效率,但該策略與全局免疫策略的免疫效率有一定差距.

以圖1為例,如果只選擇一個(gè)免疫節(jié)點(diǎn),隨機(jī)免疫策略可能選擇V1作為免疫節(jié)點(diǎn). 如果V1被選為種子節(jié)點(diǎn),則隨機(jī)鄰居免疫策略會(huì)從直接鄰居V4和V5中隨機(jī)選取一個(gè)作為免疫節(jié)點(diǎn). 而當(dāng)覆蓋范圍d=3時(shí),圖覆蓋免疫策略會(huì)將到V1距離小于等于3的{V1,V2,V3,V4,V5,V7,V9}集合中選取一個(gè)最大度節(jié)點(diǎn)作為免疫節(jié)點(diǎn),即V5或V9;而基于AOC免疫策略中的entity根據(jù)它們之間的自組織交互及局部正反饋機(jī)制最優(yōu)移動(dòng)規(guī)則,最終選取V12為免疫節(jié)點(diǎn).

2 同構(gòu)網(wǎng)絡(luò)中免疫策略對(duì)比及分析

本文以兩個(gè)真實(shí)郵件網(wǎng)絡(luò)(美國(guó)安然公司和西班牙ROVIRA I VIRGILI大學(xué)郵件網(wǎng)絡(luò))及GLP算法[29]構(gòu)建的人工網(wǎng)絡(luò)作為實(shí)驗(yàn)用的同構(gòu)網(wǎng)絡(luò),從免疫效率、 代價(jià)和魯棒性三方面定量分析不同類型免疫策略對(duì)病毒的抑制能力,所用網(wǎng)絡(luò)列于表1. 對(duì)比免疫相同數(shù)目節(jié)點(diǎn)時(shí),用網(wǎng)絡(luò)中最終被感染節(jié)點(diǎn)的數(shù)目判斷哪種策略免疫效率最好;免疫代價(jià)不僅比較了各策略的時(shí)間復(fù)雜度,還分析了免疫臨界值,即選擇哪種策略可在免疫最少節(jié)點(diǎn)的情況下,將病毒傳播率控制在最小范圍內(nèi);魯棒性則分析對(duì)比各策略對(duì)網(wǎng)絡(luò)拓?fù)渥兓倪m應(yīng)能力.

表1 實(shí)驗(yàn)所用同構(gòu)網(wǎng)絡(luò)Table 1 Homogeneous networks used in experiments

2.1 免疫效率

在交互式郵件傳播模型[30]中,對(duì)比分析目前最具代表的網(wǎng)絡(luò)免疫策略對(duì)病毒傳播的抑制能力. 病毒傳播模型參數(shù)設(shè)置與文獻(xiàn)[30]相同,傳播過(guò)程模擬運(yùn)行600個(gè)時(shí)間步,初始病毒攻擊采用隨機(jī)攻擊方式感染網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn). 所有數(shù)值結(jié)果均為運(yùn)行100次的平均值. 從網(wǎng)絡(luò)中分別選取5%,10%和30%的節(jié)點(diǎn)進(jìn)行免疫,觀察不同策略對(duì)病毒傳播的抑制能力,即網(wǎng)絡(luò)的最終被感染節(jié)點(diǎn)數(shù)目情況.

表2列出了各類策略在合成網(wǎng)絡(luò)中的免疫效率,括號(hào)內(nèi)的數(shù)字表示不采用策略時(shí)網(wǎng)絡(luò)中被感染的節(jié)點(diǎn)總數(shù). 由表2可見,在選取相同數(shù)目免疫節(jié)點(diǎn)的前提下,掌握了全局拓?fù)湫畔⒌墓?jié)點(diǎn)介數(shù)免疫策略對(duì)病毒傳播的抑制能力最強(qiáng). 而在全局信息未知情況下,基于AOC策略的免疫效果最佳. 實(shí)驗(yàn)結(jié)果也表明控制病毒的傳播并非只保護(hù)網(wǎng)絡(luò)中度數(shù)大的節(jié)點(diǎn),那些傳輸能力強(qiáng)的中繼節(jié)點(diǎn)對(duì)病毒的傳播也起至關(guān)重要的作用. 而基于AOC的免疫策略利用自組織和正反饋機(jī)制在局域環(huán)境中搜索最大度節(jié)點(diǎn)的同時(shí),間接免疫了那些具有大度數(shù)的中繼節(jié)點(diǎn),因而取得了比其他基于節(jié)點(diǎn)度數(shù)免疫策略更好的免疫效率. 人工社團(tuán)網(wǎng)絡(luò)(該網(wǎng)絡(luò)具有4個(gè)社區(qū),由100條邊將獨(dú)立的社區(qū)連接在一起)的免疫結(jié)果與人工合成網(wǎng)絡(luò)相似.

表2 人工合成網(wǎng)絡(luò)中不同免疫策略的免疫效率對(duì)比結(jié)果Table 2 Immunization efficiencies of different strategies in synthetic networks

圖2 人工社團(tuán)網(wǎng)絡(luò)最終感染的節(jié)點(diǎn) 數(shù)目隨時(shí)間變化曲線Fig.2 Final number of infected nodes with time varying in the synthetic community-based network

圖2對(duì)表現(xiàn)較優(yōu)的4種免疫策略做了進(jìn)一步分析. 其中,節(jié)點(diǎn)介數(shù)免疫策略明顯優(yōu)于目標(biāo)免疫策略,這是因?yàn)榻閿?shù)免疫可有效破壞網(wǎng)絡(luò)拓?fù)?增加網(wǎng)絡(luò)平均路徑長(zhǎng)度,切斷病毒傳播路徑. 由于基于AOC免疫策略選擇的節(jié)點(diǎn)不僅節(jié)點(diǎn)度數(shù)大,而且介數(shù)值高,所以其免疫效率又優(yōu)于只保護(hù)了節(jié)點(diǎn)介數(shù)大的介數(shù)免疫策略.

表3進(jìn)一步分析了各策略在真實(shí)郵件網(wǎng)絡(luò)中的免疫效率. 圖3顯示了在安然網(wǎng)絡(luò)中被感染節(jié)點(diǎn)數(shù)目隨時(shí)間的變化過(guò)程(A)及被感染節(jié)點(diǎn)數(shù)目與免疫節(jié)點(diǎn)間的變化關(guān)系(B). 結(jié)果表明,在安然網(wǎng)絡(luò)中,基于AOC策略在免疫網(wǎng)絡(luò)中10%的節(jié)點(diǎn)后,達(dá)到免疫臨界點(diǎn),即病毒很難在網(wǎng)絡(luò)中大規(guī)模擴(kuò)散. 上述實(shí)驗(yàn)結(jié)果與人工網(wǎng)絡(luò)結(jié)論相同,即基于節(jié)點(diǎn)介數(shù)的免疫策略和基于AOC的免疫策略在免疫效率方面取得了比其他策略更好的效果. 由于基于AOC免疫策略只依靠局部信息即可在網(wǎng)絡(luò)中部署,故更適合在大規(guī)模分布式網(wǎng)絡(luò)中應(yīng)用.

文獻(xiàn)[17]驗(yàn)證了節(jié)點(diǎn)介數(shù)免疫策略的免疫效率優(yōu)于目標(biāo)免疫策略,這是因?yàn)榻閿?shù)免疫策略可有效破壞原有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),通過(guò)增加網(wǎng)絡(luò)平均路徑長(zhǎng)度的方式阻斷病毒傳播路徑. 而本文實(shí)驗(yàn)表明,基于AOC的分布式免疫策略的免疫效率在某些情況下甚至優(yōu)于節(jié)點(diǎn)介數(shù)免疫策略. 這是因?yàn)榛贏OC免疫策略選擇的免疫節(jié)點(diǎn)不僅具有較大的節(jié)點(diǎn)度數(shù),同時(shí)搜索自治體在網(wǎng)絡(luò)中按照網(wǎng)絡(luò)鏈路的鏈接關(guān)系進(jìn)行游走時(shí),會(huì)先保護(hù)網(wǎng)絡(luò)中中轉(zhuǎn)能力強(qiáng)的節(jié)點(diǎn),即介數(shù)大的節(jié)點(diǎn). 所以基于AOC免疫策略選出的免疫節(jié)點(diǎn)不僅具有較大的節(jié)點(diǎn)介數(shù)值,同時(shí)具有較大的節(jié)點(diǎn)度數(shù)值,因此可更有效地切斷病毒傳播路徑.

表3 真實(shí)網(wǎng)絡(luò)中不同免疫策略的免疫效率對(duì)比結(jié)果Table 3 Comparison of immunization efficiencies from different immunization strategies in benchmark networks

圖3 安然郵件網(wǎng)絡(luò)的病毒傳播示意圖Fig.3 Illustration for viruses propagation in Enron email network

2.2 免疫代價(jià)

表4 計(jì)算復(fù)雜性對(duì)比結(jié)果Table 4 Comparison of computational complex of immunization strategies

由表4可見,基于AOC免疫策略的計(jì)算復(fù)雜性最小,而全局的介數(shù)免疫策略和目標(biāo)免疫策略因?yàn)樾枰莆杖滞負(fù)浣Y(jié)構(gòu)才可以實(shí)施,因此計(jì)算復(fù)雜性最大. 在現(xiàn)實(shí)應(yīng)用中,免疫某個(gè)節(jié)點(diǎn)需要一定成本,為了既能抑制病毒傳播,又能降低成本,高效的免疫策略應(yīng)通過(guò)免疫盡量少的節(jié)點(diǎn)控制病毒的感染率. 因此衡量免疫代價(jià)的另一個(gè)指標(biāo)就是為了達(dá)到免疫臨界值所需免疫節(jié)點(diǎn)比例. 為便于闡述,定義以下變量: ρ0表示不應(yīng)用免疫策略時(shí)網(wǎng)絡(luò)的最終感染密度(ρ0=NI/N,其中NI表示被感染節(jié)點(diǎn)總數(shù));ρf表示應(yīng)用免疫策略后網(wǎng)絡(luò)節(jié)點(diǎn)最終感染密度;ρ表示病毒傳播感染率,ρ=ρf/ρ0. 根據(jù)文獻(xiàn)[25],定義fc作為免疫臨界值,表示為使病毒的傳播率ρ→0時(shí),需要免疫的網(wǎng)絡(luò)節(jié)點(diǎn)比例值f.

圖4對(duì)比了采用隨機(jī)攻擊時(shí),兩種人工合成網(wǎng)絡(luò)中ρ隨免疫節(jié)點(diǎn)比例f的變化過(guò)程. 實(shí)驗(yàn)表明,節(jié)點(diǎn)介數(shù)免疫策略能花費(fèi)最小的f值有效保護(hù)網(wǎng)絡(luò);而在分布式策略中,基于AOC的免疫策略免疫代價(jià)最小. 以圖4(A)為例,當(dāng)ρ=0.1時(shí),節(jié)點(diǎn)介數(shù)免疫策略需要的免疫臨界值f1小于基于AOC的免疫臨界值f2,而f2小于目標(biāo)免疫臨界值f3,即f1

圖4 不同冪率結(jié)構(gòu)人工網(wǎng)絡(luò)中的免疫代價(jià)對(duì)比Fig.4 Comparison of immunization costs in synthetic networks with different power-law exponents

圖5 免疫臨界值隨網(wǎng)絡(luò)結(jié)構(gòu)的變化關(guān)系Fig.5 Change of immunization critical value (fc) with the network structure

2.3 免疫魯棒性

面對(duì)網(wǎng)絡(luò)結(jié)構(gòu)差異,同一策略在不同網(wǎng)絡(luò)中會(huì)得到不同的效果,但最佳策略應(yīng)不受網(wǎng)絡(luò)拓?fù)溆绊?即策略應(yīng)具有魯棒性[25]. 圖5為免疫臨界值fc與網(wǎng)絡(luò)冪指數(shù)之間的變化關(guān)系. 由圖5可見,fc的變化幅度越小,當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)變化時(shí),為抑制病毒傳播所需免疫的節(jié)點(diǎn)比例變化越小,策略魯棒性越強(qiáng). 實(shí)驗(yàn)結(jié)果表明,節(jié)點(diǎn)介數(shù)策略的魯棒性最好,但該策略受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)限制,無(wú)法應(yīng)用于大規(guī)模分布式網(wǎng)絡(luò)中. 而在分布式策略中,基于AOC策略的魯棒性最好. 同時(shí),該策略的搜索性能所展現(xiàn)的魯棒性更適用于大規(guī)模、 分布式的動(dòng)態(tài)網(wǎng)絡(luò)[27].

3 異構(gòu)耦合網(wǎng)絡(luò)中免疫策略分析

上述病毒傳播模型是以同構(gòu)網(wǎng)絡(luò)為研究目標(biāo),即假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)度分布服從冪律分布. 而現(xiàn)實(shí)網(wǎng)絡(luò)并非擁有單一網(wǎng)絡(luò)結(jié)構(gòu),在一個(gè)網(wǎng)絡(luò)中同時(shí)包含多個(gè)子網(wǎng)絡(luò),每個(gè)子網(wǎng)絡(luò)擁有不同的度分布特征,呈現(xiàn)出異構(gòu)特點(diǎn)[31-33]. 本文構(gòu)造一個(gè)異構(gòu)耦合網(wǎng)絡(luò)(heterogeneous interdependent network),并在此網(wǎng)絡(luò)上分析免疫策略對(duì)病毒傳播的抑制能力.

異構(gòu)耦合網(wǎng)絡(luò)構(gòu)建過(guò)程如下:

1) 構(gòu)建4個(gè)具有獨(dú)立度的分布網(wǎng)絡(luò),分別用G1,G2,G3,G4表示,其中: G1和G2由GLP網(wǎng)絡(luò)產(chǎn)生器[29]產(chǎn)生無(wú)標(biāo)度網(wǎng)絡(luò),冪指數(shù)分別為1.7和2.7;G3是利用WS模型構(gòu)建的小世界網(wǎng)絡(luò);G4是利用ER模型構(gòu)建的隨機(jī)網(wǎng)絡(luò). 表5列出了4個(gè)獨(dú)立網(wǎng)絡(luò)的結(jié)構(gòu)屬性,圖6(A)的度分布清晰展現(xiàn)了4個(gè)獨(dú)立網(wǎng)絡(luò)的異質(zhì)特性.

2) 在獨(dú)立網(wǎng)絡(luò)間隨機(jī)添加100條邊,構(gòu)建異構(gòu)耦合網(wǎng)絡(luò),如圖6(B)所示. 如果網(wǎng)絡(luò)M和N之間邊數(shù)用EMN表示,則E12=17,E13=14,E14=14,E23=21,E24=19,E34=15.

表5 異構(gòu)網(wǎng)絡(luò)中的子網(wǎng)絡(luò)結(jié)構(gòu)Table 5 Structures of subnetworks in the heterogeneous network

圖6 異構(gòu)網(wǎng)絡(luò)示意圖Fig.6 Illustration for heterogeneous interdependent network

圖7 異構(gòu)耦合網(wǎng)絡(luò)中不同免疫策略 的免疫效率對(duì)比結(jié)果Fig.7 Comparison of immunization efficiencies in the heterogeneous interdependent network

下面仍以交互式郵件傳播模型[30]為基礎(chǔ),分析異構(gòu)耦合網(wǎng)絡(luò)的抗毀性及各類免疫策略對(duì)異構(gòu)耦合網(wǎng)絡(luò)的保護(hù)能力. 本文先從整個(gè)網(wǎng)絡(luò)中隨機(jī)選取2個(gè)初始感染節(jié)點(diǎn),并根據(jù)不同策略要求從網(wǎng)絡(luò)中選取不同比例的免疫節(jié)點(diǎn). 圖7為異構(gòu)耦合網(wǎng)絡(luò)中不同免疫策略的免疫效率對(duì)比結(jié)果. 由圖7可見,在異構(gòu)網(wǎng)絡(luò)中,雖然基于AOC免疫策略的效率優(yōu)于其他策略,但低于在同構(gòu)網(wǎng)絡(luò)中的效率,表明設(shè)計(jì)異構(gòu)耦合網(wǎng)絡(luò)中的免疫策略是關(guān)鍵.

圖8 從不同子網(wǎng)絡(luò)展開攻擊時(shí)的病毒傳播曲線Fig.8 Virus propagation in each subnetwork of a heterogeneous interdependent network

為進(jìn)一步分析異構(gòu)耦合網(wǎng)絡(luò)的魯棒性,設(shè)定病毒從不同子網(wǎng)絡(luò)展開攻擊,即分別從不同子網(wǎng)絡(luò)中選取2個(gè)節(jié)點(diǎn)作為初始感染節(jié)點(diǎn). 圖8為應(yīng)用目標(biāo)免疫后,病毒在不同子網(wǎng)絡(luò)中的傳播趨勢(shì). 由圖8可見,無(wú)論從何處展開攻擊,G3和G4子網(wǎng)絡(luò)感染速度都最快、 范圍最廣. 因此,對(duì)異構(gòu)耦合網(wǎng)絡(luò)中WS和ER子網(wǎng)絡(luò)的免疫是難點(diǎn).

綜上所述,網(wǎng)絡(luò)免疫技術(shù)是抑制病毒傳播的主要方法之一,也是復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)的主要研究?jī)?nèi)容. 本文先對(duì)網(wǎng)絡(luò)免疫的基本原理和關(guān)鍵技術(shù)進(jìn)行定性分析,然后在同構(gòu)網(wǎng)絡(luò)中定量分析了各策略的免疫效率、 免疫代價(jià)和免疫魯棒性. 實(shí)驗(yàn)結(jié)果表明,免疫策略對(duì)同構(gòu)網(wǎng)絡(luò)的保護(hù)能力與其計(jì)算量近似成反比. 如隨機(jī)免疫策略與其他5種免疫策略相比,計(jì)算量最小,但對(duì)網(wǎng)絡(luò)的保護(hù)能力最弱；而基于介數(shù)的免疫策略計(jì)算量最大,但該策略利用中心控制選擇節(jié)點(diǎn)(邊)介數(shù)最大的節(jié)點(diǎn)進(jìn)行免疫,可實(shí)現(xiàn)最好的免疫效率,高效阻斷病毒傳播路徑. 本文構(gòu)建了一種新型異構(gòu)耦合網(wǎng)絡(luò),并分析了免疫策略對(duì)異構(gòu)耦合網(wǎng)絡(luò)的保護(hù)能力,實(shí)驗(yàn)結(jié)果表明,已有各類免疫策略對(duì)異構(gòu)耦合網(wǎng)絡(luò)的保護(hù)能力有限,設(shè)計(jì)一種適合異構(gòu)耦合網(wǎng)絡(luò)的分布式網(wǎng)絡(luò)免疫策略是一個(gè)亟待解決的問(wèn)題.

[1] Pastor-Satorras R,Vespignani A. Immunization of Complex Networks [J]. Physical Review E,2002,65(3): 036104.

[2] CHEN Yi-ping,Paul G,Havlin S,et al. Finding a Better Immunization Strategy [J]. Physical Review Letters,2008,101(5): 058701.

[3] HU Ke,TANG Yi. Immunization for Scale-Free Networks by Random Walker [J]. Chinese Physics,2006,15(12): 2782-2787.

[4] Cohen R,Havlin S,Ben-Averaham D. Efficient Immunization Strategies for Computer Networks and Populations [J]. Physical Review Letters,2003,91(24): 247901.

[5] Echenique P,Gomez-Gardenes J,Moreno Y,et al. Distanced Covering Problem in Scale-Free Networks with Degree Correlation [J]. Physical Review E,2005,71(3): 035102.

[6] Cornforth D M,Reluga T C,Shim E,et al. Erratic Flu Vaccination Emerges from Short-Sighted Behavior in Contact Networks [J]. PLoS Computational Biology,2011,7(1): e1001062.

[7] Ames G M,George D B,Hampson C P,et al. Using Network Properties to Predict Disease Dynamics on Human Contact Networks [J]. Proceedings of the Royal Society B,2011,278: 3544-3550.

[8] GAO Jin-xi,Buldyrev S V,Havlin S,et al. Robustness of a Network of Networks [J]. Physical Review Letters,2011,107(19): 195701.

[9] Vespignani A. Complex Networks: The Fragility of Interdependency [J]. Nature,2010,464: 984-985.

[10] Menach A L,Tatem A J,Cohen J M,et al. Travel Risk,Malaria Importation and Malaria Transmission in Zanzibar [J]. Science Report,2011,1: article number 93.

[11] Rivas A L,Fasina F O,Hoogesteyn A L,et al. Connecting Network Properties of Rapidly Disseminating Epizoonotics [J]. PLoS One,2012,7(6): e39778.

[12] Bonté B,Mathias J D,Duboz R. Moment Approximation of Infection Dynamics in a Population of Moving Hosts [J]. PLoS One,2012,7(12): e51760.

[13] Stehlé J,Voirin N,Barrat A,et al. High-Resolution Measurements of Face-to-Face Contact Patterns in a Primary School [J]. PLoS One,2011,6(8): e23176.

[14] LI Wei,Bashan A,Buldyrev S V,et al. Cascading Failures in Interdependent Lattice Networks: The Critical Role of the Length of Dependency Links [J]. Physical Review Letters,2012,108(22): 228702.

[15] Hasegawa T,Konno K,Nemoto K. Robustness of Correlated Networks against Propagating Attacks [J]. The European Physical Journal B,2012,85: 262.

[16] Narasimhamurthy A,Greene D,Hurley N,et al. Partitioning Large Networks without Breaking Communities [J]. Knowledge and Information Systems,2010,25(2): 345-369.

[17] Holme P,Kim B J,Yoon C N,et al. Attack Vulnerability of Complex Networks [J]. Physical Review E,2002,65(5): 056109.

[18] Carmi S,Havlin S,Kirkpatrick S,et al. A Model of Internet Topology Usingk-Shell Decomposition [J]. Proceedings of the National Academy of Sciences of the United States of America,2007,104(27): 11150-11154.

[19] Kitsak M,Gallos L K,Havlin S,et al. Identification of Influential Spreaders in Complex Networks [J]. Nature Physics,2010,6: 888-893.

[20] Gallos L K,Liljeros F,Argyrakis P,et al. Improving Immunization Strategies [J]. Physical Review E,2007,75(4): 045104.

[21] WANG Bing,Aihara K,Kim B J. Comparison of Immunization Strategies in Geographical Networks [J]. Physics Letters A,2009,373(42): 3877-3882.

[22] Holme P. Efficient Local Strategies for Vaccination and Network Attack [J]. Europhysics Letters,2004,68(6): 908-914.

[23] Gómez-Gardenes J,Echenique P,Moreno Y. Immunization of Real Complex Communication Networks [J]. The European Physical Journal B,2002,49(2): 259-264.

[24] Christakis N A,Fowler J H. Social Network Sensors for Early Detection of Contagious Outbreaks [J]. PLoS One,2010,5(9): e12948.

[25] HUANG Xin-li,ZOU Fu-tai,MA Fan-yuan. Targeted Local Immunization in Scale-Free Peer-to-Peer Networks [J]. Journal of Computer Science and Technology,2007,22(3): 457-468.

[26] LIU Zong-hua,HU Bambi. Epidemic Spreading in Community Networks [J]. Europhysics Letters,2005,72(2): 315-321.

[27] GAO Chao,LIU Ji-ming,ZHONG Ning. Network Immunization with Distributed Autonomy-Oriented Entities [J]. IEEE Transactions on Parallel and Distributed Systems,2011,22(7): 1222-1229.

[28] HUANG Jing,LIU Da-you,YANG Bo,et al. A Self-organization Based Divide and Conquer Algorithm for Distributed Constraint Optimization Problems [J]. Journal of Computer Research and Development,2008,45(11): 1831-1839. (黃晶,劉大有,楊博,等. 自組織分治求解分布式約束優(yōu)化問(wèn)題 [J]. 計(jì)算機(jī)研究與發(fā)展,2008,45(11): 1831-1839.)

[29] Bu S T,Towsley D. On Distinguishing between Internet Power Law Topology Generators [C]//Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02). New York: IEEE,2002: 638-647.

[30] Zou C C,Towsley D,GONG Wei-bo. Modeling and Simulation Study of the Propagation and Defense of Internet E-mail Worms [J]. IEEE Transaction on Dependable and Secure Computing,2007,4(2): 105-118.

[31] Dickison M,Havlin S,Stanley H E. Epidemics on Interconnected Networks [J]. Physical Review E,2012,85(6): 066109.

[32] Tanizawa T,Havlin S,Stanley H E. Robustness of Onionlike Correlated Networks against Targeted Attacks [J]. Physical Review E,2012,85(4): 046109.

[33] Parshani R,Buldyrev S V,Havlin S. Interdependent Networks: Reducing the Coupling Strength Leads to a Change from a First to Second Order Percolation Transition [J]. Physical Review Letters,2010,105(4): 048701.