復雜網絡免疫策略分析

李向華,王 欣,高 超

(1. 西南大學 計算機與信息科學學院,重慶 400715;2. 吉林大學 計算機科學與技術學院,長春 130012)

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

判斷一種網絡免疫策略是否可在網絡中有效執行,通常從兩方面評價: 1) 策略對網絡的保護能力,即評估其對病毒傳播的抑制能力;2) 策略的可執行能力,即策略部署需要的前提條件. 優秀的網絡免疫策略應首先能有效地抑制病毒的傳播,保護網絡中大多數節點不被病毒感染;同時必須能克服網絡拓撲結構和網絡動態性的影響,易于在網絡中部署.

1 復雜網絡免疫策略分類及分析

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

按獲取信息程度的不同,目前的網絡免疫策略可分為全局免疫策略和局部免疫策略;而按選取依據不同,又可分為基于節點度數、 基于網絡介數和基于節點核數的免疫策略.

1.1 基于網絡全局信息的免疫策略

節點度數反映了節點在網絡中的重要程度,目標免疫策略[1-2]作為全局性策略,根據網絡拓撲信息直接選擇網絡中度數最大的一組節點作為免疫節點,取得了非常好的免疫效果. 而介數反映了節點(邊)在特定網絡結構中承載的流量,進而反映其通信中轉能力[16]. 通常介數大的節點(邊)是兩個社團的橋梁,如果將節點(邊兩端的節點)去除,則可將網絡分割成多個子網絡,進而阻止病毒擴散[17]. 因此,基于介數的免疫策略[17]選取網絡中中轉能力強的中繼節點抑制病毒傳播. 圖1為不同免疫策略選擇免疫節點的示意圖. 由圖1可見,基于節點介數的免疫策略會選擇網絡中節點介數最大的V9進行免疫；邊介數免疫策略則從邊介數最大的邊L1和L2兩端節點(V5,V7或V9)中隨機選擇一個免疫. 通過免疫介數大的節點,可將圖1網絡劃分為兩個子網絡,如果免疫V5或V9,則該策略還能進一步打破上(或下)側子網絡的內部結構,不僅阻止病毒在不同子網絡間的傳播,而且阻止了病毒在子網絡內的傳播. 文獻[17]通過實驗證明：節點介數免疫策略的效率優于目標免疫. 因此,免疫策略不但要保護網絡中的重要節點(即度大節點),而且中繼節點也要進行免疫才能更好地控制病毒的傳播.

圖1 不同免疫策略選擇免疫節點的示意圖Fig.1 Illustration for immunized nodes selected by different immunization strategies

還有些全局免疫策略通過節點的核數(k-shell或k-core)值[18]選擇免疫節點. 當網絡中只有單一病毒傳播源時,基于核數免疫策略的效率優于目標免疫策略；但當存在多個病毒傳播源時,則遜于目標免疫策略[19]. 這是因為基于核數免疫策略選擇的節點大多數是網絡的核心,聚集在網絡的中心位置,而目標免疫選擇的節點可分散在網絡中的任意位置. 由于本文仿真實驗采用多源攻擊,因此實驗部分并未對比基于核數策略與其他策略的性能差別.

綜上所述,雖然全局免疫策略可取得很好的免疫效果,但現實網絡大多數是分布式和離散式的,獲取整個網絡拓撲信息幾乎無法實現. 同時,對于一些缺乏集中管理的大規模動態網絡,很難獲取整個網絡信息,為了在效率和可行性之間取得平衡,人們提出了基于局部信息的免疫策略.

1.2 基于網絡局部信息的免疫策略

局部免疫策略克服了全局策略需要預先掌握網絡拓撲的瓶頸,其中隨機免疫策略[1,3]忽略網絡節點屬性差異,以等概率方式選取一定比例的節點進行保護. 雖然該策略對均勻網絡的保護能力較優,但在無標度網絡中,該策略幾乎需要免疫所有節點才可能阻止病毒傳播[1],這在現實世界很難實現.

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

基于圖覆蓋的免疫策略將免疫過程視為一個圖覆蓋問題,即以“種子”節點為中心,免疫其周圍d步范圍內的最大度節點. 該方法利用一定局部拓撲知識,取得明顯優于鄰居免疫的效果. 但由于該策略選擇節點行為固定,受網絡拓撲,特別是社團結構的影響較大,常陷入局部最優解[26]. 雖然該方法適合于分布式網絡,但其計算復雜性隨覆蓋距離的增加而指數級增大,且在實際應用中,用戶很難獲得間接鄰居信息. 同時,該策略并未考慮任何與應用領域相關的啟發信息,也未回答針對不同網絡,d值如何選取,因此具有一定的局限性.

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

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

2 同構網絡中免疫策略對比及分析

本文以兩個真實郵件網絡(美國安然公司和西班牙ROVIRA I VIRGILI大學郵件網絡)及GLP算法[29]構建的人工網絡作為實驗用的同構網絡,從免疫效率、 代價和魯棒性三方面定量分析不同類型免疫策略對病毒的抑制能力,所用網絡列于表1. 對比免疫相同數目節點時,用網絡中最終被感染節點的數目判斷哪種策略免疫效率最好;免疫代價不僅比較了各策略的時間復雜度,還分析了免疫臨界值,即選擇哪種策略可在免疫最少節點的情況下,將病毒傳播率控制在最小范圍內;魯棒性則分析對比各策略對網絡拓撲變化的適應能力.

表1 實驗所用同構網絡Table 1 Homogeneous networks used in experiments

2.1 免疫效率

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

表2列出了各類策略在合成網絡中的免疫效率,括號內的數字表示不采用策略時網絡中被感染的節點總數. 由表2可見,在選取相同數目免疫節點的前提下,掌握了全局拓撲信息的節點介數免疫策略對病毒傳播的抑制能力最強. 而在全局信息未知情況下,基于AOC策略的免疫效果最佳. 實驗結果也表明控制病毒的傳播并非只保護網絡中度數大的節點,那些傳輸能力強的中繼節點對病毒的傳播也起至關重要的作用. 而基于AOC的免疫策略利用自組織和正反饋機制在局域環境中搜索最大度節點的同時,間接免疫了那些具有大度數的中繼節點,因而取得了比其他基于節點度數免疫策略更好的免疫效率. 人工社團網絡(該網絡具有4個社區,由100條邊將獨立的社區連接在一起)的免疫結果與人工合成網絡相似.

表2 人工合成網絡中不同免疫策略的免疫效率對比結果Table 2 Immunization efficiencies of different strategies in synthetic networks

圖2 人工社團網絡最終感染的節點 數目隨時間變化曲線Fig.2 Final number of infected nodes with time varying in the synthetic community-based network

圖2對表現較優的4種免疫策略做了進一步分析. 其中,節點介數免疫策略明顯優于目標免疫策略,這是因為介數免疫可有效破壞網絡拓撲,增加網絡平均路徑長度,切斷病毒傳播路徑. 由于基于AOC免疫策略選擇的節點不僅節點度數大,而且介數值高,所以其免疫效率又優于只保護了節點介數大的介數免疫策略.

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

文獻[17]驗證了節點介數免疫策略的免疫效率優于目標免疫策略,這是因為介數免疫策略可有效破壞原有網絡拓撲結構,通過增加網絡平均路徑長度的方式阻斷病毒傳播路徑. 而本文實驗表明,基于AOC的分布式免疫策略的免疫效率在某些情況下甚至優于節點介數免疫策略. 這是因為基于AOC免疫策略選擇的免疫節點不僅具有較大的節點度數,同時搜索自治體在網絡中按照網絡鏈路的鏈接關系進行游走時,會先保護網絡中中轉能力強的節點,即介數大的節點. 所以基于AOC免疫策略選出的免疫節點不僅具有較大的節點介數值,同時具有較大的節點度數值,因此可更有效地切斷病毒傳播路徑.

表3 真實網絡中不同免疫策略的免疫效率對比結果Table 3 Comparison of immunization efficiencies from different immunization strategies in benchmark networks

圖3 安然郵件網絡的病毒傳播示意圖Fig.3 Illustration for viruses propagation in Enron email network

2.2 免疫代價

表4 計算復雜性對比結果Table 4 Comparison of computational complex of immunization strategies

由表4可見,基于AOC免疫策略的計算復雜性最小,而全局的介數免疫策略和目標免疫策略因為需要掌握全局拓撲結構才可以實施,因此計算復雜性最大. 在現實應用中,免疫某個節點需要一定成本,為了既能抑制病毒傳播,又能降低成本,高效的免疫策略應通過免疫盡量少的節點控制病毒的感染率. 因此衡量免疫代價的另一個指標就是為了達到免疫臨界值所需免疫節點比例. 為便于闡述,定義以下變量: ρ0表示不應用免疫策略時網絡的最終感染密度(ρ0=NI/N,其中NI表示被感染節點總數);ρf表示應用免疫策略后網絡節點最終感染密度;ρ表示病毒傳播感染率,ρ=ρf/ρ0. 根據文獻[25],定義fc作為免疫臨界值,表示為使病毒的傳播率ρ→0時,需要免疫的網絡節點比例值f.

圖4對比了采用隨機攻擊時,兩種人工合成網絡中ρ隨免疫節點比例f的變化過程. 實驗表明,節點介數免疫策略能花費最小的f值有效保護網絡;而在分布式策略中,基于AOC的免疫策略免疫代價最小. 以圖4(A)為例,當ρ=0.1時,節點介數免疫策略需要的免疫臨界值f1小于基于AOC的免疫臨界值f2,而f2小于目標免疫臨界值f3,即f1

圖4 不同冪率結構人工網絡中的免疫代價對比Fig.4 Comparison of immunization costs in synthetic networks with different power-law exponents

圖5 免疫臨界值隨網絡結構的變化關系Fig.5 Change of immunization critical value (fc) with the network structure

2.3 免疫魯棒性

面對網絡結構差異,同一策略在不同網絡中會得到不同的效果,但最佳策略應不受網絡拓撲影響,即策略應具有魯棒性[25]. 圖5為免疫臨界值fc與網絡冪指數之間的變化關系. 由圖5可見,fc的變化幅度越小,當網絡結構變化時,為抑制病毒傳播所需免疫的節點比例變化越小,策略魯棒性越強. 實驗結果表明,節點介數策略的魯棒性最好,但該策略受網絡拓撲結構限制,無法應用于大規模分布式網絡中. 而在分布式策略中,基于AOC策略的魯棒性最好. 同時,該策略的搜索性能所展現的魯棒性更適用于大規模、 分布式的動態網絡[27].

3 異構耦合網絡中免疫策略分析

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

異構耦合網絡構建過程如下:

1) 構建4個具有獨立度的分布網絡,分別用G1,G2,G3,G4表示,其中: G1和G2由GLP網絡產生器[29]產生無標度網絡,冪指數分別為1.7和2.7;G3是利用WS模型構建的小世界網絡;G4是利用ER模型構建的隨機網絡. 表5列出了4個獨立網絡的結構屬性,圖6(A)的度分布清晰展現了4個獨立網絡的異質特性.

2) 在獨立網絡間隨機添加100條邊,構建異構耦合網絡,如圖6(B)所示. 如果網絡M和N之間邊數用EMN表示,則E12=17,E13=14,E14=14,E23=21,E24=19,E34=15.

表5 異構網絡中的子網絡結構Table 5 Structures of subnetworks in the heterogeneous network

圖6 異構網絡示意圖Fig.6 Illustration for heterogeneous interdependent network

圖7 異構耦合網絡中不同免疫策略 的免疫效率對比結果Fig.7 Comparison of immunization efficiencies in the heterogeneous interdependent network

下面仍以交互式郵件傳播模型[30]為基礎,分析異構耦合網絡的抗毀性及各類免疫策略對異構耦合網絡的保護能力. 本文先從整個網絡中隨機選取2個初始感染節點,并根據不同策略要求從網絡中選取不同比例的免疫節點. 圖7為異構耦合網絡中不同免疫策略的免疫效率對比結果. 由圖7可見,在異構網絡中,雖然基于AOC免疫策略的效率優于其他策略,但低于在同構網絡中的效率,表明設計異構耦合網絡中的免疫策略是關鍵.

圖8 從不同子網絡展開攻擊時的病毒傳播曲線Fig.8 Virus propagation in each subnetwork of a heterogeneous interdependent network

為進一步分析異構耦合網絡的魯棒性,設定病毒從不同子網絡展開攻擊,即分別從不同子網絡中選取2個節點作為初始感染節點. 圖8為應用目標免疫后,病毒在不同子網絡中的傳播趨勢. 由圖8可見,無論從何處展開攻擊,G3和G4子網絡感染速度都最快、 范圍最廣. 因此,對異構耦合網絡中WS和ER子網絡的免疫是難點.

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

[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. (黃晶,劉大有,楊博,等. 自組織分治求解分布式約束優化問題 [J]. 計算機研究與發展,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.