王 斌,王亞云,盛津芳,孫澤軍,2

1(中南大學(xué) 計(jì)算機(jī)學(xué)院，長沙 410083)2(平頂山學(xué)院 網(wǎng)絡(luò)中心,河南 平頂山 467000)

1 引 言

復(fù)雜網(wǎng)絡(luò)簡化標(biāo)識現(xiàn)實(shí)世界中的復(fù)雜系統(tǒng),對復(fù)雜網(wǎng)絡(luò)的研究能幫助人們對其深刻認(rèn)知,了解內(nèi)部動(dòng)態(tài)演化及行為預(yù)測[1-3].復(fù)雜網(wǎng)絡(luò)中存在部分節(jié)點(diǎn),這些節(jié)點(diǎn)數(shù)量少,但是在整個(gè)網(wǎng)絡(luò)的信息傳播中扮演著關(guān)鍵的角色,稱為關(guān)鍵節(jié)點(diǎn).識別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域中的一個(gè)重要方向[4],對現(xiàn)實(shí)中網(wǎng)絡(luò)信息傳播[5],傳染病擴(kuò)散[6],產(chǎn)品推廣[7,8]等具有很高的實(shí)際價(jià)值,在一定程度上可以有效減少經(jīng)濟(jì)投入和避免經(jīng)濟(jì)損失[9].

近幾十年來,從基于結(jié)構(gòu)中心性,迭代細(xì)化中心性,到基于節(jié)點(diǎn)動(dòng)態(tài)操作,復(fù)雜網(wǎng)絡(luò)領(lǐng)域有很多識別關(guān)鍵節(jié)點(diǎn)的算法被提出,例如度中心性(Degree Centrality,DC)[10]算法通過統(tǒng)計(jì)網(wǎng)絡(luò)中與節(jié)點(diǎn)直接相連的鄰居節(jié)點(diǎn)個(gè)數(shù)作為判斷節(jié)點(diǎn)重要性的依據(jù).Chen等[11]考慮節(jié)點(diǎn)半局部信息,提出半局部中心性.介數(shù)中心性(Betweenness Centrality,BC)[12]描述了節(jié)點(diǎn)對網(wǎng)絡(luò)中沿最短路徑傳輸?shù)男畔⒘鞯目刂颇芰?隨機(jī)游走介數(shù)中心性認(rèn)為在網(wǎng)絡(luò)信息傳播過程中最短路徑比非最短路徑重要.K-shell[13]算法通過層層剝離處于網(wǎng)絡(luò)外層的節(jié)點(diǎn),認(rèn)為處于網(wǎng)絡(luò)核心的節(jié)點(diǎn)具有較高的影響力.特征向量中心性通過統(tǒng)計(jì)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的重要度作為該節(jié)點(diǎn)的關(guān)鍵性指標(biāo).PageRank[14]算法是特征向量中心性的變種[15],其是應(yīng)用在Google搜索引擎中的網(wǎng)頁排序算法.Lü[16]等提出的LeaderRank算法通過隨機(jī)游走的思想識別關(guān)鍵節(jié)點(diǎn),其在有向網(wǎng)絡(luò)中表現(xiàn)良好.HITS[17]賦予每個(gè)節(jié)點(diǎn)權(quán)威值和樞紐值,二者相互影響以做為評價(jià)節(jié)點(diǎn)影響力的指標(biāo).以及其他基于節(jié)點(diǎn)刪除和收縮的算法,如節(jié)點(diǎn)收縮法等.

上述算法從不同角度刻畫了節(jié)點(diǎn)的影響力,有各自的優(yōu)點(diǎn),但也有一定的局限性,例如,DC是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最直觀的算法,但是沒有考慮節(jié)點(diǎn)的位置及周圍節(jié)點(diǎn)的影響[18];k-shell在一些特殊的網(wǎng)絡(luò),如樹形網(wǎng)絡(luò)中,經(jīng)常會(huì)分配給大量節(jié)點(diǎn)相同的Ks值;PageRank將自己的PR值平均分配給相鄰節(jié)點(diǎn),這與實(shí)際認(rèn)知有偏差;BC和基于節(jié)點(diǎn)刪除或收縮的算法時(shí)間復(fù)雜度很高,并且一些算法在不連通網(wǎng)絡(luò)中效果欠佳,如節(jié)點(diǎn)刪除法不能區(qū)分刪除后使網(wǎng)絡(luò)變得不再連通的節(jié)點(diǎn)的重要度[19].

另一方面,上述算法大部分都是基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),沒有考慮節(jié)點(diǎn)之間的屬性信息,而網(wǎng)絡(luò)結(jié)構(gòu)在表達(dá)節(jié)點(diǎn)信息上具有一定的局限性.事實(shí)上,網(wǎng)絡(luò)中節(jié)點(diǎn)之間的交互行為也可能會(huì)影響節(jié)點(diǎn)的重要性.例如在社交網(wǎng)絡(luò)中,如果兩個(gè)個(gè)體之間有更多的共同點(diǎn),二者越相似,也就越信任對方,越傾向于交換更多信息;此外,如果某一個(gè)體與網(wǎng)絡(luò)中較多個(gè)體之間有關(guān)聯(lián),那么在信息傳播中,將信息傳輸給該個(gè)體將有利于信息流在整個(gè)網(wǎng)路中的快速擴(kuò)散.文獻(xiàn)[20] 考慮節(jié)點(diǎn)共同指向和指出的節(jié)點(diǎn)個(gè)數(shù),提出了基于LeaderRank和節(jié)點(diǎn)相似性的關(guān)鍵節(jié)點(diǎn)識別算法.本文結(jié)合提出的節(jié)點(diǎn)信任度和PageRank算法構(gòu)建一種關(guān)鍵節(jié)點(diǎn)識別算法TPR(Trust-PageRank),該算法綜合考慮了網(wǎng)絡(luò)本身的拓?fù)浣Y(jié)構(gòu)特性及節(jié)點(diǎn)之間的交互行為,避免因單一角度地刻畫造成評價(jià)的片面性.在實(shí)驗(yàn)部分將TPR算法和DC,BC,PageRank,HITS算法應(yīng)用在具體的真實(shí)網(wǎng)絡(luò)并進(jìn)行對比,結(jié)果表明TPR算法能合理有效地識別復(fù)雜網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn),并且可以有效區(qū)分重要度相當(dāng)?shù)墓?jié)點(diǎn).

2 基于信任度和PageRank的關(guān)鍵節(jié)點(diǎn)識別

2.1 基本思想

PageRank算法最初由萬維網(wǎng)網(wǎng)頁排序產(chǎn)生,它的有效性不是基于難以測量的內(nèi)在結(jié)構(gòu),而是其感知有效性和易于理解的哲學(xué):不是根據(jù)對象難以衡量的自身質(zhì)量進(jìn)行排序,如網(wǎng)頁的實(shí)用性,而是將每個(gè)鏈接理解為潛在的投票來挖掘網(wǎng)絡(luò)中隱藏的綜合特征[21].目前PageRank算法不僅是谷歌及其他搜索引擎的核心,而且被用在各種網(wǎng)絡(luò)環(huán)境中對數(shù)據(jù)進(jìn)行排名.PageRank算法認(rèn)為網(wǎng)頁的重要性依賴于與它相鄰的頁面重要性.如果一個(gè)網(wǎng)頁有很多來自其他重要頁面的鏈接,那么該網(wǎng)頁也有較高的重要性.算法初始時(shí),每個(gè)網(wǎng)頁擁有一個(gè)初始的PR值,通過不斷迭代達(dá)到穩(wěn)定狀態(tài).在這個(gè)過程中,每個(gè)網(wǎng)頁以一個(gè)隨機(jī)概率跳轉(zhuǎn)到相鄰網(wǎng)頁,以額外概率跳轉(zhuǎn)到所有網(wǎng)頁,節(jié)點(diǎn)vi的PageRank值定義為:

(1)

α為跳轉(zhuǎn)概率,一般會(huì)取α=0.85.

在PageRank算法中,網(wǎng)頁將自己的PR值平均分配給相鄰節(jié)點(diǎn),但是在實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)之間交換信息的概率及信息量很大程度上并不僅僅是平均分配.在網(wǎng)絡(luò)的信息傳播中,為了敘述簡便,在此假設(shè)其中只有一個(gè)節(jié)點(diǎn)需要將信息傳播到網(wǎng)絡(luò)中,為使信息盡可能以較快的速率傳輸?shù)剿泄?jié)點(diǎn),該節(jié)點(diǎn)應(yīng)將信息擴(kuò)散到與其相鄰的所有節(jié)點(diǎn),并且對于自己比較“信任”的節(jié)點(diǎn)會(huì)擴(kuò)散更多的信息,直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信息達(dá)到比較均衡的狀態(tài),或者算法達(dá)到一定的迭代次數(shù),這和我們在現(xiàn)實(shí)中的認(rèn)知是一致的.

本文中,網(wǎng)絡(luò)由G=(V,E)表示,其中V表示網(wǎng)絡(luò)的節(jié)點(diǎn)集,E表示節(jié)點(diǎn)的邊集.網(wǎng)絡(luò)G的鄰接矩陣為A={aij},在無向網(wǎng)絡(luò)中,如果節(jié)點(diǎn)vi與vj之間有連邊,則aij=1.n=|V|是網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù),m=|E|為網(wǎng)路中邊的個(gè)數(shù).表1給出了下文將要用到的符號列表.

表1 符號列表
Table 1 List of symbol

2.2 Trust-PageRank關(guān)鍵節(jié)點(diǎn)識別

2.2.1 相似性比例

在現(xiàn)實(shí)生活的社交網(wǎng)絡(luò)中,如果兩個(gè)個(gè)體有共同的愛好,那么他們在某種程度上會(huì)有一定的相似性,交互的頻率也會(huì)較多,也即,相互之間會(huì)交換更多的信息.相反,如果個(gè)體之間沒有任何交集,那么個(gè)體之間的相似性比較小,相應(yīng)地會(huì)以很小的頻率交互.

假設(shè)節(jié)點(diǎn)vi和vj的愛好集為H(i)和H(j),則節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的相似性s(i,j)為:

s(i,j)=|H(i)∩H(j)|

(2)

如圖1(a)所示的網(wǎng)絡(luò)中,節(jié)點(diǎn)v,1,2,3,4的愛好集合分別為H(v),H(1),H(2),H(3),H(4).

H(v)={basketball,pingpong,run},

H(1)={basketball,run},

H(2)={pingpong},

H(3)={tennis},

H(4)={run}.

則,

s(1,v)=|H(1)∩H(v)|=|{basketball,run}|=2,

s(2,v)=|H(2)∩H(v)|={pingpong}|=1,

s(3,v)=|H(3)∩H(v)|=|φ|=0,

s(4,v)=|H(4)∩H(v)|=|{run}|=1.

如果定義節(jié)點(diǎn)vi與其鄰居節(jié)點(diǎn)的相似性之和Si為:

(3)

則圖1(a)中節(jié)點(diǎn)v與其所有鄰居節(jié)點(diǎn)的相似性之和為Sv=2+1+1=4.

如果把節(jié)點(diǎn)的每一個(gè)愛好集合看做一個(gè)相鄰節(jié)點(diǎn)集,如圖1(b)所示,那么節(jié)點(diǎn)的相似性就由節(jié)點(diǎn)的共同鄰居節(jié)點(diǎn)決定:如果兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越相似,那么這兩個(gè)節(jié)點(diǎn)也就越相似.另外,公式(2)只是為了便于簡要說明節(jié)點(diǎn)的相似性依賴于其鄰居節(jié)點(diǎn)的相似性的思想,用以計(jì)算相似性值過于簡化.本文采用了另一種計(jì)算相似性的算法:SimRank算法.

SimRank[22]算法認(rèn)為兩個(gè)節(jié)點(diǎn)的相似性取決于其鄰居節(jié)點(diǎn),若其鄰居節(jié)點(diǎn)越相似,則二者越相似.基本的SimRank算法公式為:

(4)

其中,C是一個(gè)衰減因子,為常數(shù),C∈[0,1],一般情況下,如果N(a)或N(b)為空集,為了避免公式(4)出現(xiàn)除數(shù)為0的情況,會(huì)定義s(a,b)=0.定義網(wǎng)絡(luò)節(jié)點(diǎn)的初始相似性為:

(5)

SimRank和PageRank算法類似,都是采用迭代計(jì)算,且s(a,b)=s(b,a).由于在本實(shí)驗(yàn)中計(jì)算的是相似性比例,因此,常數(shù)C的值對實(shí)驗(yàn)結(jié)果并無影響,在此本文取C=1.

基于節(jié)點(diǎn)相似性可以得到相似性比例.

定義1.節(jié)點(diǎn)vi占節(jié)點(diǎn)vj的相似性比例Rs(i,j)為:

(6)

圖1(b)中節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合Nv={1,2,3,4,5,6,8},節(jié)點(diǎn)v與其所有鄰居節(jié)點(diǎn)相似性之和為Sv=s(1,v)+s(2,v)+s(3,v)+s(4,v)+s(5,v)+s(6,v)+s(8,v),則節(jié)點(diǎn)1占節(jié)點(diǎn)v的相似性比例為Rs(1,v)=s(1,v)/Sv,其他節(jié)點(diǎn)與此類似.

圖1 節(jié)點(diǎn)愛好集圖及節(jié)點(diǎn)相似性網(wǎng)絡(luò)Fig.1 Hobby sets and the network of nodes′ similarity

2.2.2 相鄰度比例

網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的度越大,其與周圍節(jié)點(diǎn)接觸的范圍越大.如果一個(gè)節(jié)點(diǎn)需要進(jìn)行信息傳播,那么將信息傳播給度值較大的鄰居節(jié)點(diǎn)將有助于網(wǎng)絡(luò)中信息流的擴(kuò)散,但并不是片面的只將信息傳播給度值最大的節(jié)點(diǎn).如圖2所示,節(jié)點(diǎn)v的相鄰節(jié)點(diǎn)1,2,3,4中,節(jié)點(diǎn)1的度值最大.如果節(jié)點(diǎn)v只將信息傳播給度值最大的節(jié)點(diǎn)1,那么區(qū)域b,c和d將得不到任何傳輸?shù)男畔?為使信息能盡可能以最大速率到達(dá)網(wǎng)絡(luò)中的所有節(jié)點(diǎn),本文綜合考慮節(jié)點(diǎn)及相鄰節(jié)點(diǎn)的度值提出相鄰度比例.

定義2.節(jié)點(diǎn)vi占節(jié)點(diǎn)vj的相鄰度比例Rd(i,j)為:

(7)

其中,di表示節(jié)點(diǎn)vi的度,圖2展示了節(jié)點(diǎn)鄰居集合及其相鄰度比例.

2.2.3 節(jié)點(diǎn)信任度

網(wǎng)絡(luò)中節(jié)點(diǎn)之間的信任度由節(jié)點(diǎn)基于屬性信息的相似性比例和基于拓?fù)浣Y(jié)構(gòu)的度比例組成.

定義3.節(jié)點(diǎn)vj對vi的信任度Tij為:

Tij=(1-k)Rs(i,j)+kRd(i,j)

(8)

k∈[0,1],本文中,定義k與PageRank算法中的跳轉(zhuǎn)概率α相等,即k=α.

圖2 節(jié)點(diǎn)相鄰度比例Fig.2 Degree-ratio of nodes

2.2.4 Trust-PageRank算法

結(jié)合PageRank算法提出基于節(jié)點(diǎn)信任度的Trust-PageRank算法.從節(jié)點(diǎn)信任值來看,網(wǎng)絡(luò)中的信息流動(dòng)時(shí)節(jié)點(diǎn)會(huì)將信息按信任度分配給相鄰節(jié)點(diǎn),同時(shí)信任度越大的鄰居節(jié)點(diǎn)將會(huì)得到更多的信息.通過將節(jié)點(diǎn)信任度引入到PageRank算法中識別關(guān)鍵節(jié)點(diǎn).

表2 基于信任度的關(guān)鍵節(jié)點(diǎn)識別算法

Table 2 Algorithm identifying influential nodes based on trust-value

Input:G=(V,E)Output:rankList1 forallvs∈Vdo2 Initializethenetworkandcountthesetofadjacentnodesofvs;3 endfor4 forallconnectednodesvu,vv∈Vdo5 Initializethesimilaritys(vu,vv)ofvuandvvusingthefor-mula(5);6 endfor7 forallvi∈Vdo8 foralladjacentnodesvjofvi,do9 ifvi=vjthen10 s(vi,vj)=1;11 else12 Statisticthesimilaritiess(vm,vn)betweenneigh-bornodesofvi,vjwithvm∈Nvi,vn∈Nvjandthengets(vi,vj)usingtheformula(4);13 endif14 simRatioMap.put((vi,vj),s(vi,vj));15 endfor16 endfor17 forallvt∈Vdo18 CalculateTPRtbasedonsimRatioMapandtheratioofde-greeObtainedatthefirstofthealgorithmusingtheformula(9);19 rankList.put(vt,TPRt);20 endfor21 rankList.sort();

定義4.網(wǎng)絡(luò)中節(jié)點(diǎn)vi的影響力指標(biāo)TPRi為:

(9)

其中,Tij為由公式(8)得出的節(jié)點(diǎn)vj對節(jié)點(diǎn)vi的信任度,n為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù),α為跳轉(zhuǎn)概率,N(i)為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合,di表示節(jié)點(diǎn)vi的度.本文實(shí)驗(yàn)取α=0.85.

算法通過對輸入的網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行初始化,迭代計(jì)算得到節(jié)點(diǎn)相似性集,根據(jù)相似性集合和初始化集合計(jì)算相似性比例和相鄰度比例,進(jìn)而得到節(jié)點(diǎn)之間的信任度,再結(jié)合PageRank計(jì)算網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的TPR指標(biāo)值.算法具體步驟如表2所示.

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

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

本文選擇9個(gè)真實(shí)網(wǎng)絡(luò)及1個(gè)非真實(shí)網(wǎng)絡(luò)進(jìn)行算法有效性驗(yàn)證,分別包括Email網(wǎng)絡(luò),Euroroad電子道路網(wǎng)絡(luò),US Power Grid美國電力網(wǎng)絡(luò),Protein和PDZBase蛋白質(zhì)網(wǎng)絡(luò),Polbooks美國政治書網(wǎng)絡(luò),Football足球俱樂部網(wǎng)絡(luò)等.各個(gè)網(wǎng)絡(luò)詳細(xì)信息如表3所示.

表3 數(shù)據(jù)集
Table 3 Data sets

網(wǎng)絡(luò)|v||E|kmaxCCKite10183.660.578Zachary34784.5888170.588Polbooks1054418.4250.488Football11561310.661120.403PDZBase2122422.283210.013Email113354519.622710.254Euroroad117414172.414100.02Propro187022772.356560.153Protein313361493.9251290.106PowerGrid494165942.669190.107

其中,|v|和|E|分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊的數(shù)量,和kmax表示網(wǎng)絡(luò)節(jié)點(diǎn)的平均度和最大度,CC為網(wǎng)絡(luò)平均聚類系數(shù).

3.2 評價(jià)指標(biāo)

3.2.1 SIR模型

本文采用SIR模型[23]評價(jià)TPR算法的性能及有效性.在SIR模型中,所有節(jié)點(diǎn)共有3種狀態(tài):

1)易感染狀態(tài)S:處于該狀態(tài)的節(jié)點(diǎn)會(huì)被其他節(jié)點(diǎn)感染;

2)感染狀態(tài)I:感染節(jié)點(diǎn)會(huì)以β的概率感染其他節(jié)點(diǎn),并以γ的概率恢復(fù)到免疫狀態(tài);

3)免疫狀態(tài)R:由感染狀態(tài)恢復(fù),不具有感染其他節(jié)點(diǎn)的能力,并且不能再次被感染.評價(jià)實(shí)驗(yàn)進(jìn)行多次迭代,進(jìn)行t步感染,每次迭代時(shí)選擇一個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn).將最終t步感染后網(wǎng)絡(luò)中感染節(jié)點(diǎn)及恢復(fù)節(jié)點(diǎn)的平均數(shù)量做為該節(jié)點(diǎn)的傳播能力,記為F(t).定義節(jié)點(diǎn)vi的SIR傳播重要性Ki為：

(10)

其中Nite為迭代次數(shù),本文中Nite=100,nI和nR分別為感染節(jié)點(diǎn)和恢復(fù)節(jié)點(diǎn)的數(shù)量.

3.2.2 Kendall系數(shù)

Kendall相關(guān)系數(shù)[24]用于測量多列等級變量的相關(guān)性,定義為:

(11)

其中,C,D分別代表兩個(gè)排序序列集合中一致和不一致的數(shù)量,N表示統(tǒng)計(jì)對象個(gè)數(shù).τ∈[-1,1],τ取值越大,表示二者相關(guān)性越強(qiáng).τ=0說明二者相互獨(dú)立;τ=-1,表示二者排序相關(guān)性相反.

3.3 有效性分析

本文首先以小型風(fēng)箏網(wǎng)絡(luò)Kite[25]及跆拳道Zachary網(wǎng)絡(luò)為例初步驗(yàn)證算法的有效性,網(wǎng)絡(luò)如圖3所示.將TPR算法應(yīng)用在Kite及Zachary網(wǎng)絡(luò)中識別其關(guān)鍵節(jié)點(diǎn),得出網(wǎng)絡(luò)中的Top-10節(jié)點(diǎn),并將其結(jié)果與DC,BC,PageRank,HITS算法進(jìn)行對比,結(jié)果如表4所示.

圖3 兩個(gè)小型網(wǎng)絡(luò)Fig.3 Two small-scale networks

從表4中可以看出對于對稱的風(fēng)箏網(wǎng)絡(luò),各個(gè)算法排序結(jié)果都比較合理,TPR算法識別的關(guān)鍵節(jié)點(diǎn)排序與DC一致,此外TPR相對于PageRank算法認(rèn)為節(jié)點(diǎn)6和8比節(jié)點(diǎn)2排名靠前,是因?yàn)楣?jié)點(diǎn)2的TPR值主要由其鄰居節(jié)點(diǎn)1,3貢獻(xiàn),而節(jié)點(diǎn)1,3的TPR指標(biāo)值都比較小;此外節(jié)點(diǎn)2的度數(shù)較小,并且其與節(jié)點(diǎn)3的相似性相比節(jié)點(diǎn)3的其他鄰居節(jié)點(diǎn)(節(jié)點(diǎn)4,5)并不占優(yōu)勢;而節(jié)點(diǎn)6的(或節(jié)點(diǎn)8)鄰居節(jié)點(diǎn)排名均比較靠前,并且其度數(shù)和相似性與周圍鄰居節(jié)點(diǎn)相比無明顯差別.

Zachary網(wǎng)絡(luò)中,TPR算法選擇的Top-10節(jié)點(diǎn)基本與其他算法一致,僅在排序上有部分差異.DC,PageRank,TPR認(rèn)為前10個(gè)重要節(jié)點(diǎn)為節(jié)點(diǎn)1,2,3,4,9,14,24,32,33,34,BC算法認(rèn)為節(jié)點(diǎn)6,20比節(jié)點(diǎn)4,24重要,HITS算法認(rèn)為節(jié)點(diǎn)31比節(jié)點(diǎn)24重要.

在進(jìn)行SIR傳播驗(yàn)證時(shí),由于在實(shí)際中節(jié)點(diǎn)的擴(kuò)散能力在初始傳播時(shí)更為重要[11],因此,本文只將節(jié)點(diǎn)進(jìn)行10步(即t=10)感染傳播,而不是等待整個(gè)網(wǎng)絡(luò)的感染傳播達(dá)到穩(wěn)定狀態(tài).

首先,每次迭代中感染節(jié)點(diǎn)以0.3的概率感染其鄰居節(jié)點(diǎn),并以1的概率恢復(fù)到免疫狀態(tài),即β=0.3,γ=1.將TPR算法和DC,BC,PageRank,HITS算法進(jìn)行對比,這些中心性算法計(jì)算的各個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)中心性值與經(jīng)過10步SIR傳播計(jì)算的節(jié)點(diǎn)傳播重要性統(tǒng)計(jì)結(jié)果如圖4所示.

在Email網(wǎng)絡(luò)(圖4(a))中,DC,PageRank,HITS及TPR算法能很好地表現(xiàn)出節(jié)點(diǎn)重要度與SIR傳播重要度指標(biāo)正相關(guān)的特征,且DC,PageRank,TPR算法中節(jié)點(diǎn)分布集中,線性程度更好,而BC的中心性指標(biāo)值分布整體比較分散.Euroroad網(wǎng)絡(luò)(圖4(b))中,各個(gè)算法都能表現(xiàn)正相關(guān)性特性,但是TPR及PageRank算法節(jié)點(diǎn)分布集中且正相關(guān)性特征明顯,DC不能區(qū)分度數(shù)相同的節(jié)點(diǎn),BC不能很好地表現(xiàn)中心性值與節(jié)點(diǎn)傳播能力的正相關(guān)性(其圖中節(jié)點(diǎn)大多集中在介數(shù)值較小即橫坐標(biāo)軸左側(cè)處),HITS算法中對于部分SIR傳播重要度值較大的節(jié)點(diǎn),其HITS中心性指標(biāo)值相對較低.DC,PageRank,HITS及TPR算法在Protein網(wǎng)絡(luò)(圖4(c))中結(jié)果表現(xiàn)相似,BC算法中節(jié)點(diǎn)分布相對分散.幾種算法在Power Grid網(wǎng)絡(luò)(圖4(d))中表現(xiàn)結(jié)果中同Euroroad網(wǎng)絡(luò)相似.從上述實(shí)驗(yàn)結(jié)果圖來看,在Email,Euroroad,Protein網(wǎng)絡(luò)中,TPR算法計(jì)算的中心性指標(biāo)值與SIR模型得到的節(jié)點(diǎn)傳播重要度線性一致性相比其他算法較好或相當(dāng),即對于SIR模型識別的重要度相當(dāng)?shù)墓?jié)點(diǎn),TPR算法也認(rèn)為這些節(jié)點(diǎn)重要度差別不大.在Power Grid網(wǎng)絡(luò)中,HITS算法的線性一致性優(yōu)于TPR算法.

表4 網(wǎng)絡(luò)Top-10節(jié)點(diǎn)
Table 4 Top-10 nodes of kite and zachary

排序KiteDCBCPageRankHITSTPR排序ZacharyDCBCPageRankHITSTPR17377713413434124444421341134355555333333333349299943333335107101010523222263936364932932761028673224144886638891424414928822914209329101111110246143124

圖4 網(wǎng)絡(luò)不同中心性值與SIR傳播力對比Fig.4 Figure comparing between central-value and the propagation of SIR

其次,為了評估每個(gè)算法識別出的排名靠前的關(guān)鍵節(jié)點(diǎn)的感染能力,本文選取DC,BC,PageRank,HITS算法和TPR算法分別識別出的前10個(gè)關(guān)鍵節(jié)點(diǎn)作為種子節(jié)點(diǎn),設(shè)定β=0.3,γ=1,進(jìn)行20步傳播,并對此進(jìn)行100次迭代,最后統(tǒng)計(jì)傳播結(jié)束后網(wǎng)絡(luò)中感染節(jié)點(diǎn)和恢復(fù)節(jié)點(diǎn)的總數(shù),以此來表示各個(gè)算法選出的前10個(gè)節(jié)點(diǎn)的傳播能力,結(jié)果如圖5所示.

可以看出,在Email(圖5(a))和Protein(圖5(c))網(wǎng)絡(luò)中各個(gè)算法識別的Top-10節(jié)點(diǎn)傳播能力相當(dāng),且t<5時(shí),DC,BC,PageRank,TPR算法感染曲線斜率相當(dāng),HITS算法線性斜率略小于其他算法.在Euroroad網(wǎng)絡(luò)(圖5(b))中,各個(gè)算法識別的Top-10節(jié)點(diǎn)在20步傳播之后,網(wǎng)絡(luò)中處于感染和恢復(fù)狀態(tài)的節(jié)點(diǎn)數(shù)及種子節(jié)點(diǎn)感染速率均為TPR>DC>PageRank> HITS> BC.在Power Grid網(wǎng)絡(luò)(圖5(d))中,DC識別的Top-10節(jié)點(diǎn)傳播能力較強(qiáng),各個(gè)算法的Top-10節(jié)點(diǎn)感染節(jié)點(diǎn)數(shù)量和感染增速分別為DC> TPR> PageRank> BC> HITS和DC> TPR> PageRank> HITS> BC.上述實(shí)驗(yàn)結(jié)果中,0

圖5 感染和恢復(fù)節(jié)點(diǎn)的數(shù)量增長圖Fig.5 Growth graph of infected and recovered nodes

表5 kendall相關(guān)性系數(shù)
Table 5 Kendall′s coefficient

數(shù)據(jù)算法DCBCPageRankHITSTPRPolbooks0.687350.282750.645970.517240.67356PDZBase0.269170.461660.299840.409830.46589Football0.113630.132570.215900.189390.30681Propro0.410730.411470.399700.140080.54318

4 結(jié) 論

本文考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及節(jié)點(diǎn)屬性信息提出節(jié)點(diǎn)相鄰度比例及相似性比例,綜合提出節(jié)點(diǎn)信任度,并結(jié)合PageRank提出基于節(jié)點(diǎn)信任度的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別算法Trust-PageRank.實(shí)驗(yàn)部分,首先將TPR算法應(yīng)用在風(fēng)箏網(wǎng)絡(luò)和跆拳道網(wǎng)絡(luò)中初步驗(yàn)證了算法的有效性.為了評估TPR算法識別關(guān)鍵節(jié)點(diǎn)的準(zhǔn)確度及感染能力,本文另選擇8個(gè)真實(shí)網(wǎng)絡(luò),利用SIR模型及kendall相關(guān)性系數(shù)評估網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播速率和能力.將DC,BC,PageRank,HITS和TPR算法識別出的各個(gè)網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn),與利用SIR模型得到的結(jié)果進(jìn)行對比,并計(jì)算各個(gè)對比算法識別出的前30%的關(guān)鍵節(jié)點(diǎn)與SIR模型排序結(jié)果的相關(guān)性系數(shù),結(jié)果顯示TPR算法能有效地識別關(guān)鍵節(jié)點(diǎn),并且在SIR初始傳播和識別重要度相當(dāng)?shù)墓?jié)點(diǎn)方面有一定的優(yōu)勢.