肖詠

摘? 要： 提出一種基于圖覆蓋的改進復(fù)雜網(wǎng)絡(luò)免疫策略。該方法引入模擬退火的思想，利用局部信息，以節(jié)點度大為原則選取免疫節(jié)點，同時以一定的概率接受度小的節(jié)點。使用交互式郵件傳播模型，在真實的網(wǎng)絡(luò)數(shù)據(jù)集上從免疫效率和免疫代價的角度進行了對比實驗。實驗結(jié)果發(fā)現(xiàn)，改進的方法在一些社團結(jié)構(gòu)明顯的網(wǎng)絡(luò)中具有更好的效果，從而驗證該方法的有效性。

關(guān)鍵詞： 圖覆蓋; 免疫策略; 模擬退火; 免疫效率; 免疫代價

中圖分類號：TP391? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2021）05-53-05

An improved complex network immunization strategy based on graph covering

Xiao Yong

（Information Technology Center， Chongqing Medical University， Yuzhong， Chongqing 400016， China）

Abstract： An improved complex network immune strategy based on graph coverage is proposed. This method introduces the idea of simulated annealing， uses local information， selects immune nodes according to the principle of large node degree， and accepts nodes with small degree with a certain probability. Using the interactive e-mail propagation model， a comparative experiment is conducted on real network data sets from the perspective of immune efficiency and immune cost. The experimental results show that the improved method has better effect in some networks with obvious community structure， which verifies the effectiveness of the method.

Key words： graph covering; immune strategy; simulated annealing; immune efficiency; immune cost

0 引言

現(xiàn)今，復(fù)雜網(wǎng)絡(luò)的病毒傳播相關(guān)研究已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的重要研究分支，近年來的研究表明，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)小世界和無標度特性，在很大程度上影響病毒的傳播行為，在現(xiàn)實復(fù)雜網(wǎng)絡(luò)中，發(fā)生少量病毒感染源即使病毒傳播速率非常低，也可以在網(wǎng)絡(luò)中廣泛蔓延開來[1-3]，故挖掘有效的免疫策略來控制病毒的爆發(fā)與傳播具有重大現(xiàn)實意義。針對免疫策略，人們做了大量研究，提出了以隨機免疫[4]，目標免疫[5]，熟人免疫[6]，圖覆蓋免疫[7]為代表的一系列免疫策略。本文在圖覆蓋免疫的基礎(chǔ)上，結(jié)合模擬退火思想，提出了一種改進的策略。通過在真實社團網(wǎng)絡(luò)數(shù)據(jù)集上的實驗，驗證了本文策略具有更好的免疫效果。

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

復(fù)雜網(wǎng)絡(luò)一般用圖來表示，一個具體的網(wǎng)絡(luò)可抽象為圖G=（V，E），由節(jié)點集V（vertex）和邊集E（edge）組成，免疫的核心思想就是想辦法找到一些重要的點，提前采取保護措施來降低節(jié)點感染的概率，從而阻止病毒的傳播。

隨機免疫，不考慮節(jié)點和網(wǎng)絡(luò)拓撲結(jié)構(gòu)的差異，在網(wǎng)絡(luò)中隨機選取一定比例的節(jié)點進行免疫，發(fā)現(xiàn)在均勻網(wǎng)絡(luò)中是有效的，而在大規(guī)模無標度網(wǎng)絡(luò)中幾乎需要免疫所有節(jié)點才能控制病毒的傳播，顯然，這是沒有意義的。

目標免疫，其核心思想是找到網(wǎng)絡(luò)中一部分重要節(jié)點進行免疫，以節(jié)點度為代表，這是利用了無標度網(wǎng)絡(luò)中大部分節(jié)點的度很小、小部分節(jié)點的度很大的特性，一旦控制住了度大的節(jié)點，其他節(jié)點被感染的幾率會顯著降低，花費比較小的代價起到了很好的控制效果。然而作為一個全局性的免疫策略，目標免疫必須遍歷掌握整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，對于現(xiàn)實大規(guī)模和動態(tài)網(wǎng)絡(luò)，實施難度顯而易見。

熟人免疫，試圖找到一個方法既能克服目標免疫需要全局信息的缺點，又能達到目標免疫的效果，首先在網(wǎng)絡(luò)中隨機選取一部分節(jié)點，然后以他們?yōu)榛A(chǔ)，再次隨機選取他們周圍一個或者多個節(jié)點進行免疫，因為無標度網(wǎng)絡(luò)大部分節(jié)點的度很小，第一次隨機到他們的可能性較大，他們往往連接著度大的節(jié)點，第二次隨機到度大的節(jié)點概率也較大，故只需要局部信息，就可以獲得比隨機免疫好的效果，但是事實上，這種隨機選擇的方式，在效果上與目標免疫還是有一定的差距。

圖覆蓋免疫在熟人免疫的基礎(chǔ)上加以改進，轉(zhuǎn)換為一個圖論覆蓋問題，第一次仍然在網(wǎng)絡(luò)中隨機選取一部分節(jié)點，以他們?yōu)橹行?，再次選取d步以內(nèi)鄰居中度最大的節(jié)點進行免疫，d=1為選取節(jié)點的鄰居節(jié)點，d=2為選取鄰居的鄰居節(jié)點，此方式也是利用了局部信息，第二次有目標的選擇使得它具有比熟人免疫更好的免疫效果。

表1為不同免疫策略對比[8]，其中N為節(jié)點總數(shù)，n為免疫節(jié)點數(shù)，為平均節(jié)點數(shù)，k表示策略想要選擇的熟人數(shù)目，可以看出，單從免疫效果上講，目標免疫效果最好，但是時間復(fù)雜度最高，圖覆蓋免疫效果次之，時間復(fù)雜度也相對低些。

2 改進的免疫策略

圖覆蓋免疫策略能夠以局部信息獲得較好的免疫效果，在現(xiàn)實網(wǎng)絡(luò)中具有較好的操作性，但該策略選擇節(jié)點行為固定，受網(wǎng)絡(luò)拓撲， 特別是社團結(jié)構(gòu)的影響較大，常陷入局部最優(yōu)解[8]，以圖1為例，該網(wǎng)絡(luò)有明顯的社團結(jié)構(gòu)，假設(shè)第一次隨機選擇到種子節(jié)點v15，d=1時，根據(jù)圖覆蓋免疫的原理，第二次應(yīng)選擇v16，而我們發(fā)現(xiàn)v12盡管不是d=1時的最大度節(jié)點，但是它起到更為重要的作為，保護v12能夠阻止病毒朝著v5-v11這個社團傳播，從這個角度看，v16只是局部最優(yōu)解，從全局看并不能起到最優(yōu)的效果。

所以圖覆蓋免疫要避免在社團結(jié)構(gòu)明顯的網(wǎng)絡(luò)中陷入局部最優(yōu)解，就不能在第二次選擇過程中只考慮度最大的節(jié)點，度小的節(jié)點也需要加以考慮，但是也不能直接選擇度小的節(jié)點。這里，我們引入模擬退火的思想[9-10]，通過模擬物理中高溫物體的退火過程尋找全局最優(yōu)解，首先產(chǎn)生一個初始解為當前解，隨著溫度的下降，以一定的概率接受非局部最優(yōu)解為新解，使之跳出局部最優(yōu)的陷阱，并重復(fù)這個過程至條件結(jié)束，開始溫度較高時，接受較差解的概率也比較高，會有更大的機會跳出局部最優(yōu)解，隨著退火的進行即溫度的逐步下降，算法接收較差解的概率也變小。故我們在第二次選取種子節(jié)點的鄰居節(jié)點時，不是直接選取度最大的節(jié)點，而是以一定的規(guī)則去選取，定義選取的規(guī)則如下：

[Pvi=1，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? vj.deg

其中，T為溫度，vj.deg為在遍歷過程節(jié)點過程中臨時解的度，vi.deg為目標節(jié)點的度。選取的過程如下。

⑴ 在網(wǎng)絡(luò)中第一次隨機選取一部分節(jié)點，以它們?yōu)橹行?，假設(shè)取d=1，遍歷它們的鄰居節(jié)點。

⑵ 初始化溫度T，當前選取節(jié)點vj為初始解。

⑶ 如果遍歷到vi，節(jié)點vi的度大于vj的度，那么節(jié)點vi為新解，否則根據(jù)公示計算概率1/（1+exp（（vj.deg-vi.deg）/T）），根據(jù)結(jié)果決定是否選取節(jié)點vi。

⑷ 如果達到終止條件，則算法結(jié)束，否則按衰減函數(shù)得到新的溫度T重復(fù)步驟⑵-⑷。

可以看出，開始溫度較高時，選取度小的概率相對來說還比較高，隨著算法迭代，溫度不斷降低，概率越來越低，并且目標節(jié)點的度越小，選取的概率越小，但是不代表一定不選取。為了更好的理解這個過程，我們還是以圖1為例：假設(shè)第一次隨機選擇到種子節(jié)點v15，d=1，遍歷v15的鄰居節(jié)點，v16為初始解，開始設(shè)定溫度為100，根據(jù)選取規(guī)則，選取v14的概率為49.25%，隨著環(huán)境變化，假設(shè)溫度下降到了10，選取v14的概率為42.56%，盡管概率變小，但還是有跳出局部最優(yōu)解的可能。

改進后的免疫策略思路為：第一次在網(wǎng)絡(luò)中隨機選取一部分節(jié)點，以他們?yōu)橹行?，再次在d步以內(nèi)的鄰居中選取目標節(jié)點進行免疫，目標節(jié)點以盡量選取度大的為原則，同時以一定的概率接受度小的節(jié)點，以跳出局部最優(yōu)解。

3 實驗分析

3.1 實驗數(shù)據(jù)集

本文選取NetScience網(wǎng)絡(luò)數(shù)據(jù)集、Geom網(wǎng)絡(luò)數(shù)據(jù)集來進行實驗，NetScience[11]網(wǎng)絡(luò)是一些科學家關(guān)于網(wǎng)絡(luò)原理和實驗研究的合作關(guān)系，Geom網(wǎng)絡(luò)是科學家關(guān)于計算機幾何學研究的合作關(guān)系，NetScience網(wǎng)絡(luò)和Geom網(wǎng)絡(luò)具有明顯的社團結(jié)構(gòu)，表2為它們的基本統(tǒng)計特性。

3.2 實驗方案

盡管免疫的核心問題已經(jīng)轉(zhuǎn)化為找出一些重要的節(jié)點來進行保護，但評價一種免疫策略的有效性必須結(jié)合病毒傳播模型，觀察在病毒的傳播過程中，是否有效地被抑制，本文選擇交互式郵件傳播模型[12]來觀察實驗結(jié)果。

在交互式郵件傳播模型中，用戶分為健康、危險、感染三種狀態(tài)，病毒的傳播主要與用戶檢查郵件的時間T和點擊病毒郵件的概率C有關(guān)，T和C服從高斯分布，本文中T和C的設(shè)定與原文模型保持一致，即取T～N（40，202），C～N（0.5，0.32），算法步驟如下。

⑴ 初始化網(wǎng)絡(luò)結(jié)構(gòu)。

⑵ 初始化節(jié)點狀態(tài)，選取感染節(jié)點。

⑶ 根據(jù)免疫策略選取免疫節(jié)點。

⑷ 針對每個節(jié)點，用戶查看郵箱操作，如果檢查郵件的時間滿足，并且打開了病毒附件，則被感染，并且向鄰居列表的所有用戶發(fā)送病毒郵件，如果沒有打開則默認恢復(fù)到健康狀態(tài)。

⑸ 更新下次查看郵箱時間。

⑹ 輸出每個時間步的感染節(jié)點數(shù)。

3.3 實驗結(jié)果分析

當病毒在網(wǎng)絡(luò)中的傳播趨于相對穩(wěn)定的狀態(tài)時，通過對比被感染的節(jié)點數(shù)量來衡量免疫策略的效果，為了消除隨機性對實驗結(jié)果的影響，我們將對每次實驗運行100次，取100次實驗的平均值作為實驗結(jié)果，算法時間步數(shù)為600，圖覆蓋半徑d=1，初始隨機感染節(jié)點數(shù)量為2，圖2、圖3為在2個網(wǎng)絡(luò)數(shù)據(jù)集中取1%（分別為16、73個）的免疫節(jié)點后網(wǎng)絡(luò)中被感染的節(jié)點數(shù)量隨時間的變化趨勢，實驗結(jié)果表明，病毒攻擊網(wǎng)絡(luò)后，網(wǎng)絡(luò)中被感染的節(jié)點快速上升，隨著時間的增加，慢慢趨于平衡，對比原方法和本文改進的方法，采用本文改進的方法最終被感染的節(jié)點低于原方法，效果有所提升，在2個網(wǎng)絡(luò)中分別提升約13%和7%。同時我們發(fā)現(xiàn)由于實驗結(jié)果無法避免隨機性，本文的方法也存在無法優(yōu)于原方法的情形，出現(xiàn)這種情形是由于不是每次實驗都會陷入局部最優(yōu)解。

圖4、圖5為在不同免疫比例下被感染的節(jié)點數(shù)量，在同一免疫比例下，本文改進的方法效果優(yōu)于原方法，隨著免疫比例的提升，網(wǎng)絡(luò)中被感染的節(jié)點數(shù)量明顯下降，病毒的傳播被控制在比較低的水平。

考慮免疫效率的同時，免疫代價也不可忽視，它也是衡量免疫策略有效性的一個重要指標，即采用較少的免疫節(jié)點使病毒感染傳播率達到一個較低的水平，病毒感染傳播率ρ=ρf/ρ0，ρf為采用免疫策略后的感染密度，ρ0為沒有采用免疫策略的感染密度，感染密度為感染節(jié)點數(shù)與總節(jié)點數(shù)的比值，定義?c作為免疫臨界值，表示當病毒的感染傳播率ρ趨于0時，所需要的免疫節(jié)點比例值。本文對此設(shè)計了另一組實驗，圖6、圖7的實驗結(jié)果為網(wǎng)絡(luò)中病毒感染傳播率隨免疫比例的變化情況，結(jié)果表明為了使病毒的感染傳播率控制在一定比例下，在趨近免疫臨界值時，本文改進的方法能夠使用更小的免疫節(jié)點比例值，以較小的免疫代價有效地保護網(wǎng)絡(luò)，控制病毒的傳播。

4 結(jié)束語

復(fù)雜網(wǎng)絡(luò)的免疫策略研究對抑制病毒傳播具有重點現(xiàn)實意義，本文先對比分析了幾種經(jīng)典的免疫策略，基于圖覆蓋免疫策略，引入模擬退火的思想，提出一種改進方法，結(jié)合交互式郵件傳播模型，在真實的網(wǎng)絡(luò)數(shù)據(jù)上設(shè)計了多組實驗，從免疫效率和免疫代價的角度對比了原方法和本文改進的方法，發(fā)現(xiàn)改進的方法在一些社團結(jié)構(gòu)明顯的網(wǎng)絡(luò)中具有更好的效果，從而驗證了本文方法的有效性。未來的研究方向是針對不同的網(wǎng)絡(luò)，如何選取圖覆蓋距離d的取值。

參考文獻（References）：

[1] 阮中遠.復(fù)雜網(wǎng)絡(luò)上的流行病傳播[J].中國科學：物理學力學天文學，2020.1.

[2] 葛新，趙海，張君.基于熟人免疫的復(fù)雜網(wǎng)絡(luò)免疫策略[J].計算機科學，2011.38（11）：83-86

[3] 李向華，王欣，高超.復(fù)雜網(wǎng)絡(luò)免疫策略分析[J].吉林大學學報（理學版），2013.3：444-452

[4] Cohen J E. Infectious Diseases of Humans： Dynamics andControl[J].JAMA The Journal of the American Medical Association，1992.268（23）：3381

[5] Pastor-Satorras R， Vespignani A. Immunization ofcomplex networks.[J].Physical Review E，2002.65（3）：106-126

[6] Cohen R， Havlin S， Ben-Avraham D. Efficient Immuniza-tion Strategies for Computer Networksand Populations[J].Phys Rev Lett，2003.91（24）12343-12343

[7] P E， J G， Y M， et al. Distance-d covering problems inscale-free networks with degreecorrelations[J].Physical Review E，2005.71（3）：142-154

[8] Gao C，Liu J， Zhong N.Network Immunization withDistributed Autonomy-Oriented Entities[J]. IEEE Transactions on Parallel & Distributed Systems，2011.22（7）：1222-1229

[9] Metropolis N ， Rosenbluth A W ， Rosenbluth M N， et al.Equation of State Calculations by Fast Computing Machines[J].The Journal of Chemical Physics，2004.21.

[10] Jinna Ma， Yong Xiao， Hailing Xiong. An Improved AOC-Based Immunization Strategy Based on Simulated Annealing[J]. Journal of Computational Information Systems，2015.11（8）： 2915-292

[11] Newman M E. Finding community structure in networksusing the eigenvectors of matrices[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics，2006.74（3 Pt 2）：92-100

[12] Zou C C， Towsley D， Gong W. Modeling and SimulationStudy of the Propagation and Defense of Internet Email Worm[J]. IEEE Transactions on Dependable and Secure Computing，2007.