李澤荃 郭作星 申 咪

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

0 引 言

諸如生物、社會、神經(jīng)系統(tǒng)、計算機(jī)網(wǎng)絡(luò)、交通運(yùn)輸?shù)葟?fù)雜系統(tǒng)[1-6]都可以用網(wǎng)絡(luò)來表示。其中：節(jié)點代表系統(tǒng)的各個實體；節(jié)點間的連邊表示實體間的關(guān)系。同樣，包括電力、通信、供水、供氣、航空、道路等基礎(chǔ)設(shè)施[7-11]也可以表示為復(fù)雜網(wǎng)絡(luò)，利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和動力學(xué)特征來研究其特性。

眾多學(xué)者[10,12]研究這些基礎(chǔ)設(shè)施網(wǎng)絡(luò)的統(tǒng)計特性和動力學(xué)過程，結(jié)果表明現(xiàn)實網(wǎng)絡(luò)中的節(jié)點地位或者位置不同，在擾動下網(wǎng)絡(luò)的破壞性也存在不同程度的差異。因此，針對基礎(chǔ)設(shè)施網(wǎng)絡(luò)中的節(jié)點重要性進(jìn)行排序，識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點對于網(wǎng)絡(luò)抗毀性能的研究具有重要意義。而對于此項工作，復(fù)雜網(wǎng)絡(luò)中稱為最優(yōu)滲流，目前也成為網(wǎng)絡(luò)科學(xué)的重要研究方向之一[13-14]。

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

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

文獻(xiàn)[10]以山西大水網(wǎng)工程為網(wǎng)絡(luò)背景，研究了度中心、接近中心、介數(shù)中心和k-核分解四種單指標(biāo)水網(wǎng)節(jié)點重要性排序方法的缺點，提出了基于TOPSIS的多屬性決策方法。并在考慮水網(wǎng)方向和級別差異的情況下，運(yùn)用PageRank算法對有向賦權(quán)水網(wǎng)節(jié)點進(jìn)行了重要性評價?；蛟S對于像水網(wǎng)這樣的基礎(chǔ)設(shè)施網(wǎng)絡(luò)運(yùn)用PageRank算法進(jìn)行重要節(jié)點排序還很少見，文獻(xiàn)[10]的研究結(jié)果也沒有通過相關(guān)模型進(jìn)行驗證。為解決此問題，本文將選4種重要節(jié)點排序方法進(jìn)行了節(jié)點排序?qū)Ρ?，并通過災(zāi)害蔓延模型進(jìn)行仿真驗證。

1 網(wǎng)絡(luò)原型及方法

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

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

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

2 災(zāi)害蔓延動力學(xué)模型

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

對于基礎(chǔ)設(shè)施網(wǎng)絡(luò)，本文主要關(guān)注的是網(wǎng)絡(luò)的脆弱性，即網(wǎng)絡(luò)中某個(些)節(jié)點破壞后，這種破壞狀態(tài)或者災(zāi)害在網(wǎng)絡(luò)中的傳播速度和傳播范圍。基于此，Buzna等[6]建立了一個普適性的災(zāi)害傳播動力學(xué)模型，用于模擬災(zāi)害在網(wǎng)絡(luò)中的傳播過程。

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

(5)

(6)

(7)

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

3 結(jié)果分析

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

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

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

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

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

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

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

(a) 前5個重要節(jié)點

(b) 前10個重要節(jié)點

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

4 結(jié) 語

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