基于圖覆蓋的改進(jìn)復(fù)雜網(wǎng)絡(luò)免疫策略

肖詠

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

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

中圖分類號(hào)：TP391? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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ò)的拓?fù)浣Y(jié)構(gòu)小世界和無標(biāo)度特性，在很大程度上影響病毒的傳播行為，在現(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)中，發(fā)生少量病毒感染源即使病毒傳播速率非常低，也可以在網(wǎng)絡(luò)中廣泛蔓延開來[1-3]，故挖掘有效的免疫策略來控制病毒的爆發(fā)與傳播具有重大現(xiàn)實(shí)意義。針對(duì)免疫策略，人們做了大量研究，提出了以隨機(jī)免疫[4]，目標(biāo)免疫[5]，熟人免疫[6]，圖覆蓋免疫[7]為代表的一系列免疫策略。本文在圖覆蓋免疫的基礎(chǔ)上，結(jié)合模擬退火思想，提出了一種改進(jìn)的策略。通過在真實(shí)社團(tuán)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了本文策略具有更好的免疫效果。

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

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

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

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

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

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

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

2 改進(jìn)的免疫策略

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

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

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

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

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

⑵ 初始化溫度T，當(dāng)前選取節(jié)點(diǎn)vj為初始解。

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

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

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

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 實(shí)驗(yàn)方案

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

在交互式郵件傳播模型中，用戶分為健康、危險(xiǎn)、感染三種狀態(tài)，病毒的傳播主要與用戶檢查郵件的時(shí)間T和點(diǎn)擊病毒郵件的概率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é)點(diǎn)狀態(tài)，選取感染節(jié)點(diǎn)。

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

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

⑸ 更新下次查看郵箱時(shí)間。

⑹ 輸出每個(gè)時(shí)間步的感染節(jié)點(diǎn)數(shù)。

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)（References）：

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

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

[3] 李向華，王欣，高超.復(fù)雜網(wǎng)絡(luò)免疫策略分析[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），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.