基于不等概率疊加隨機游走關鍵點識別

寧 陽，武志峰，張 策

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

0 引 言

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

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

1 相關工作

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

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

2 不等概率疊加隨機方法

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

2.1 構建不等概率隨機游走轉移矩陣

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

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

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

無權無向圖：

(1)

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

算法主要步驟如下：

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

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

(2)

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

(3)

(4)

2.2 基于疊加效應的局部隨機游走

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

(5)

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

(6)

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

2.3 基于相似和的疊加隨機游走

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

公式如下所示：

(7)

算法流程如圖1所示。

圖1 算法流程

3 實驗結果與分析

3.1 SIR傳播模型

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

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

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

R:移除狀態(tài)，也稱免疫狀態(tài)或恢復狀態(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ù)上述分析，為了驗證文中提出的基于不等概率疊加隨機游走關鍵點識別方法的有效性，對9/11恐怖襲擊網(wǎng)絡[24]、科研合作網(wǎng)[25]、USAir97數(shù)據(jù)集進行仿真實驗，使用Python語言對算法進行實現(xiàn)，并與度中心性、介數(shù)中心性、接近中心性、等概率疊加隨機游走方法進行比較；對3個數(shù)據(jù)集基于SIR模型計算標準排序結果，計算各中心性算法與SIR的Kendall tau距離的差異；分析算法的時間復雜度。表1給出了這3個網(wǎng)絡的拓撲結構統(tǒng)計特征,其中n表示節(jié)點數(shù)，m表示邊數(shù)，表示節(jié)點平均度，kmax表示節(jié)點最大度，表示網(wǎng)絡節(jié)點間最短路徑平均數(shù)，C表示聚類系數(shù)，用來評估節(jié)點聚集成團的集聚程度；R表示同配系數(shù)，用來反映鄰接節(jié)點間的度相關性；H表示異質系數(shù)，衡量網(wǎng)絡中節(jié)點度分布的異質性[1,26]?？梢钥闯?個網(wǎng)絡具有明顯的小世界性，即高聚類系數(shù)和短的平均最短路徑長度，同時USAir97擁有明顯大度節(jié)點且具有高異質性，因此具有無標度網(wǎng)絡的特征。

表1 網(wǎng)絡拓撲結構的統(tǒng)計特征

9/11恐怖襲擊是伊斯蘭恐怖組織在美國發(fā)動的四次有組織的恐怖襲擊，19名恐怖分子劫持四架客機，該無向網(wǎng)絡結構共包含62個節(jié)點，148條邊，每個節(jié)點代表一名恐怖分子，包含劫持客機的19名恐怖分子及其同謀者。節(jié)點之間的邊代表恐怖分子之間的聯(lián)系。網(wǎng)絡結構如圖3所示，其中4次劫機行動中所在飛機的恐怖分子編號為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ù)中心性、度中心性、接近中心性指標、等概率疊加隨機游走比較，結果如表2所示。

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

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

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

續(xù)表2

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

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

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

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

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

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

4 結束語

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