帶有節(jié)點異質性和免疫策略流行度的研究方法

張照文，范通讓

（石家莊鐵道大學 信息科學與技術學院，河北 石家莊 050043）

計算機網(wǎng)絡病毒的出現(xiàn)嚴重影響了網(wǎng)絡用戶的利益，也對網(wǎng)絡的發(fā)展產生了負面的影響。所以網(wǎng)絡病毒的防止技術的發(fā)展顯得尤為重要。由于互聯(lián)網(wǎng)和社會網(wǎng)絡的相似性，許多關于流行病的防治方法被借鑒用于網(wǎng)絡病毒的防治。例如當前的許多病毒免疫模型，病毒免疫策略等都或多或少受到流行病學的影響。同時，對于無標度網(wǎng)絡本身結構性質的研究，也為控制網(wǎng)絡病毒的傳播提供了理論基礎。但當前的許多網(wǎng)絡病毒的防治方法或是病毒免疫策略，都是通過網(wǎng)絡仿真的結果來評判免疫策略的優(yōu)劣性，忽略了免疫策略本身流行度問題，也沒有考慮到網(wǎng)絡節(jié)點的異質性。提出一種免疫策略研究方法，將免疫策略流行度和網(wǎng)絡節(jié)點異質性考慮在內。

1 相關研究

1.1 無標度網(wǎng)絡上的病毒免疫策略

人們對互聯(lián)網(wǎng)病毒的研究類似于社會網(wǎng)絡上的流行病研究，一般控制病毒的傳播主要采取兩個方面，隔離和免疫。由于采取免疫的策略不需要與網(wǎng)絡隔離，在獲得網(wǎng)絡資源的同時，使節(jié)點獲得對病毒的免疫能力，降低了被感染的風險。因而更具有研究價值。

1999年Fa loutsos等人［1］發(fā)現(xiàn)，互聯(lián)網(wǎng)表現(xiàn)出很強的冪律分布特點，節(jié)點的度有很大的波動性。具有冪律分布特點的網(wǎng)絡也稱為無標度網(wǎng)?；ヂ?lián)網(wǎng)和社會網(wǎng)絡都屬于無標度網(wǎng)絡，因此研究病毒在無標度網(wǎng)絡上的傳播及控制很有意義。

通過對無標度網(wǎng)絡病毒模型的研究，可更深刻地理解網(wǎng)絡病毒對網(wǎng)絡造成危害的現(xiàn)象，為網(wǎng)絡病毒防治技術提供足夠的理論基礎。文獻［2］指出，目前研究最為徹底、應用最為廣泛的傳染病模型是SIR，SIS，SIRS模型。當然，我們也不能忽略研究者對SIR等進行改進所作出的貢獻，例如，文獻［3］提出的改進的SIR計算機病毒傳播模型。本文所討論的免疫策略研究方法，也是立足于SIR模型之上的。

隨著對網(wǎng)絡病毒研究的深入，越來越多的病毒免疫策略被提出來。文獻［4］提出了隨機免疫策略：以等概率方式選取一定比例的節(jié)點進行保護。文獻［5］提出了熟人免疫策略：先在網(wǎng)絡中選取一定比例的節(jié)點進行免疫，然后再從這些節(jié)點的鄰居節(jié)點隨機的選擇節(jié)點進行免疫。文獻［6］提出了圖覆蓋免疫策略：將免疫過程視為一個圖覆蓋問題，即以“種子”節(jié)點為中心，免疫其周圍d步范圍內的最大度節(jié)點。該方法利用一定局部拓撲知識，取得明顯優(yōu)于鄰居免疫的效果。文獻［7］對以上幾種免疫策略進行了簡單論述和分析，指出了各種病毒免疫策略的優(yōu)缺點。以上的研究對本文的研究具有一定的指導意義。

1.2 創(chuàng)新事物在網(wǎng)絡上的傳播

人們是否會接受一種創(chuàng)新事物，很大程度上是受到其鄰居節(jié)點或朋友節(jié)點的影響。文獻［8］中論述了創(chuàng)新事物在網(wǎng)絡中的傳播過程，并且，指出了限制創(chuàng)新事物在網(wǎng)絡中傳播的障礙，即網(wǎng)絡中具有一定密度的“聚簇”的存在。同時作者還指出提高創(chuàng)新事物的流行度的方法：第一：保證其本身的相對同類產品的優(yōu)越性，使其更具有競爭力；第二：減低其在網(wǎng)絡中傳遞的門檻值，使其被更多網(wǎng)絡節(jié)點所接受。這樣就能夠突破“聚簇”的包圍，向更遠的地方傳播。同時指出，網(wǎng)絡中橋節(jié)點對創(chuàng)新數(shù)傳播的消極作用。

2 帶有節(jié)點異質性和免疫策略流行度的研究方法

無標度網(wǎng)絡上，病毒免疫策略的制定一直是當前的研究重點。選擇網(wǎng)絡中的那些節(jié)點注入抗病毒“疫苗”，對控制網(wǎng)絡病毒的傳播起著至關重要的作用。當前，一些主要的免疫策略，如隨機免疫，目標免疫等都具有很高的利用價值。但是對網(wǎng)絡節(jié)點異質性和免疫策略的流行度的研究還不夠。筆者提出一種新的免疫策略研究方法，將這兩個重要的因素考慮在內。

2.1 病毒免疫策略的流行度

流行度一般是指事物在社會中被認知，被接受的程度。知道的人越多其流行度也就越多。在本文中，將抗病毒“疫苗”和免疫策略本身在網(wǎng)絡中的接受程度，統(tǒng)稱為免疫策略流行度。由于免疫策略要在選擇的目標節(jié)點注入“疫苗”來阻止病毒的傳播，所以，目標節(jié)點集合中接受“疫苗”節(jié)點的數(shù)量對免疫策略的抗病毒效果影響無疑是巨大的。也就是本文提出的免疫策略流行度在抗病毒的過程中的重要性，也是該免疫策略是否切實可行的重要評價指標。

2.2 網(wǎng)絡中節(jié)點的異質性

在現(xiàn)實社會中，由于個人的年齡、健康程度、社會地位、財富的擁有量等的不同，造就了人的個體差異性。使得每個人在面對流行病的時候表現(xiàn)出不同的抵抗力，抵抗力弱的人容易被疾病感染，抵抗力強的人不容感染。同時，財富的擁有量使得其在面對疾病時有更多的選擇余地，例如他可以選擇代價較高，效果較好疾病“疫苗”；一旦被疾病感染，他也能獲得更有效地醫(yī)治。同樣的，在無標度網(wǎng)絡中，每個節(jié)點也是有差異的，因為它們在網(wǎng)絡中所處的位置不同，與之相連的節(jié)點和節(jié)點數(shù)目的不同等，造就節(jié)點在抗病毒感染，傳播創(chuàng)新事物上表現(xiàn)出不一致性。

2.3 免疫策略執(zhí)行步驟

為了驗證網(wǎng)絡節(jié)點異質性和免疫策略流行度，在控制網(wǎng)絡病毒傳播時的作用。本文構造一個仿真網(wǎng)絡來模擬病毒防治的過程?，F(xiàn)實網(wǎng)絡和仿真時采用的虛擬網(wǎng)絡是有差異的。那么，為了是免疫策略更具使用價值，就要在構建仿真網(wǎng)絡時，要使二者更為接近。需要說明的是，網(wǎng)絡節(jié)點異質性表現(xiàn)為兩個方面。第一：節(jié)點本身在不借助外界條件下對病毒的抵抗力；第二：節(jié)點在傳播創(chuàng)新事物時表象不同，在本文中則涉及到免疫策略的流行度問題。所以，關于網(wǎng)絡節(jié)點異質性問題會在不同的步驟中涉及到。具體的步驟如下：

第一步：構建SIR模型網(wǎng)絡。網(wǎng)絡中有三種節(jié)點：尚未感染且容易感染節(jié)點S和感染狀態(tài)節(jié)點I以及恢復節(jié)點R。主要任務是：初始化網(wǎng)絡規(guī)模，確定網(wǎng)絡冪率參數(shù)γ，網(wǎng)絡節(jié)點的總數(shù)N，以及S、I、R，三種類型節(jié)點數(shù)目。設置傳播參數(shù)，健康節(jié)點被感染的概率β，感染節(jié)點被治愈的概率δ。節(jié)點的異質性表現(xiàn)為兩個方面，每個節(jié)點被感染的概率是不同的；每個節(jié)點有I態(tài)轉到R態(tài)的概率是不同的。這里我們根據(jù)網(wǎng)絡節(jié)點度大小，來確定β和δ的大小。

第二步：在第一步所建立的網(wǎng)絡上進行仿真實驗。本步驟主要是研究，免疫策略在所有目標節(jié)點都注入“疫苗”的情況下（這里我們認為該免疫策略的流行度比例為100%），控制病毒傳播的效果。如果最后的實驗結果顯示，該免疫策略能夠產生很好的控制網(wǎng)絡病毒傳播的效果，則進行下一步；否則，就說明改免疫策略不能夠很好的抑制網(wǎng)絡病毒的傳播，沒要應用價值，那么則結束本次實驗。

第三步：考慮帶有免疫策略流行度的實驗。在本步驟中，主要是驗證免疫策略的流行度造成的影響。在初始條件下，即設定初始免疫策略的傳播的門檻值，網(wǎng)絡節(jié)點為接受免疫策略的所需付出代價的大小。這里我們同樣依據(jù)網(wǎng)絡節(jié)點度的大小來區(qū)別設定網(wǎng)絡節(jié)點付出代價的大小。當免疫策略門檻值小于節(jié)點能夠承受的代價時，網(wǎng)絡節(jié)點接受采取該免疫策略（注入其病毒“疫苗”），否則這拒絕該免疫策略。最后，查看免疫策略的流行度（目標節(jié)點集中接受該免疫策略的節(jié)點的百分比），查看當前流行度下的免疫策略的抗病毒效果。根據(jù)實驗結束時感染病毒節(jié)點占總節(jié)點數(shù)的比重。

第四步：通過修改免疫策略門檻值，提高“疫苗”質量等方法，來增加免疫策略的流行度。驗證節(jié)點異質性等因素對免疫策略流行度的影響和病毒免疫的效果。驗證增加免疫策略流行度的方法的作用。

第五步：結束實驗，總結網(wǎng)絡節(jié)點異質性和免疫策略流行度在病毒免疫中的作用。實驗步驟的簡易流程如圖1所示。

圖1 免疫策略方法流程圖

3 結束語

網(wǎng)絡病毒免疫技術為網(wǎng)絡病毒防治做出了突出貢獻。針對當前病毒免疫策略中，未提到的免疫策略流行度問題，以及網(wǎng)絡節(jié)點異質性因素，提出了一種新的免疫策略研究方法，將這兩個重要因素，加入到免疫策略制定的過程中。下一步工作主要是進一步細化實驗過程，通過一個具體的仿真網(wǎng)絡，具體網(wǎng)絡病毒免疫策略，來驗證本文提出的免疫策略研究方法。

［1］Faloutsos M，F(xiàn)aloutsos P，F(xiàn)aloutsos C.On power－law relationships of the Internet topology［J］.Computer Communicat ionRev iew，1999，29（4）：251－262.

［2］孫建華，李麗娟，李丁丁，羌衛(wèi)中.大規(guī)模網(wǎng)絡的病毒群體免疫模型［J］計算機應用，2007，27（3）：580－583.

［3］馮麗萍，王鴻斌，馮素琴.改進的SIR計算機病毒傳播模型［J］.計算機應用，2011，31（7）：1891－1893

［4］Pasto－Satorras R，Vespignani A.Immunization of Cornplex Networks［J］.Physical Review E，2002，65（3）：036104.1－036104.9.

［5］葛新，趙海，張君.基于熟人免疫的復雜網(wǎng)絡免疫策略［J］.計算機科學，2011，38（11）：83－86.

［6］Eehenique P，Gomez－Gardenes J，Moreno Y，et al.Distanced Covering Problem in Seale－Free Networks with Degree Correlation［J］.Physical Review E，2005，71（3）：035102.

［7］李向華，王欣，高超.復雜網(wǎng)絡免疫策略分析［J］.吉林大學學報，2013，51（3）：444－452

［8］大衛(wèi)·伊斯利，喬恩·克萊因伯格著，李曉明，王衛(wèi)紅，楊韞利譯著.網(wǎng)絡、群體與市場－揭示高度互聯(lián)世界的行為原理與效應機制［M］.北京：清華大學出版社，2011.