基礎設施網絡上PageRank算法的應用

李澤荃 郭作星 申 咪

1(華北科技學院 北京 101601)2(北京印刷學院 北京 102600)

0 引 言

諸如生物、社會、神經系統、計算機網絡、交通運輸等復雜系統[1-6]都可以用網絡來表示。其中：節點代表系統的各個實體；節點間的連邊表示實體間的關系。同樣，包括電力、通信、供水、供氣、航空、道路等基礎設施[7-11]也可以表示為復雜網絡，利用網絡的拓撲結構和動力學特征來研究其特性。

眾多學者[10,12]研究這些基礎設施網絡的統計特性和動力學過程，結果表明現實網絡中的節點地位或者位置不同，在擾動下網絡的破壞性也存在不同程度的差異。因此，針對基礎設施網絡中的節點重要性進行排序，識別網絡中的關鍵節點對于網絡抗毀性能的研究具有重要意義。而對于此項工作，復雜網絡中稱為最優滲流，目前也成為網絡科學的重要研究方向之一[13-14]。

關于網絡中重要節點的排序方法目前常用的有度中心性[15]、k-殼分解法[16]、信息指標[17]、介數中心性[18]以及它們的含權方法等。可以看出，網絡重要節點評價方法較多，各有側重。為便于針對實際問題選取合適的方法，任曉龍等[19]系統分析了復雜網絡領域具有代表性的30多種重要節點挖掘方法，并將其歸納為4個大類，即基于節點近鄰的排序方法、基于路徑的排序方法、基于特征向量的排序方法和基于節點移除和收縮的排序方法。

相對于其他類的排序方法，基于特征向量的方法不僅考慮了節點的鄰居數量，還考慮了其質量對節點重要性的影響，因此，近年來在理論和商業上都受到了廣泛關注。特別是谷歌搜索引擎的核心算法PageRank，除在網頁排序領域中的廣泛應用之外，很多學者也將其引入到其他方面，如識別社會網絡中的領導者[20]、科學論文引用分析[21]、水網中節點重要性的評價[10]等。

文獻[10]以山西大水網工程為網絡背景，研究了度中心、接近中心、介數中心和k-核分解四種單指標水網節點重要性排序方法的缺點，提出了基于TOPSIS的多屬性決策方法。并在考慮水網方向和級別差異的情況下，運用PageRank算法對有向賦權水網節點進行了重要性評價。或許對于像水網這樣的基礎設施網絡運用PageRank算法進行重要節點排序還很少見，文獻[10]的研究結果也沒有通過相關模型進行驗證。為解決此問題，本文將選4種重要節點排序方法進行了節點排序對比，并通過災害蔓延模型進行仿真驗證。

1 網絡原型及方法

文中采用的基礎實施網絡為美國航空交通控制網絡ATC(Air traffic control)，來源于美國的聯邦航空管理局飛行數據中心(FAA-NFDC)。在該網絡中，節點代表機場或者服務中心，連邊表示由NFDC推薦的首選飛行線路。ATC網絡為有向無標度網絡，共有1 226個節點、2 615條邊，網絡中節點的最大度為37，冪律常數為3.7。

文獻[19]通過分析目前學術界和工業界有關網絡重要節點排序的常用方法，并總結出4種基本類型。本文借鑒其思路，分別從4種類型的方法中各選擇一種，即度中心性(基于節點近鄰的排序方法)、介數中心性(基于路徑的排序方法)、殘余接近中心性(基于節點移除和收縮的排序方法)和PageRank方法(基于特征向量的排序方法)。下面針對這四種方法作簡要介紹：

(1) 度中心性：一個節點的重要性等價于該節點與其周圍節點建立直接聯系的能力，定義為節點的鄰邊數，記為:

DC(i)=ki/(n-1)

(1)

(2) 介數中心性：一個節點的重要性是通過該節點負載的信息或能量的大小來刻畫的，即經過該節點的最短路徑數越多，其就越重要，記為：

(2)

式中：gjk為節點j與節點k之間的所有最短路徑數目；gjk(i)為節點j與節點k之間經過節點i的最短路徑數目；(n-1)(n-2)/2為最大可能的節點介數。

(3) 殘余接近中心性：若一個節點的刪除增加了網絡的脆弱性，則該節點就越重要，用來衡量節點的移除對網絡帶來的影響，記為：

(3)

式中：djk(-i)為刪除節點i之后，節點j與節點k之間的最短距離。

(4) PageRank算法：最初主要用于網頁排序，一個頁面的重要性取決于指向它的其他頁面的數量和質量，如果一個頁面被較多的高質量頁面指向，則這個頁面的質量也比較高，記為：

(4)

另外，對于本文的研究思路，描述如下：首先，采用上面提到的4種排序方法對ATC網絡中所有的節點進行排序；然后，分別選取前5(Top-5)、前10(Top-10)和前20(Top-20)的節點運用災害蔓延動力學模型進行攻擊模擬，模擬時間為20步；最后，對比相變之后某個時間步時網絡中崩潰節點的總數，從模擬結果來看，t=10時已達到平衡。

2 災害蔓延動力學模型

在評價各種節點重要性挖掘算法時，傳統上一般采用傳染病模型，即SIS模型和SIR模型，如通信網絡中的病毒傳播[22]、電力網絡中的相繼故障[23]等。然而，對于猶如電力系統等基礎設施網絡，采用傳染病模型不能有效地描述災害在網絡中的傳播過程。信息和病毒在網絡中的傳播有很大的不同，病毒的傳播需要物理層面上的接觸，有關此問題的詳細討論可參考文獻[24]。自從Buzna等[6]提出災害蔓延動力學模型后，眾多學者開始轉向采用該模型進行基礎設施網絡上的災害傳播研究。因此，本文也采用該動力學模型作為排序算法的評價驗證模型。

對于基礎設施網絡，本文主要關注的是網絡的脆弱性，即網絡中某個(些)節點破壞后，這種破壞狀態或者災害在網絡中的傳播速度和傳播范圍。基于此，Buzna等[6]建立了一個普適性的災害傳播動力學模型，用于模擬災害在網絡中的傳播過程。

假定一個有向網絡G=(N,S)包含節點i∈N:={1,2,…,n}和邊(i,j)N×N，它們分別代表系統的節點和各節點之間的相互關系；xi表示節點的屬性值，當xi=0時表示節點處于穩定狀態，當xi偏離零時表示節點發生破壞。因此，節點關于時間的演化動力學模型可以表示為：

(5)

(6)

(7)

該動力學方程包括三個部分：式(5)等號右邊第一項表示節點的自我修復功能；第二項表示節點的災害蔓延機理；第三項表示節點的內部隨機噪聲。其中：1/τ為節點的自我修復速度；Mij為節點i對節點j的影響程度；tij為節點i和節點j之間的影響延遲時間；β為傳播過程中的阻尼作用。式(6)為Sigmoid函數，α為定值，θi為節點i的閾值。式(7)為節點i的出度函數，反映節點i對其他節點的影響程度，oi為出度值，a和b為定值。

3 結果分析

按照上述思路，本文首先給出4種排序方法的排序結果，詳細情況見表1。可以看出，對于前20個重要節點，度中心性和介數中心性的排序重合度較大，而殘余接近中心性和PageRank算法與前兩者交叉性非常小，特別是對于PageRank算法，前5個重要節點與其他三種方法完全不同。

表1 節點排序結果(Top-20)

為了更好地理解PageRank排序算法下節點的特性，這里給出3個節點的鄰居數量及其質量示意圖，具體如圖1所示。可以看出，排序靠前的節點除鄰邊數目較多以外，其鄰居的質量更好，或者說其鄰居的鄰居更多。從原理上來講，PageRank算法屬于基于特征向量的方法，其不僅考慮到鄰居的數量，而且還考慮到鄰居的質量對節點重要性的影響。這與圖1所展現的特性剛好吻合。

(a) 節點52，排序第9位

(b) 節點266，排序第20位

(c) 節點312，排序第31位圖1 PageRank算法下節點鄰居數量及質量情況(圓的大小表示節點的鄰邊數)

表1已經給出了4種算法的重要節點排序結果。本文通過災害蔓延動力學模型進行模擬仿真，對算法的排序結果進行評價驗證，具體結果如圖2所示。圖2(a)中，PageRank算法和度中心性方法的模擬仿真結果基本類似，相比其他方法，特別是度中心性排序方法，PageRank算法的優勢還不夠顯著。但隨著增加排序節點數，如圖2中的(b)和(c)，運用PageRank得出的排序節點模擬仿真后，網絡中的崩潰節點累積數逐漸增加，例如圖2(c)中的PageRank已經遠遠超過介數中心性。因此，可以說明采用PageRank算法求解出的排序節點對網絡的影響較大。

(a) 前5個重要節點

(b) 前10個重要節點

(c) 前20個重要節點圖2 4種方法獲得的重要節點的傳播影響力比較

4 結 語

本文在一個實際的航空交通基礎設施網絡(US Air traffic control)上對比了度中心性、介數中心性、殘余接近中心性和PageRank4種重要節點排序算法的排序結果，并通過災害蔓延動力學模型進行了模擬驗證。結果表明，PageRank算法可以用于進行基礎設施網絡上的重要節點排序，與其他排序方法相比，它使得網絡最終的崩潰節點數始終保持最多，說明PageRank算法擁有比其他方法具有更好的重要節點識別能力。