朱義鑫，張鳳荔，王瑞錦，秦志光

?

時序網(wǎng)絡(luò)上的隨機游走免疫策略研究

朱義鑫1,2，張鳳荔2，王瑞錦2，秦志光2

(1. 新疆財經(jīng)大學(xué)計算機科學(xué)與工程學(xué)院 烏魯木齊 830012；2. 電子科技大學(xué)網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點實驗室 成都 610054)

針對傳統(tǒng)免疫模型在時序網(wǎng)絡(luò)中所面臨的難以收集、分析網(wǎng)絡(luò)拓撲信息的困境，提出了基于隨機游走機制的免疫策略，一定數(shù)量的免疫粒子被隨機地分配到網(wǎng)絡(luò)節(jié)點上，當該節(jié)點有邊激活時，免疫粒子就可以沿著激活邊游走到另一節(jié)點，獲得免疫粒子的節(jié)點獲得免疫能力，失去免疫粒子的節(jié)點轉(zhuǎn)換成非免疫的易感態(tài)。根據(jù)隨機游走者之間在轉(zhuǎn)移時是否相互影響，分別建立了非獨立隨機游走免疫模型和_獨立隨機游走免疫模型。在這兩種免疫模型中，免疫粒子傳播所需的網(wǎng)絡(luò)開銷受到事先給定的免疫粒子密度的限制。實驗表明，這兩種隨機游走免疫模型可以獲得比熟人免疫模型更好的免疫效果，而與目標免疫模型的比較結(jié)果取決于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的異質(zhì)性程度。

陣發(fā)性; 免疫策略; 隨機游走; 時序網(wǎng)絡(luò); 病毒傳播

新型網(wǎng)絡(luò)病毒不斷涌現(xiàn)，不僅威脅到網(wǎng)絡(luò)和主機的安全，也威脅著網(wǎng)絡(luò)用戶的信息安全。為了阻止或抑制病毒在網(wǎng)絡(luò)上的傳播，各種免疫策略被提出，如環(huán)狀免疫、目標免疫、熟人免疫、局部免疫及優(yōu)先刪邊免疫等[1-5]。這些免疫策略往往是選擇一些重要節(jié)點實施免疫，被免疫的節(jié)點既不會感染病毒也不會傳播病毒。熟人免疫策略有兩個針對時序網(wǎng)絡(luò)的改編版[6]：1) 權(quán)重協(xié)議，選擇與隨機選取的節(jié)點交互次數(shù)最多的節(jié)點加入免疫節(jié)點集；2) 最近協(xié)議，選擇與隨機選取的節(jié)點最后一次交互的節(jié)點加入免疫節(jié)點集。這些免疫策略實施的一個前提條件是事先收集、分析網(wǎng)絡(luò)拓撲信息，以確定免疫對象。在時序網(wǎng)絡(luò)中，節(jié)點間的連接是暫時的、反復(fù)的且具有陣發(fā)性的，即網(wǎng)絡(luò)結(jié)構(gòu)是不斷變化的，故只能根據(jù)部分的或是已知的時序網(wǎng)絡(luò)信息，對節(jié)點進行排名，以確定網(wǎng)絡(luò)節(jié)點的重要性。在大型網(wǎng)絡(luò)中，收集、分析含有時間維度的網(wǎng)絡(luò)信息，以確定免疫對象十分困難。因此，本文研究無需收集網(wǎng)絡(luò)拓撲信息，就可以快速實施的免疫策略。

1 多粒子隨機游走過程分析及分類

網(wǎng)絡(luò)的時間屬性會對擴散過程產(chǎn)生怎樣的影響，解決這一問題的第一種方法是在真實或人工合成的帶時間戳的事件序列數(shù)據(jù)上模擬隨機游走過程，并與所定義的空模型比較相應(yīng)的動態(tài)屬性[7-9]。第二種方法，研究分析在特定時序網(wǎng)絡(luò)模型上的隨機游走屬性[10-11]。

文獻[10, 12-13]提出將時序網(wǎng)絡(luò)建模成事件隨機序列，其中每個鏈接上的事件服從規(guī)定的間隔時間分布?？紤]個節(jié)點的一個無向網(wǎng)絡(luò)，由節(jié)點集和邊集組成，這種網(wǎng)絡(luò)往往被稱為聚合網(wǎng)絡(luò)，它被認為是時序網(wǎng)絡(luò)的聚合。用更新方式給每個邊分配一個隨機事件間隔時間，通過在聚合網(wǎng)絡(luò)上添加時間維度生成隨機時序網(wǎng)絡(luò)[10,12]。用表示的概率密度函數(shù)(probability density function, PDF)，并假設(shè)的均值有限。隨機游走者可以立刻從當前節(jié)點跳到一個鄰近節(jié)點，只要這兩個節(jié)點之間的鏈接出現(xiàn)。

在時序網(wǎng)絡(luò)中，根據(jù)隨機游走者沿著一個鏈接到達一個節(jié)點時，該節(jié)點的其他鏈接的事件間隔時間[14]是否重新初始化，隨機游走過程可以分為主動隨機游走和被動隨機游走兩種模式。1) 主動隨機游走過程被定義為一個更新過程，一個隨機游走者到達一個節(jié)點后，這個節(jié)點的所有鏈接的事件間隔時間重新初始化[10,12]。它的非馬爾科夫性是由于這樣一個事實：一個事件發(fā)生的概率取決于前面的事件。這種隨機過程可以用廣義主方程表示，并且可以獲得一些屬性的解析解，比如穩(wěn)態(tài)密度[12]和弛豫時間。2) 被動隨機游走模式，當一個游走者到達一個節(jié)點時，只初始化剛使用的鏈接的事件間隔時間。與主動隨機游走相比，被動隨機游走被認為是一種更自然的網(wǎng)絡(luò)擴散模式。因為在現(xiàn)實中，擴散的實體，如病毒，通常不會重新啟動一個活躍邊兩端的節(jié)點。被動隨機游走比主動隨機游走表現(xiàn)出更強的非馬爾科夫性，因為被動隨機游走者在某種程度上記住了過去的游走軌跡。

本文提出的隨機游走模型包含多個隨機游走者，每一個隨機游走者都是一個免疫粒子，它作為一種特殊的蠕蟲程序，可以轉(zhuǎn)移但不能增生，即它可以從一個節(jié)點轉(zhuǎn)移到另一節(jié)點，但不能增加免疫體數(shù)量。獲得免疫粒子的節(jié)點獲得免疫力，失去免疫粒子的節(jié)點轉(zhuǎn)換成非免疫的易感態(tài)。在多隨機游走者的模型中，無論是主動隨機游走模式還是被動隨機游走模式都存在一個同樣的問題，即隨機游走者之間在轉(zhuǎn)移時是否相互影響。任意一個免疫粒子在隨機游走中不受其他免疫粒子影響的模型被稱為獨立隨機游走免疫模型。免疫粒子在隨機游走中相互影響的模型被稱為非獨立隨機游走免疫模型。

如圖1所示，當一個邊被激活后，這條邊的兩個端節(jié)點中的免疫粒子便可以從一個端節(jié)點沿著這條活躍邊轉(zhuǎn)移到另一個端節(jié)點。圖1中的直線表示連接兩個節(jié)點的邊，直線上方的實心圓數(shù)目表示將要轉(zhuǎn)移的粒子數(shù)，直線上方的箭頭表示免疫粒子的轉(zhuǎn)移方向，以上解釋同樣適用于圖2和圖3。當端節(jié)點中含有的免疫粒子數(shù)不超過1個時，獨立與非獨立的隨機游走方式是相同的。圖1b中的雙方互換免疫粒子，看似是一個浪費網(wǎng)絡(luò)資源的無意義的數(shù)據(jù)傳輸，但它避免了通信雙方在傳輸數(shù)據(jù)前互換彼此狀態(tài)信息(含有的免疫粒子數(shù))所帶來的網(wǎng)絡(luò)開銷，同時也簡化了免疫粒子轉(zhuǎn)移時的傳輸協(xié)議。

當出現(xiàn)節(jié)點含有多個免疫粒子的情形時，這兩種隨機游走方式存在區(qū)別。由于獨立隨機游走的免疫粒子互不影響，當其所在節(jié)點有邊出現(xiàn)(激活)時，免疫粒子就會沿著邊轉(zhuǎn)移到另一節(jié)點，而無論其所在節(jié)點中是否有其他免疫粒子存在或轉(zhuǎn)移。因此，如圖2a所示，對于獨立隨機游走方式，當圖中的邊被激活后，該邊左側(cè)端節(jié)點中的所有免疫粒子都會向右側(cè)端節(jié)點轉(zhuǎn)移。而對于非獨立的隨機游走方式，如圖2b所示，當圖中的邊被激活時，該邊左側(cè)端節(jié)點中的多個免疫粒子只有一個會向右側(cè)端節(jié)點轉(zhuǎn)移，而其他免疫粒子或者選擇該節(jié)點同時激活的其他邊，或者等待該節(jié)點下一個活躍邊的到來。如圖3所示，時刻，節(jié)點有兩個活躍邊，每個活躍邊都有一個免疫粒子經(jīng)此轉(zhuǎn)移。時刻，節(jié)點有一個活躍邊，剩下的一個免疫粒子經(jīng)此活躍邊轉(zhuǎn)移至另一端的鄰節(jié)點。

2 隨機游走免疫模型

2.1 非獨立隨機游走免疫模型

算法1：非獨立隨機游走免疫模型算法

將每個選出的節(jié)點的資源置成(1,0)，其他節(jié)點的資源置成(0,0)；

end if

end if

end while

end for

end for

2.2 P_獨立隨機游走免疫模型

獨立隨機游走模型有一個很明顯的問題，如圖2a所示，一旦有多個游走者到達同一節(jié)點，則它們將永遠結(jié)伴而行，因為只要有邊激活，它們便一同沿邊轉(zhuǎn)移，這對免疫一定數(shù)量的節(jié)點非常不利。一個好的解決辦法是：當一個節(jié)點有邊激活時，該節(jié)點上的每個免疫粒子便以概率轉(zhuǎn)移，以概率1-不轉(zhuǎn)移。每個免疫粒子是否轉(zhuǎn)移與節(jié)點上是否有其他免疫粒子存在或轉(zhuǎn)移無關(guān)，稱這種獨立隨機游走免疫模型為_獨立隨機游走免疫模型。具體算法如下：

算法2：_獨立隨機游走免疫模型算法

將每個選出的節(jié)點的資源置成(1,0)，其他節(jié)點的資源置成(0,0)；

產(chǎn)生[0,1)之間的隨機數(shù)RandomNum；

if RandomNum

end if

end for

產(chǎn)生[0,1)之間的隨機數(shù)RandomNum；

if RandomNum

end if

end for

end while

end for

end for

3 實驗與分析

3.1 以BA網(wǎng)絡(luò)為底圖的實驗及分析

如圖4所示，實驗所使用的時序網(wǎng)絡(luò)底圖(聚合網(wǎng)絡(luò))為BA網(wǎng)絡(luò)，其節(jié)點總數(shù)，每個新加入節(jié)點連接5個已有節(jié)點，邊的激活間隔時間服從指數(shù)為2.1的冪律分布。對于隨機游走免疫模型而言，免疫粒子密度是指要設(shè)定的免疫粒子數(shù)與網(wǎng)絡(luò)節(jié)點總數(shù)的比值。對于目標免疫模型與熟人免疫模型而言，免疫粒子密度是指要選擇的免疫節(jié)點數(shù)與網(wǎng)絡(luò)節(jié)點總數(shù)的比值。實驗結(jié)果中的感染密度是指實驗結(jié)束時，網(wǎng)絡(luò)中處于感染態(tài)的節(jié)點數(shù)與網(wǎng)絡(luò)節(jié)點總數(shù)的比值。每次實驗的總時間步為5 000，對于每一個給定的免疫粒子密度值，圖中對應(yīng)的各模型的感染密度值均為100次重復(fù)實驗的均值。實驗結(jié)果的圖例中及分析論述中出現(xiàn)的URW、PRW分別表示非獨立隨機游走免疫模型和_獨立隨機游走免疫模型，其中。

實驗以隨機游走免疫模型的開始實施時間為0時刻，目標免疫和熟人免疫開始實施時間為時刻，將時間內(nèi)收集到的所有節(jié)點間的交互聚合成一個無重邊的無向網(wǎng)絡(luò)，就獲得了時序網(wǎng)絡(luò)在這個時間段內(nèi)的拓撲結(jié)構(gòu)信息。這個結(jié)構(gòu)信息是熟人免疫和目標免疫為選擇免疫節(jié)點而需要收集的網(wǎng)絡(luò)信息，可以用一個稱之為網(wǎng)絡(luò)拓撲信息量的定義來量化，它可以由下式定義：

隨機游走免疫模型與熟人免疫模型、目標免疫模型的免疫效果對比如圖4所示。圖例前綴AI表示熟人免疫，TI表示目標免疫，圖例中的數(shù)字表示熟人免疫模型和目標免疫模型實施免疫的開始時刻。由于熟人免疫(AI)結(jié)果的3條曲線基本重合，目標免疫(TI)結(jié)果的3條曲線非常接近，需要在圖中的曲線旁注明其對應(yīng)的免疫策略。在本實驗中，在時，網(wǎng)絡(luò)拓撲信息量為43.8%，在1 000時，網(wǎng)絡(luò)拓撲信息量增加至98.1%，熟人免疫模型和目標免疫模型分別以這兩個不同時刻作為免疫開始時間，所獲得的免疫效果并沒有明顯的區(qū)別，這個信息表明網(wǎng)絡(luò)拓撲信息量的持續(xù)增加并不能明顯地持續(xù)改善這兩種免疫策略的免疫效果。

如圖4所示，各免疫模型的免疫效果由好至差依次為URW免疫模型、PRW免疫模型、目標免疫模型、熟人免疫模型。與PRW免疫模型和目標免疫相比，URW免疫模型的免疫效果有明顯的優(yōu)勢，而前兩者又明顯優(yōu)于熟人免疫模型。PRW免疫模型與目標免疫模型相比較，隨著免疫粒子密度的增大，PRW免疫模型的優(yōu)勢逐漸顯現(xiàn)。

3.2 以AS網(wǎng)絡(luò)為底圖的實驗及分析

本實驗所使用的真實網(wǎng)絡(luò)數(shù)據(jù)是來自俄勒岡州立大學(xué)的路由器視角項目的在線數(shù)據(jù)。這個數(shù)據(jù)集包含了從1997年11月8日～2000年1月2日共785天中的733天的英特網(wǎng)自治域間的數(shù)據(jù)交換，所有數(shù)據(jù)交換關(guān)系聚合成一個AS網(wǎng)絡(luò)。以這個AS網(wǎng)絡(luò)作為時序網(wǎng)絡(luò)的底圖，只有底圖上存在的邊才有可能在某個時刻被激活，并發(fā)送數(shù)據(jù)。本次實驗仍設(shè)網(wǎng)絡(luò)邊激活間隔時間服從指數(shù)為2.1的冪律分布。測試前對網(wǎng)絡(luò)做預(yù)處理，剔除網(wǎng)絡(luò)中不連通的部分，只保留最大連通子圖，處理后的聚合網(wǎng)絡(luò)節(jié)點數(shù)=6 474，邊的總數(shù)為26 467，在這里簡記為AS20網(wǎng)絡(luò)。

如圖5所示，以AS20網(wǎng)絡(luò)為底圖的時序網(wǎng)絡(luò)上，各免疫模型的免疫效果由好至差依次為目標免疫模型(TI)、URW免疫模型、PRW免疫模型、熟人免疫模型(AI)。AS20網(wǎng)絡(luò)與前面所用的BA網(wǎng)絡(luò)相比較有一個顯著區(qū)別：網(wǎng)絡(luò)度分布的異質(zhì)性程度。BA網(wǎng)絡(luò)度分布是服從冪指數(shù)為3的冪律分布，而AS20網(wǎng)絡(luò)度分布的冪指數(shù)是小于1.5，即AS20網(wǎng)絡(luò)的拓撲結(jié)構(gòu)遠比BA網(wǎng)絡(luò)拓撲結(jié)構(gòu)的異質(zhì)性要強。意味著，與BA網(wǎng)絡(luò)相比，AS20網(wǎng)絡(luò)中的節(jié)點度集中在更少的節(jié)點上。因此，與以BA網(wǎng)絡(luò)為底圖的時序網(wǎng)絡(luò)上的相應(yīng)免疫模型的免疫效果(見圖4)相比較，目標免疫模型和熟人免疫模型都有顯著提高，尤其是目標免疫的免疫效果有了很大的飛躍，其免疫粒子密度臨界值<0.01，成為免疫效果最好的模型。但目標免疫必須要能夠搜集到足夠的信息，并匯總分析以產(chǎn)生全局信息，只有這樣才能對節(jié)點排序、免疫。因此，在大的時序網(wǎng)絡(luò)上比較免疫效果，目標免疫只是作為一個標桿，其難以實施。另一方面，即便在拓撲結(jié)構(gòu)的異質(zhì)性很強的AS20網(wǎng)絡(luò)上，URW免疫模型和PRW免疫模型的免疫效果也是優(yōu)于熟人免疫模型的免疫效果，它們的免疫粒子密度臨界值分別小于或等于0.03和0.05，而熟人免疫模型的免疫粒子密度臨界值是大于這兩個值的(超出了圖5的橫坐標范圍)。

與以BA網(wǎng)絡(luò)為底圖的時序網(wǎng)絡(luò)上的各模型免疫效果比較，不僅是目標免疫模型和熟人免疫模型的免疫效果有顯著提高，URW免疫模型和PRW免疫模型的免疫效果也有較大的提高。在以AS20網(wǎng)絡(luò)為底圖的時序網(wǎng)絡(luò)上，URW免疫模型和PRW免疫模型在免疫更少比例的節(jié)點基礎(chǔ)上，獲得了更好的免疫效果。其原因仍然是與BA網(wǎng)絡(luò)相比，AS20網(wǎng)絡(luò)的拓撲結(jié)構(gòu)異質(zhì)性更強。對于拓撲結(jié)構(gòu)異質(zhì)性越強的網(wǎng)絡(luò)，就會有越少的重要性更強的節(jié)點?；陔S機游走擴散機制的免疫粒子更傾向于游走到這些更重要的節(jié)點上，所以在以AS20網(wǎng)絡(luò)為底圖的時序網(wǎng)絡(luò)上，通過免疫這些少量的重要節(jié)點，就可以獲得好的免疫效果。

4 結(jié)束語

本文提出了基于隨機游走機制的免疫模型，包括非獨立隨機游走免疫模型和_獨立隨機游走免疫模型，這兩種免疫模型的免疫節(jié)點密度都不超過給定的免疫粒子密度。通過實驗，發(fā)現(xiàn)隨機游走免疫模型的免疫效果優(yōu)于熟人免疫模型，與目標免疫模型的比較結(jié)果取決于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的異質(zhì)性程度。隨機游走免疫模型具有無需搜集、分析網(wǎng)絡(luò)拓撲信息，以及可以隨時部署實施的優(yōu)勢。隨機游走免疫模型需要考量免疫粒子傳播所需要的網(wǎng)絡(luò)開銷，而這一網(wǎng)絡(luò)開銷可以直接通過事先設(shè)定的免疫粒子密度等模型參數(shù)得以控制。

本文研究工作還得到了網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點實驗室開放課題(NDSMS201603)、新疆維吾爾自治區(qū)高?？蒲杏媱澘茖W(xué)研究重點項目(XJEDU2016I036)以及新疆財經(jīng)大學(xué)博士啟動基金(2016BS008)的資助，在此表示感謝。

[1] MULLER J, SCHONFISCH B, KIRKILIONIS M. Ring vaccination[J]. J Math Biol, 2000, 41(2): 143-171.

[2] PASTOR-SATORRAS R, VESPIGNANI A. Immunization of complex networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2002, 65(3 Pt 2A): 036104.

[3] COHEN R, HAVLIN S, BEN-AVRAHAM D. Efficient immunization strategies for computer networks and populations[J]. Physical Review Letters, 2003, 91(24): 247901.

[4] HOLME P. Efficient local strategies for vaccination and network attack[J]. EPL (Europhysics Letters), 2004, 68(6): 908.

[5] CHEN Y, PAUL G, HAVLIN S, et al. Finding a better immunization strategy[J]. Physical Review Letters, 2008, 101(5): 058701.

[6] LEE S, ROCHA L E, LILJEROS F, et al. Exploiting temporal network structures of human interaction to effectively immunize populations[J]. PloS One, 2012, 7(5): e36439.

[7] STARNINI M, BARONCHELLI A, BARRAT A, et al. Random walks on temporal networks[J]. Physical Review E, 2012, 85(5): 056115.

[8] RIBEIRO B, PERRA N, BARONCHELLI A. Quantifying the effect of temporal resolution on time-varying networks[J]. Scientific Reports, 2013, 3(10): 3006.

[9] ROCHA L E C, MASUDA N. Random walk centrality for temporal networks[J]. New Journal of Physics, 2014, 16: 063023.

[10] HOFFMANN T, PORTER M A, LAMBIOTTE R. Generalized master equations for non-Poisson dynamics on networks[J]. Physical Review E, 2012, 86(4): 046102.

[11] SPEIDEL L, LAMBIOTTE R, AIHARA K, et al. Steady state and mean recurrence time for random walks on stochastic temporal networks[J]. Physical Review E, 2015, 91: 012806.

[12] HOFFMANN T, PORTER M A, LAMBIOTTE R. Random walks on stochastic temporal networks[M]//HOLME P, SARAMAKI J. Temporal Networks, Berlin: Springer, 2013: 295-313.

[13] ROCHA L E, BLONDEL V D. Bursts of vertex activation and epidemics in evolving networks[J]. PLoS Computational Biology, 2013, 9(3): e1002974.

[14] LAMBIOTTE R, TABOURIER L, DELVENNE J-C. Burstiness and spreading on temporal networks[J]. European Physical Journal B, 2013, 86(7): 1-4.

編 輯 蔣 曉

Reseach on Immunization Strategy Based on Random Walk Mechanism in Temporal Networks

ZHU Yi-xin1,2, ZHANG Feng-li2, WANG Rui-jin2, and QIN Zhi-guang2

(1. School of Computer Science and Engineering, Xinjiang University of Finance and Economics Urumqi 830012; 2. Network and Data Security key Laboratory of Sichuan Province, University of Electronic Science and Technology of China Chengdu 610054)

For the problems of traditional immune models arising in collectingand analyzing network topology information in temporal networks, an immune strategy based on random walk mechanism is put forward and itcan be implemented withoutcollectingnetwork topology information. A certain number of immune particles were randomly assigned to the network nodes.When a nodewith immune particles has one or more activated links,the immune particles on the node will walk to another node along anactivated link of the node.The nodes with immune particlesacquire the immunity,but thenodes losingimmune particleswill betransformed into the susceptible state. Considering whether the random walkers exert impact upon each other when they move, the dependent random walk immune model and the P_independent random walk immune model are established,respectively, in which the network transmission overhead of the immune particle is limited by a given immune particle density. Experiments show the two random walk immune models are characterized by their better immune effects with lower immune particle density and the network overhead when compared with acquaintances immune model. In addition, the comparative result with the target immune model depends on heterogeneity of network topology.

burstiness; immunization strategy; random walk; temporal network; virus propagation

TP393.08

A

10.3969/j.issn.1001-0548.2017.01.015

2015-03-11；

2016-06-10

國家自然科學(xué)基金(61440047)；國家自然科學(xué)基金青年項目(61502087)

朱義鑫(1974-)，男，博士，主要從事計算機網(wǎng)絡(luò)安全、復(fù)雜網(wǎng)絡(luò)傳播方面的研究.