基于多粒子隨機(jī)游走免疫算法

盧彬煒，閆光輝?，羅 浩，楊 波，張 磊，王 瓊

1.蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅蘭州 730070；

2.國網(wǎng)甘肅省電力公司信息通信公司，甘肅蘭州730070

0 引言

傳播廣泛存在于自然界及人類社會(huì)活動(dòng)中，分析復(fù)雜網(wǎng)絡(luò)上的傳播機(jī)理、設(shè)計(jì)高效免疫策略并有效調(diào)控網(wǎng)絡(luò)傳播是復(fù)雜網(wǎng)絡(luò)研究與應(yīng)用的經(jīng)典問題,其中研究如何控制疾病與謠言傳播爆發(fā)的免疫策略一直是網(wǎng)絡(luò)傳播的熱點(diǎn)課題之一。鑒于免疫資源有限，無法免疫網(wǎng)絡(luò)中所有節(jié)點(diǎn)，只能選擇其中部分進(jìn)行免疫，為此尋找一種高效的免疫策略具有重要的研究意義。

傳統(tǒng)免疫方式包括隨機(jī)免疫[1](random immunization,RI)，目標(biāo)免疫[2](targeted immunization,TI)以及熟人免疫[3](acquaintance immunization,AI)，學(xué)者們所研究的方法多是以上經(jīng)典策略的結(jié)合與改進(jìn)[4～6]。研究表明，具有明顯社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)中，免疫社團(tuán)間的橋節(jié)點(diǎn)通常比免疫度值大的節(jié)點(diǎn)更能夠有效地限制網(wǎng)絡(luò)傳播范圍[7]，而此類免疫方式的時(shí)間復(fù)雜度較高，為O(n3),需要較大的時(shí)間開銷，且未綜合考慮節(jié)點(diǎn)度值以及所處網(wǎng)絡(luò)位置對(duì)網(wǎng)絡(luò)傳播的貢獻(xiàn)能力，不適合在大規(guī)模網(wǎng)絡(luò)中使用。

綜上所述，傳統(tǒng)或是改進(jìn)研究多是將節(jié)點(diǎn)度值與節(jié)點(diǎn)位置信息分別考慮，且基于介數(shù)中心性的算法存在復(fù)雜度高等問題。因此，本文提出基于多粒子隨機(jī)游走免疫算法用于無向無權(quán)網(wǎng)絡(luò)免疫的研究，借鑒文獻(xiàn)[8]隨機(jī)游走免疫粒子在網(wǎng)絡(luò)節(jié)點(diǎn)間游走免疫的思想，逆向考慮將節(jié)點(diǎn)間隨機(jī)游走的粒子作為攜帶消息或是病毒的載體，獲取一組對(duì)網(wǎng)絡(luò)傳播貢獻(xiàn)大的節(jié)點(diǎn)，通過免疫此類節(jié)點(diǎn)進(jìn)而控制網(wǎng)絡(luò)傳播。

1 本文算法

本文所做工作主要包含兩部分內(nèi)容：1）節(jié)點(diǎn)篩選工作，根據(jù)所提隨機(jī)游走算法對(duì)網(wǎng)絡(luò)進(jìn)行多粒子游走，流量排序后按比例獲取流量較大的節(jié)點(diǎn)；2）傳播驗(yàn)證工作，根據(jù)游走所篩選的節(jié)點(diǎn)進(jìn)行SI(suspected-infected)與SIR(suspected-infectedrecovered/removed)傳播實(shí)驗(yàn)，通過與多種其他免疫方法對(duì)比，論證本文方法有效性與可行性。

本小節(jié)主要介紹多粒子隨機(jī)游走免疫算法內(nèi)容。

1.1 算法思想

本文假設(shè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)存在若干數(shù)目的粒子，僅考慮一個(gè)節(jié)點(diǎn)內(nèi)的粒子（它可以是一條消息或是潛在的病毒，起源于網(wǎng)絡(luò)傳染源節(jié)點(diǎn)），粒子在連通的網(wǎng)絡(luò)中隨機(jī)游走。對(duì)于無向無權(quán)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的連邊代表節(jié)點(diǎn)間的聯(lián)系，在傳播游走的每一個(gè)迭代步中，粒子從當(dāng)前節(jié)點(diǎn)移動(dòng)至任一鄰居節(jié)點(diǎn)，屬于等概率事件。而在加權(quán)網(wǎng)絡(luò)中，對(duì)連邊的賦權(quán)可能代表了節(jié)點(diǎn)間的聯(lián)系強(qiáng)度或是親密程度，游走的依據(jù)需充分考慮節(jié)點(diǎn)間的聯(lián)系程度或是親密程度。因此，粒子游走概率亦受節(jié)點(diǎn)間連邊權(quán)值影響，通過某一連邊的概率為

其中，wi,j表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的連邊權(quán)值，nbr(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)。

基于以上描述，本文所選的無向無權(quán)網(wǎng)絡(luò)可作為加權(quán)網(wǎng)絡(luò)的一種特殊情況，即所有連邊賦權(quán)為1?？紤]到每一步的游走概率只與粒子所在節(jié)點(diǎn)度(加權(quán)網(wǎng)絡(luò)中還需考慮邊權(quán)大小)有關(guān)，并不會(huì)基于過去或當(dāng)前的表現(xiàn)，且無法預(yù)知下一步的動(dòng)態(tài)和方向，接近于布朗運(yùn)動(dòng)[9]，根據(jù)其隨機(jī)性命名為多粒子隨機(jī)游走免疫算法(multi-particle random walk immunization,RWI)。

1.2 算法描述

定義1[10]對(duì)于網(wǎng)絡(luò)G(V,E)(簡(jiǎn)記為G)，令V=V(G)表示網(wǎng)絡(luò)G的節(jié)點(diǎn)集合，E=E(G)表示網(wǎng)絡(luò)G的連邊集合。

本文若無特別說明，所使用的網(wǎng)絡(luò)均為無向無權(quán)網(wǎng)絡(luò)。

對(duì)于網(wǎng)絡(luò)G(V,E)，節(jié)點(diǎn)總數(shù)為n，單個(gè)節(jié)點(diǎn)生成的游走序列數(shù)為R?，F(xiàn)僅考慮單粒子游走情況，設(shè)f(t)為該粒子在進(jìn)行t步游走后的途經(jīng)節(jié)點(diǎn)序列，即f(t)=[N1,N2,…,Nt]，則實(shí)際游走步驟如下：

步驟1給定初始節(jié)點(diǎn)N0，即粒子所在初始節(jié)點(diǎn)；

步驟2設(shè)定最終游走迭代步數(shù)T，t為當(dāng)前迭代步數(shù)，t=1；

步驟3遍歷粒子所在節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)度數(shù)為KNi，粒子隨機(jī)游走至下一鄰居節(jié)點(diǎn)Nt+1，概率為，令t=t+1；若當(dāng)前節(jié)點(diǎn)無鄰居節(jié)點(diǎn)，游走停止，流量記為0；

步驟4若t＜T，進(jìn)行步驟3；反之，游走結(jié)束；

步驟5流量統(tǒng)計(jì)：若序列中含有與該粒子起始節(jié)點(diǎn)相同的節(jié)點(diǎn)，移除；之后對(duì)所有序列節(jié)點(diǎn)數(shù)目累加求和，由高到低輸出節(jié)點(diǎn)列表L(R,T)。

根據(jù)上述步驟，算法中完成單節(jié)點(diǎn)內(nèi)單個(gè)隨機(jī)粒子的游走共計(jì)使用了兩次循環(huán)嵌套，粒子數(shù)目為R，游走生成的列表長度為T，且每個(gè)游走步驟需遍歷當(dāng)前節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)與網(wǎng)絡(luò)的平均度相關(guān)。在算法運(yùn)行過程中，R、T和三類參數(shù)均與網(wǎng)絡(luò)相關(guān)，設(shè)置為常數(shù)。設(shè)s為單節(jié)點(diǎn)內(nèi)粒子數(shù)與游走深度及網(wǎng)絡(luò)平均度的乘積，即

由以上描述可知s為常數(shù)。而網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模為n，因此該算法時(shí)間復(fù)雜度為O(sn)，數(shù)據(jù)存儲(chǔ)的空間復(fù)雜度僅與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目相關(guān)，即為O(n)。

1.3 模型分析

根據(jù)游走規(guī)則，假定t時(shí)間步i節(jié)點(diǎn)的粒子數(shù)目為

那么，經(jīng)過T時(shí)間步后的游走，可得出節(jié)點(diǎn)i的途經(jīng)粒子總數(shù)

事實(shí)上，（3）式作為對(duì)單節(jié)點(diǎn)某時(shí)刻的粒子數(shù)目的計(jì)算，可展開為如下轉(zhuǎn)移式

1.4 理論推導(dǎo)

以網(wǎng)絡(luò)鄰接矩陣表示網(wǎng)絡(luò)中各節(jié)點(diǎn)的連邊關(guān)系，對(duì)于無向加權(quán)網(wǎng)絡(luò)可用0表示兩節(jié)點(diǎn)間無鄰邊存在，用1表示兩節(jié)點(diǎn)間存在鄰邊。那么，網(wǎng)絡(luò)鄰接矩陣可表示如下

節(jié)點(diǎn)間粒子的游走概率受節(jié)點(diǎn)的鄰居數(shù)量影響，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的粒子遷入概率，其轉(zhuǎn)移矩陣可表示如下

假設(shè)網(wǎng)絡(luò)初始狀態(tài)下每個(gè)節(jié)點(diǎn)中包含粒子初始數(shù)目均為R，根據(jù)上述游走算法描述，經(jīng)過一步游走后的網(wǎng)絡(luò)中粒子數(shù)量分布為

經(jīng)過T步迭代游走后的粒子數(shù)量分布為

而本文算法考慮每一個(gè)節(jié)點(diǎn)的歷史途經(jīng)粒子流量，則需要把每一步的流量分布進(jìn)行累加，即為（4）式。

P的計(jì)算與PageRank原理相似，是一種類馬爾可夫過程，Google公司的PageRank算法[11]沿用隨機(jī)游走思想，將游走的過程變?yōu)楦怕蕚鞑サ倪^程，最后統(tǒng)計(jì)各節(jié)點(diǎn)的概率，但該算法最終會(huì)受網(wǎng)絡(luò)出入度值的影響，形成某些無出度節(jié)點(diǎn)的“黑洞”，最終退化為節(jié)點(diǎn)度排序。本文所提的概率轉(zhuǎn)移矩陣形式與PageRank算法的概率轉(zhuǎn)移矩陣計(jì)算方式不同，PageRank表示在網(wǎng)絡(luò)中的頁面跳出關(guān)系，其統(tǒng)計(jì)的是最終的頁面排序；而本文隨機(jī)游走算法為統(tǒng)計(jì)粒子遷入概率，將每一個(gè)時(shí)間步的歷史流量進(jìn)行累加，考慮的是過程的流量。在游走過程中對(duì)每一步游走添加前提限制，考慮到現(xiàn)實(shí)傳播受出度影響，因此算法步驟3對(duì)無出度或是無下一鄰居節(jié)點(diǎn)做停止游走處理，流量記作0。

通過多個(gè)時(shí)間步的迭代，由（3）式可知，某個(gè)節(jié)點(diǎn)的粒子流量與兩部分因素有關(guān)：一是受該節(jié)點(diǎn)度值影響，節(jié)點(diǎn)的度值越大，鄰居節(jié)點(diǎn)越多，那么能得到鄰居節(jié)點(diǎn)提供流量的機(jī)會(huì)越多；二是與該節(jié)點(diǎn)所處位置有關(guān)，如果該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度值不大，但該節(jié)點(diǎn)是橋節(jié)點(diǎn)，它也能獲得較大的流量。由此推知當(dāng)選取一定比例的節(jié)點(diǎn)進(jìn)行免疫時(shí)，通過隨機(jī)游走選取的節(jié)點(diǎn)集合中必然會(huì)有一部分與目標(biāo)免疫相似，具體在實(shí)驗(yàn)部分詳述。

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

2.1 數(shù)據(jù)集準(zhǔn)備

為了驗(yàn)證本文算法的有效性，實(shí)驗(yàn)選取了真實(shí)網(wǎng)絡(luò)共計(jì)8個(gè)不同數(shù)據(jù)集，包括不同尺度的具有無標(biāo)度特性[12～15]與小世界特性[16～19]的網(wǎng)絡(luò)。表1給出了這8個(gè)數(shù)據(jù)集的參數(shù)及描述。在本文中，以|V|表示網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)目，|E|表示網(wǎng)絡(luò)中連邊總數(shù)目，K表示網(wǎng)絡(luò)節(jié)點(diǎn)平均度。

表1 數(shù)據(jù)集參數(shù)及相關(guān)描述Table 1 Datasets par ameters and r elated descr iption

2.2 實(shí)驗(yàn)設(shè)計(jì)

文獻(xiàn)[20]的結(jié)果表明，疾病與謠言傳播在無標(biāo)度網(wǎng)絡(luò)中的速度快且范圍更廣；在小世界特性的網(wǎng)絡(luò)中，平均度越大，則傳播峰值越高。由此根據(jù)不同的網(wǎng)絡(luò)特征使用SIR與SI傳播模型，本文主要選取五個(gè)已有的網(wǎng)絡(luò)免疫策略進(jìn)行橫向?qū)Ρ葋碓u(píng)估本文算法性能。

定義2在SIR與SI傳播模型中，β表示易感節(jié)點(diǎn)與相鄰感染節(jié)點(diǎn)接觸后的感染概率，γ表示易感染節(jié)點(diǎn)的恢復(fù)概率，在SIR傳播模型中，將有效傳播率定義為λ，且λ=另外，λc定義為網(wǎng)絡(luò)疾病暴發(fā)閾值，當(dāng)λ＞λc，傳播現(xiàn)象將在網(wǎng)絡(luò)中爆發(fā)并在一定時(shí)間步后達(dá)到峰值。

為了便于觀察結(jié)果的差異性，在無標(biāo)度網(wǎng)絡(luò)中采用SI傳播實(shí)驗(yàn)，而在小世界網(wǎng)絡(luò)中采用SIR傳播實(shí)驗(yàn)，并且SIR傳播實(shí)驗(yàn)采用了不同的有效傳播率。實(shí)驗(yàn)中對(duì)不同網(wǎng)絡(luò)設(shè)置了不同的傳播率β、恢復(fù)率γ和傳播迭代步數(shù)。表2為實(shí)驗(yàn)參數(shù)設(shè)置。

表2 傳播實(shí)驗(yàn)參數(shù)設(shè)置Table 2 Spread experiments parameter settings

本文實(shí)驗(yàn)將恢復(fù)率定為0.05，使用的有效傳播率區(qū)間λ?[0.5,4]。

不失一般性，本文實(shí)驗(yàn)次數(shù)設(shè)置為500次，網(wǎng)絡(luò)中節(jié)點(diǎn)感染比例為每一次實(shí)驗(yàn)中最大感染率值的平均值。每次實(shí)驗(yàn)都選取固定比例(網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的5%)的節(jié)點(diǎn)作為網(wǎng)絡(luò)傳播的傳染源，且傳染源節(jié)點(diǎn)均隨機(jī)生成，每次傳播實(shí)驗(yàn)感染源節(jié)點(diǎn)都不同，能夠保證在不同情況下傳播爆發(fā)對(duì)網(wǎng)絡(luò)采取免疫措施的有效性。

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

與本文的RWI作比對(duì)的免疫策略有:熟人免疫(AI)[3]、目標(biāo)免疫中的度中心(degree centrality)免疫TI_DC以及介數(shù)中心(betweenness centrality)免疫TI_BC[2]、PageRank篩選節(jié)點(diǎn)的免疫方式(PRI)以及文獻(xiàn)[8]中的免疫粒子非獨(dú)立隨機(jī)游走免疫方法(dependent random walk particle immunization,DRWPI)。鑒于現(xiàn)實(shí)情況下免疫資源有限，且在實(shí)驗(yàn)準(zhǔn)備過程中發(fā)現(xiàn)，在多數(shù)網(wǎng)絡(luò)數(shù)據(jù)集中，當(dāng)免疫率達(dá)到0.20時(shí)，網(wǎng)絡(luò)傳播范圍已低于20%，甚至在有些情況下網(wǎng)絡(luò)傳播范圍低于10%，控制傳播效果明顯，且已無明顯的邊際增益效果，因此本實(shí)驗(yàn)選取的免疫率均介于0.01至0.23之間，步長0.02。

圖1給出了不同的免疫策略在無標(biāo)度網(wǎng)絡(luò)模型中的傳播實(shí)驗(yàn)結(jié)果。多數(shù)網(wǎng)絡(luò)中，當(dāng)免疫率低于0.13時(shí)，RWI算法與TI_BC和TI_DC相比優(yōu)勢(shì)較小，當(dāng)免疫率在0.13～0.23之間時(shí)，RWI算法要優(yōu)于TI_BC和TI_DC。通過對(duì)感染率最大值的計(jì)算，RWI算法在4個(gè)無標(biāo)度網(wǎng)絡(luò)均優(yōu)于目標(biāo)免疫，顯示出了更好的效果。

通過實(shí)驗(yàn)結(jié)果的對(duì)比，在具有無標(biāo)度網(wǎng)絡(luò)特性的數(shù)據(jù)集中，當(dāng)免疫節(jié)點(diǎn)率較低時(shí)，RWI與目標(biāo)免疫中的TI_DC和TI_BC的差異不明顯，這是因?yàn)樵诘兔庖呗氏?，依?jù)（3）式可以推測(cè)網(wǎng)絡(luò)拓?fù)涮卣?即節(jié)點(diǎn)的度值)依然對(duì)網(wǎng)絡(luò)免疫策略起決定作用，通過對(duì)比三種方法RWI、TI_DC和TI_BC的節(jié)點(diǎn)集，發(fā)現(xiàn)他們節(jié)點(diǎn)的重復(fù)程度很高，超過90%的節(jié)點(diǎn)是相同的，因此曲線幾乎是重合的。而當(dāng)免疫率較高時(shí)，三種方法在選取節(jié)點(diǎn)上體現(xiàn)了較大的差異性，說明此時(shí)隨機(jī)游走能夠辨識(shí)出更多易受傳播影響的節(jié)點(diǎn)，此類節(jié)點(diǎn)在網(wǎng)絡(luò)中雖沒有較大的度值，但他們卻處在易受影響的關(guān)鍵位置，比如連接不同社團(tuán)的橋節(jié)點(diǎn)(這類節(jié)點(diǎn)往往度值較小，不易被目標(biāo)免疫發(fā)現(xiàn))，亦或是在度相同的情況下，選取了更為重要的樞紐節(jié)點(diǎn)，這一類節(jié)點(diǎn)的鄰居也許是度值較大，或是流量更大的節(jié)點(diǎn)。通過對(duì)這部分節(jié)點(diǎn)的免疫，能夠更好地限制疾病向其他社團(tuán)擴(kuò)散并控制傳播范圍?？蓮膱D1發(fā)現(xiàn)，本文所借鑒的DRWPI方法在低免疫率條件下(免疫率低于0.20)，控制傳播的效果遠(yuǎn)不及目標(biāo)免疫，這是由于DRWPI算法中的免疫粒子只能使節(jié)點(diǎn)具有暫態(tài)免疫效果，當(dāng)粒子游走至其他節(jié)點(diǎn)時(shí)，當(dāng)前節(jié)點(diǎn)將處于易感態(tài)，DRWPI方法仍不能有效控制網(wǎng)絡(luò)的傳播范圍。

圖1 兩種不同無標(biāo)度網(wǎng)絡(luò)在不同免疫率下的傳播實(shí)驗(yàn)Fig.1 Propagation experiment of two different scale-free networks in different immune rates

圖2為當(dāng)免疫率為0.11時(shí)不同有效傳播率下的傳播實(shí)驗(yàn)在具有小世界特性網(wǎng)絡(luò)中的效果對(duì)比。與無標(biāo)度網(wǎng)絡(luò)相同，RWI算法均在控制網(wǎng)絡(luò)傳播的作用上比TI_BC和TI_DC有所提升。隨著網(wǎng)絡(luò)有效傳播率的提升，傳播范圍逐步提升，從圖2可以看出，DRWPI在較小的有效傳播率下免疫的效果比其他免疫策略都要好，這是由于較低的有效傳播率對(duì)節(jié)點(diǎn)的感染能力較弱，網(wǎng)絡(luò)中移動(dòng)的免疫粒子對(duì)傳染有更好更快的控制能力。而隨著傳播率提升，網(wǎng)絡(luò)中節(jié)點(diǎn)受感染概率增大，感染態(tài)(infected)節(jié)點(diǎn)數(shù)目會(huì)在極短的時(shí)間步內(nèi)達(dá)到峰值，使得DRWPI方法中的免疫粒子無法快速響應(yīng)并控制傳播，DRWPI方法成了除AI之外最差的。從圖2曲線走勢(shì)也看出，隨著傳播率提升，RWI算法相比其他算法的優(yōu)勢(shì)更加明顯?？梢?，RWI算法在高傳播率下具有更好的免疫能力。

對(duì)比RWI和目標(biāo)免疫選取的免疫節(jié)點(diǎn)集，二者識(shí)別出的節(jié)點(diǎn)排序有較大差異。從圖1和圖2可知小世界網(wǎng)絡(luò)不同于無標(biāo)度網(wǎng)絡(luò)的度分布，小世界網(wǎng)絡(luò)各節(jié)點(diǎn)的度值更加接近，由于差值較小，以度值為主要依據(jù)對(duì)節(jié)點(diǎn)的評(píng)價(jià)作用也隨之降低；小世界網(wǎng)絡(luò)具有較高的平均聚集系數(shù)，由于具有明顯的社團(tuán)聚集現(xiàn)象，因此會(huì)出現(xiàn)更多連接不同社團(tuán)的橋節(jié)點(diǎn)和樞紐節(jié)點(diǎn)。通過分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可知此類節(jié)點(diǎn)不易于發(fā)現(xiàn)，那么這種依賴于計(jì)算機(jī)算力的模擬仿真方式通過游走實(shí)驗(yàn)更容易篩選出網(wǎng)絡(luò)中的易受影響節(jié)點(diǎn)。

圖2 在兩種小世界網(wǎng)絡(luò)中，當(dāng)免疫率為0.11時(shí)，不同有效傳播率下的傳播實(shí)驗(yàn)Fig.2 Propagation experiment of two different small world networks with different effective transmission when immune rate was 0.11

圖3為在有效傳播率λ=3.0時(shí)，不同策略在enron-email網(wǎng)絡(luò)與ca-hepth網(wǎng)絡(luò)的傳播比率。其中，免疫率分別為0.07和0.15。對(duì)比圖2發(fā)現(xiàn)，RWI與目標(biāo)免疫均能有效控制網(wǎng)絡(luò)傳播，不僅能夠顯著降低節(jié)點(diǎn)的感染數(shù)目，還能夠有效減緩傳播速度。相比而言，RWI則體現(xiàn)出更好的免疫效果。圖3（a）和（b）是無標(biāo)度網(wǎng)絡(luò)下的SI傳播，在傳播一定時(shí)間步后，達(dá)到一個(gè)穩(wěn)態(tài)，曲線越低說明最終傳播范圍越低，免疫效果越好。圖3（a）和（b）中RWI的曲線是最低的，所以它的免疫效果是最好的。圖3（c）和（d）是SIR傳播，峰值越大說明傳播范圍越廣，從中我們也可看出RWI的免疫效果較好。通過對(duì)網(wǎng)絡(luò)選取適量的節(jié)點(diǎn)采取免疫措施盡管不可能完全阻止病毒或者謠言的暴發(fā)，但從圖3中仍可知曉，免疫策略使傳播速度減緩、傳播范圍縮小，對(duì)控制網(wǎng)絡(luò)傳播很重要。

圖3 真實(shí)網(wǎng)絡(luò)中不同免疫率的傳播結(jié)果Fig.3 The results of propagation experiment in different immune rates in real networks

上述兩種不同特性的網(wǎng)絡(luò)進(jìn)行傳播免疫實(shí)驗(yàn)結(jié)果對(duì)比表明，RWI算法在具有小世界特性的網(wǎng)絡(luò)數(shù)據(jù)集中的免疫效果要顯著優(yōu)于無標(biāo)度網(wǎng)絡(luò)。這是由于無標(biāo)度網(wǎng)絡(luò)的結(jié)構(gòu)所致，其網(wǎng)絡(luò)度值更集中于少部分節(jié)點(diǎn)，度分布的差異性對(duì)隨機(jī)游走算法的影響更明顯，因此篩選出的節(jié)點(diǎn)與目標(biāo)免疫方法的節(jié)點(diǎn)高度一致。而在小世界特性的網(wǎng)絡(luò)中，它們分化出不同的社區(qū)，連接社區(qū)間的節(jié)點(diǎn)度值差異不明顯，通過RWI在真實(shí)網(wǎng)絡(luò)中更容易篩選出社區(qū)邊緣節(jié)點(diǎn)與樞紐。正是由于在不同特性網(wǎng)絡(luò)中的這種差異，使得RWI算法的有效性不會(huì)僅局限于理論，在實(shí)際應(yīng)用中更加能體現(xiàn)其價(jià)值所在。

圖4為RWI與TI_BC兩種方法在不同數(shù)據(jù)集下運(yùn)行時(shí)間對(duì)比。如前文所述，TI_BC的時(shí)間復(fù)雜度為O(n3)，從圖4可看出RWI的時(shí)間消耗占比明顯更少；隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量遞增，兩種方法運(yùn)行時(shí)間的差異更加明顯。從圖4還可以看出，RWI相較于TI_BC在具有小世界網(wǎng)絡(luò)特性的數(shù)據(jù)集中具有明顯更低的時(shí)間占比，說明其對(duì)小世界網(wǎng)絡(luò)特性的網(wǎng)絡(luò)結(jié)構(gòu)具有更好的適應(yīng)性。

圖4 RWI與TI_BC在不同網(wǎng)絡(luò)運(yùn)行時(shí)間百分比堆積圖Fig.4 RWIand T I_BC in different network running time percentage stacking chart

3 結(jié)語

本文利用節(jié)點(diǎn)排序思想，通過結(jié)合多粒子隨機(jī)游走的方式，識(shí)別關(guān)鍵傳播路徑上的節(jié)點(diǎn)，利用粒子累計(jì)游走數(shù)量作為節(jié)點(diǎn)的排序依據(jù)，通過對(duì)比多種經(jīng)典免疫算法證實(shí)了RWI算法的有效性。

綜合考慮節(jié)點(diǎn)度中心性以及位置信息對(duì)傳播范圍與傳播爆發(fā)的時(shí)間影響，根據(jù)RWI算法在不同網(wǎng)絡(luò)模型、不同傳播模型進(jìn)行實(shí)驗(yàn)的結(jié)果證實(shí)：

1）在無向無權(quán)網(wǎng)絡(luò)中，由于真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)特性差異，對(duì)于社區(qū)化明顯的網(wǎng)絡(luò)，其社區(qū)邊緣的節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)傳播具有重要作用，通過對(duì)網(wǎng)絡(luò)中此類節(jié)點(diǎn)采取免疫能夠有效抑制網(wǎng)絡(luò)社區(qū)間的傳播，說明RWI算法對(duì)控制現(xiàn)實(shí)傳播具有指導(dǎo)意義；

2）由多粒子的隨機(jī)游走實(shí)驗(yàn)結(jié)果可知，受傳播機(jī)制與網(wǎng)絡(luò)結(jié)構(gòu)影響，節(jié)點(diǎn)的度中心性和所處網(wǎng)絡(luò)位置存在一定差異，從側(cè)面可以反映出節(jié)點(diǎn)傳播能力并不只受節(jié)點(diǎn)度值的影響，在控制網(wǎng)絡(luò)的傳播問題時(shí)，也應(yīng)充分考慮節(jié)點(diǎn)的位置信息，基于節(jié)點(diǎn)的隨機(jī)游走算法對(duì)于找出此類節(jié)點(diǎn)具有更高的準(zhǔn)確性；

3）相比于其他基于網(wǎng)絡(luò)連邊進(jìn)行的隨機(jī)游走算法以及基于介數(shù)中心性中節(jié)點(diǎn)對(duì)流量控制能力排序的算法，RWI具有更低的時(shí)間復(fù)雜度以及更廣泛的使用范圍。

綜上可知，本文提出的RWI算法在不同類型不同大小的網(wǎng)絡(luò)上均表現(xiàn)了較好的結(jié)果，在不同的真實(shí)數(shù)據(jù)集中，免疫資源有限的情況下，RWI被證明是優(yōu)于現(xiàn)有的經(jīng)典免疫策略。本文創(chuàng)新性地結(jié)合隨機(jī)游走思想的免疫算法為后續(xù)的復(fù)雜網(wǎng)絡(luò)傳播控制提供了新的思路，針對(duì)多種不同的真實(shí)數(shù)據(jù)集傳播實(shí)驗(yàn)，證明了算法在多種應(yīng)用場(chǎng)景的有效性。