基于不等概率疊加隨機(jī)游走關(guān)鍵點識別

寧 陽，武志峰，張 策

(天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津 300222)

0 引 言

網(wǎng)絡(luò)科學(xué)研究的是看起來互不相同的復(fù)雜網(wǎng)絡(luò)之間共性和處理的普適方法。網(wǎng)絡(luò)科學(xué)中研究的問題來源于各種實際網(wǎng)絡(luò)，網(wǎng)絡(luò)中的關(guān)鍵點識別是網(wǎng)絡(luò)科學(xué)的重要研究內(nèi)容之一。根據(jù)傳播動力學(xué)的研究形成的理論和方法更好地認(rèn)識不同網(wǎng)絡(luò)上的傳播行為之間的聯(lián)系與區(qū)別。關(guān)鍵點識別的研究在不同的領(lǐng)域具有重要意義，例如在社會網(wǎng)絡(luò)中找到最有影響力的人可以控制流言的傳播，疾病傳播過程中找到易感人群，對疾病進(jìn)行有效的預(yù)防和控制，城市交通系統(tǒng)、電力系統(tǒng)中找到關(guān)鍵樞紐進(jìn)行重點維護(hù)，降低經(jīng)濟(jì)損失風(fēng)險等。有效地評價和衡量網(wǎng)絡(luò)中節(jié)點的重要性，借助圖論的概念和術(shù)語，將具體實際問題抽象為圖，得到網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，將多學(xué)科融合在一起作為研究方向，具有廣泛的應(yīng)用價值。

首先介紹提出不等概率疊加隨機(jī)游走的相關(guān)工作，然后介紹不等概率疊加隨機(jī)游走方法，構(gòu)建不等概率轉(zhuǎn)移矩陣，進(jìn)行疊加。隨機(jī)游走，通過相似和衡量節(jié)點重要性。通過對3個數(shù)據(jù)集的仿真實驗，與度中心性、介數(shù)中心性、接近中心性和等概率疊加隨機(jī)游走進(jìn)行比較，并與SIR標(biāo)準(zhǔn)傳播模型[1-2]進(jìn)行Kendall tau距離[3-4]相關(guān)性分析，驗證該方法的有效性。

1 相關(guān)工作

復(fù)雜網(wǎng)絡(luò)中關(guān)鍵點識別的排序方法很多，文獻(xiàn)[5]綜述了關(guān)鍵點識別問題和方法，并對其進(jìn)行分類，描述了最重要的進(jìn)展和最新技術(shù)。近年來，學(xué)者通常在衡量節(jié)點的常用指標(biāo)上進(jìn)行改進(jìn)。無向網(wǎng)絡(luò)中幾個常用衡量節(jié)點重要性的指標(biāo)包括度值、介數(shù)、接近數(shù)、k-殼值和特征向量[6-10]。有向網(wǎng)絡(luò)中經(jīng)典的兩個算法是Kleinberg提出的HITS算法[11]及Page和Brin提出的PageRank算法[12]。度中心性通過衡量一個節(jié)點的度，度越大節(jié)點越重要，即與節(jié)點在網(wǎng)絡(luò)中所處的位置有關(guān)；介數(shù)中心性是經(jīng)過某一節(jié)點整個網(wǎng)絡(luò)中所有節(jié)點對之間的最短路徑的數(shù)量反映節(jié)點重要性指標(biāo)；接近中心性通過計算當(dāng)前節(jié)點到網(wǎng)絡(luò)中其他所有節(jié)點的距離在某種程度上反映節(jié)點重要性；k-殼值通過不斷地在原始網(wǎng)絡(luò)中去除度值為1，2，3…的節(jié)點及其連邊，從而進(jìn)行節(jié)點重要性識別的一種推廣的度值指標(biāo)；特征向量中心性既考慮了鄰居節(jié)點的數(shù)量又考慮了鄰居節(jié)點的重要性[1]。HITS算法通過刻畫節(jié)點的權(quán)威性和樞紐性指標(biāo)，衡量節(jié)點重要性。PageRank算法通過指向當(dāng)前節(jié)點的數(shù)量和質(zhì)量衡量節(jié)點重要性。文獻(xiàn)[13]提出通過節(jié)點間的相互作用力構(gòu)建隨機(jī)游走模型中的概率轉(zhuǎn)移矩陣，從物理學(xué)的角度考慮網(wǎng)絡(luò)中邊的實際意義。文獻(xiàn)[14]考慮節(jié)點度及鄰居節(jié)點拓?fù)渲睾隙龋@取節(jié)點兩步內(nèi)的鄰居節(jié)點信息，通過計算節(jié)點之間相似度衡量節(jié)點重要性。文獻(xiàn)[15]提出半局部中心性方法，解決大規(guī)模網(wǎng)絡(luò)中時間消耗大的問題，僅考慮了節(jié)點兩步轉(zhuǎn)移到達(dá)節(jié)點的數(shù)量及節(jié)點度。文獻(xiàn)[16]考慮節(jié)點二階鄰居節(jié)點，節(jié)點更有遠(yuǎn)見的轉(zhuǎn)移到度(出度)大的節(jié)點，改進(jìn)PageRank指標(biāo)計算轉(zhuǎn)移概率矩陣的平穩(wěn)分布衡量節(jié)點重要性。文獻(xiàn)[17]結(jié)合節(jié)點中心性和邊的中心性指標(biāo)在無向網(wǎng)絡(luò)中重新定義轉(zhuǎn)移概率矩陣衡量節(jié)點重要性。文獻(xiàn)[18]提出了一種疊加游走相似和表征節(jié)點重要性的方法，考慮節(jié)點度、鄰接節(jié)點的屬性以及節(jié)點在網(wǎng)絡(luò)中的位置，基于等概率的隨機(jī)游走，但未考慮實際網(wǎng)絡(luò)中游走的傾向性。

針對上述問題，以及受現(xiàn)有研究的啟發(fā)，考慮節(jié)點之間的相似性[19]，進(jìn)行有偏的隨機(jī)游走，考慮兩步到達(dá)節(jié)點的概率，提出一種基于不等概率疊加隨機(jī)游走的重要節(jié)點識別算法。該方法將Node2 vec[20]中提到的隨機(jī)游走方法2nd order隨機(jī)游走與有疊加效應(yīng)的局部隨機(jī)游走指標(biāo)[18-19]相結(jié)合，考慮節(jié)點之間的相似性，同時考慮不等概率隨機(jī)游走。2nd order隨機(jī)游走下一步的選擇不再是等概率隨機(jī)的，而是以不等概率進(jìn)行隨機(jī)游走。這里引入不等概率的隨機(jī)游走，考慮有限次的游走步數(shù)、節(jié)點度的信息、節(jié)點之間的相似性作為不等概率隨機(jī)游走的依據(jù)，進(jìn)行無向網(wǎng)絡(luò)中的關(guān)鍵節(jié)點識別。

2 不等概率疊加隨機(jī)方法

文中提出的基于不等概率疊加隨機(jī)游走關(guān)鍵點識別方法主要包括3個階段，其中2.1節(jié)描述不等概率隨機(jī)游走轉(zhuǎn)移矩陣的構(gòu)建，根據(jù)Jaccard指標(biāo)[19,21]計算每個節(jié)點和網(wǎng)絡(luò)中其他節(jié)點的相似性，考慮任意兩個節(jié)點間有直接連邊，但是無共同鄰居的情況，采用文獻(xiàn)[18]疊加隨機(jī)游走通過相似和衡量節(jié)點重要度提到的節(jié)點度分之鄰接矩陣值來計算。通過歸一化處理，以此來構(gòu)建概率轉(zhuǎn)移矩陣。2.2節(jié)描述疊加效應(yīng)的局部隨機(jī)游走，根據(jù)有疊加效應(yīng)的局部隨機(jī)游走指標(biāo)[19]，在局部隨機(jī)游走指標(biāo)(local random walk，LRW)[22]的基礎(chǔ)上，將t步及其以前的結(jié)果加總得到疊加效應(yīng)的局部隨機(jī)游走相似性。這種方法可以增大鄰近目標(biāo)節(jié)點的點與目標(biāo)節(jié)點相連的機(jī)會。2.3節(jié)基于相似和的疊加隨機(jī)游走[18]，根據(jù)疊加效應(yīng)的局部隨機(jī)游走指標(biāo)，累加各行相似度，從而根據(jù)對應(yīng)節(jié)點的累加相似和進(jìn)行重要節(jié)點識別。

2.1 構(gòu)建不等概率隨機(jī)游走轉(zhuǎn)移矩陣

隨機(jī)游走(random walk)指基于過去的表現(xiàn)，無法預(yù)測將來的發(fā)展步驟和方向，下一步的選擇是隨機(jī)的，一般來講，節(jié)點通過存在邊到達(dá)相鄰節(jié)點的概率是相同的，到達(dá)非鄰居節(jié)點的概率是0，即等概率的隨機(jī)選擇到達(dá)存在邊的節(jié)點。

但實際中，從一個節(jié)點到其他鄰居節(jié)點的概率不是均勻隨機(jī)的，而是有偏的，所以文中提出基于不等概率進(jìn)行隨機(jī)游走，采用Jaccard指標(biāo)衡量網(wǎng)絡(luò)中節(jié)點之間的相似性，這里不僅考慮了存在邊的鄰居節(jié)點，同時也考慮了部分非鄰居節(jié)點，即兩步轉(zhuǎn)移能夠到達(dá)的節(jié)點。同時對于節(jié)點間存在直接連邊，但是兩個節(jié)點沒有共同鄰居，造成的Jaccard指標(biāo)衡量相似性不足的問題，文中基于文獻(xiàn)[18]考慮節(jié)點度的信息，作為相鄰節(jié)點間轉(zhuǎn)移概率。

將一個具體網(wǎng)絡(luò)抽象為一個由點集V和邊集E組成的圖G=(V,E)。頂點數(shù)記為N=|V|，邊數(shù)記為M=|E|。兩種常見的表示圖的基本結(jié)構(gòu)是鄰接矩陣(adjacency matrix)和鄰接表(adjacency list)。文中將原始數(shù)據(jù)轉(zhuǎn)化為鄰接矩陣，圖G的鄰接矩陣A=(aij)N×N是一個N階方陣，第i行第j列上的元素aij定義[1]如下：

無權(quán)無向圖：

(1)

設(shè)置初始狀態(tài)，將一個walker放置在無向無權(quán)圖G任意節(jié)點i，構(gòu)造隨機(jī)游走模型，walker每一步根據(jù)節(jié)點之間相似性，以不等概率p到達(dá)鄰居節(jié)點，同時，walker以p到達(dá)兩步轉(zhuǎn)移節(jié)點。游走的每一步方向都與已經(jīng)發(fā)生的事件無關(guān)，walker經(jīng)過的路線是一條馬爾可夫鏈。

算法主要步驟如下：

(1)使用鄰接矩陣表示圖的基本結(jié)構(gòu)，得到每個節(jié)點的度信息;

(2)使用Jaccard指標(biāo)計算節(jié)點相似性，兩節(jié)點直接相連，沒有共同鄰居利用節(jié)點度信息進(jìn)行計算；Jaccard指標(biāo)是在共同鄰居的基礎(chǔ)上考慮兩端節(jié)點度的影響，提出的衡量節(jié)點相似性指標(biāo)。

(2)

對于節(jié)點vx，鄰居集合為Γ(x)，sxy為節(jié)點vx，vy的相似性。

(3)

(4)

2.2 基于疊加效應(yīng)的局部隨機(jī)游走

劉偉平和呂琳媛[22]考慮有限次的隨機(jī)游走，提出一種基于網(wǎng)絡(luò)局部隨機(jī)游走的相似性指標(biāo)(LRW),在LRW基礎(chǔ)上，將t步及其以前的結(jié)果加總得到SRW的值，即：

(5)

設(shè)各個節(jié)點的初始資源分布為qx，基于t步隨機(jī)游走的相似性為：

(6)

文中采用劉偉平和呂琳媛提出的一種與度分布一致性的初始資源，qx=kx/M，其中M作為網(wǎng)絡(luò)的總邊數(shù)，對每一對節(jié)點對都相同，計算過程忽略不計。πxy(t)表示walker從節(jié)點x經(jīng)過t步游走到節(jié)點y的轉(zhuǎn)移概率矩陣，一般的k步轉(zhuǎn)移概率矩陣正好是一步轉(zhuǎn)移概率矩陣的k次方，可以證明k步轉(zhuǎn)移概率矩陣中各行元素之和都是1。

2.3 基于相似和的疊加隨機(jī)游走

相似度矩陣中的值代表對應(yīng)節(jié)點之間的相似度，每一行代表當(dāng)前節(jié)點與其他所有節(jié)點的相似度，采用文獻(xiàn)[18]提出的相似和概念衡量節(jié)點重要性。累加各行相似度，得到基于相似和的疊加隨機(jī)游走相似性指標(biāo)，將其用作網(wǎng)絡(luò)中關(guān)鍵節(jié)點識別。

公式如下所示：

(7)

算法流程如圖1所示。

圖1 算法流程

3 實驗結(jié)果與分析

3.1 SIR傳播模型

文中使用SIR傳播模型[1-2]得到的排序作為標(biāo)準(zhǔn)排序結(jié)果，在典型的傳染病模型中，N個節(jié)點的狀態(tài)可分為3類：

S:易染狀態(tài)，初始條件下所有節(jié)點均為易染狀態(tài)，該節(jié)點以β的概率被鄰居節(jié)點感染。

I:感染狀態(tài)，感染某種病毒作為傳染源的節(jié)點，該個體以β概率感染其鄰居節(jié)點。

R:移除狀態(tài)，也稱免疫狀態(tài)或恢復(fù)狀態(tài)，感染狀態(tài)節(jié)點以β概率感染鄰居易感節(jié)點后，以γ概率變?yōu)镽移除狀態(tài)，不再具有感染能力和易感特性。

3.2 Kendall tau距離

Kendall tau距離[3]計算兩個排序列表之間成對分歧數(shù)量，即兩個完成列表σ和τ，K(σ,τ)表示兩個列表之間的差異性:

K(σ,τ)=

|{(i,j):iτ(j)}|

(8)

例：σ={1,2,3,4}，τ={1,3,2,4}，σ列表與τ列表二元組集合如圖2所示。

二元組σ(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)τ(1,3)(1,2)(1,4)(3,2)(3,4)(2,4)K000100K=1,K'=1-2*1/4*3=0.833

3.3 仿真實驗

根據(jù)上述分析，為了驗證文中提出的基于不等概率疊加隨機(jī)游走關(guān)鍵點識別方法的有效性，對9/11恐怖襲擊網(wǎng)絡(luò)[24]、科研合作網(wǎng)[25]、USAir97數(shù)據(jù)集進(jìn)行仿真實驗，使用Python語言對算法進(jìn)行實現(xiàn)，并與度中心性、介數(shù)中心性、接近中心性、等概率疊加隨機(jī)游走方法進(jìn)行比較；對3個數(shù)據(jù)集基于SIR模型計算標(biāo)準(zhǔn)排序結(jié)果，計算各中心性算法與SIR的Kendall tau距離的差異；分析算法的時間復(fù)雜度。表1給出了這3個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)統(tǒng)計特征,其中n表示節(jié)點數(shù)，m表示邊數(shù)，表示節(jié)點平均度，kmax表示節(jié)點最大度，表示網(wǎng)絡(luò)節(jié)點間最短路徑平均數(shù)，C表示聚類系數(shù)，用來評估節(jié)點聚集成團(tuán)的集聚程度；R表示同配系數(shù)，用來反映鄰接節(jié)點間的度相關(guān)性；H表示異質(zhì)系數(shù)，衡量網(wǎng)絡(luò)中節(jié)點度分布的異質(zhì)性[1,26]。可以看出3個網(wǎng)絡(luò)具有明顯的小世界性，即高聚類系數(shù)和短的平均最短路徑長度，同時USAir97擁有明顯大度節(jié)點且具有高異質(zhì)性，因此具有無標(biāo)度網(wǎng)絡(luò)的特征。

表1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的統(tǒng)計特征

9/11恐怖襲擊是伊斯蘭恐怖組織在美國發(fā)動的四次有組織的恐怖襲擊，19名恐怖分子劫持四架客機(jī)，該無向網(wǎng)絡(luò)結(jié)構(gòu)共包含62個節(jié)點，148條邊，每個節(jié)點代表一名恐怖分子，包含劫持客機(jī)的19名恐怖分子及其同謀者。節(jié)點之間的邊代表恐怖分子之間的聯(lián)系。網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示，其中4次劫機(jī)行動中所在飛機(jī)的恐怖分子編號為1-19(A11:1-2-3-4-5(飛行員)、UA175:5-6-7-8(飛行員)-9-10、AA77:11-12-13(飛行員)-14-15)、UA93:16-17-18(飛行員)-19[16]，利用文中提出的算法，得到如圖4所示的節(jié)點重要度相似和排名，與介數(shù)中心性、度中心性、接近中心性指標(biāo)、等概率疊加隨機(jī)游走比較，結(jié)果如表2所示。

在四次恐怖劫持中，不等概率疊加隨機(jī)游走識別同節(jié)點度、接近中心性指標(biāo)、等概率疊加均識別出3名飛行員(5、8、13)，節(jié)點介數(shù)排序識別出1名，飛行員需要花費更多的資源培養(yǎng)，在劫持客機(jī)中是重要人員。上述算法在識別出的Top10節(jié)點中，度中心性可以識別出19名直接參與劫機(jī)的8名成員，其他方法次之；在Top15的節(jié)點中，度中心性、接近中心性和不等概率疊加隨機(jī)游走均識別出19名直接參與劫機(jī)的10名成員，高于介數(shù)中心性、等概率疊加隨機(jī)游走識別出的節(jié)點個數(shù)；Top19節(jié)點中，基于不等概率疊加隨機(jī)游走可以識別出19名直接參與劫機(jī)的14名成員，其他方法次之。從表4可知，文中提出的方法與標(biāo)準(zhǔn)排序結(jié)果相似性最大，顯著提高了排序精度。

圖4 恐怖襲擊網(wǎng)絡(luò)重要度排名Top19的節(jié)點相似和

表2 節(jié)點重要度比較(1)

續(xù)表2

科研合作網(wǎng)絡(luò)中網(wǎng)絡(luò)的節(jié)點表示曾在網(wǎng)絡(luò)科學(xué)領(lǐng)域發(fā)表過論文的科學(xué)家，連邊表示合作關(guān)系。文中考慮無向無權(quán)網(wǎng)絡(luò)，此數(shù)據(jù)集包含1 589個節(jié)點，2 742條邊，其中128個孤立節(jié)點，共包含268個連通集，文中提取極大連通子圖包含379個節(jié)點，974條邊。采用基于不等概率疊加隨機(jī)游走關(guān)鍵點識別算法選取重要性排名前5%的18個節(jié)點與度中心性、介數(shù)中心性、接近中心性、等概率疊加隨機(jī)游走方法進(jìn)行比較，結(jié)果如表3所示，文中提出的算法能夠通過Top5%的節(jié)點兩步轉(zhuǎn)移覆蓋節(jié)點率85%，低于介數(shù)中心性排序方法，高于節(jié)點度中心性、接近中心性和等概率疊加隨機(jī)游走方法。如表5所示，文中方法排序結(jié)果與標(biāo)準(zhǔn)排序之間相似性次于度中心性，高于等概率疊加隨機(jī)游走排序結(jié)果，能夠有效地識別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點。

USAir97網(wǎng)絡(luò)節(jié)點表示機(jī)場，邊表示航空路線，該數(shù)據(jù)集包含332個節(jié)點，2 126條邊，通過中心性算法找到交通通暢性影響較大的機(jī)場，進(jìn)行重點維護(hù)。表3通過比較不同中心性方法得到的Top10節(jié)點，不等概率疊加隨機(jī)游走方法與其他中心性方法得到Top10的差異較小，與度中心性識別重要節(jié)點相同，介數(shù)中心性差異為4個，與接近中心性差異為3個，等概率疊加隨機(jī)游走方法差異為1個。從表4可知，文中方法與SIR模型之間Kendall tau距離相似性明顯高于其他中心性方法，證明了該方法的有效性，排序精度高于其他中心性方法。

表3 節(jié)點重要度比較(2)

表4 USAir97節(jié)點重要度比較

表5 各中心性算法與SIR模型Kendall tau

對比分析各算法時間復(fù)雜度，度中心性算法時間復(fù)雜度為O(n)，介數(shù)中心性時間復(fù)雜度為O(n3)，接近中心性、等概率疊加隨機(jī)游走，文中算法時間復(fù)雜度為O(n2)。文中算法在時間復(fù)雜度一致的情況下，較等概率疊加隨機(jī)游走方法關(guān)鍵點識別的準(zhǔn)確性有很大提高。

4 結(jié)束語

針對復(fù)雜網(wǎng)絡(luò)中關(guān)鍵點識別問題，提出了一種基于不等概率疊加隨機(jī)游走的評估方法，引入Jaccard相似性指標(biāo)進(jìn)行不等概率隨機(jī)游走，結(jié)合疊加游走計算相似和在無向網(wǎng)絡(luò)中進(jìn)行關(guān)鍵點識別，綜合考慮節(jié)點間的相似性、兩步轉(zhuǎn)移到達(dá)節(jié)點、節(jié)點度信息及網(wǎng)絡(luò)中所處位置等信息。實驗證明，基于不等概率疊加隨機(jī)游走相似和在不增加時間復(fù)雜度的情況下，可以較高精度有效地識別關(guān)鍵節(jié)點。綜合實際網(wǎng)絡(luò)特點，不等概率隨機(jī)游走更好地考慮了隨機(jī)游走特點。在一定程度上說明不等概率隨機(jī)游走在無向網(wǎng)絡(luò)關(guān)鍵點識別是有效的，下一步是將不等概率隨機(jī)游走與點權(quán)相結(jié)合，并將其擴(kuò)展到有向加權(quán)網(wǎng)絡(luò)，進(jìn)行更深入研究。