王秋玲，賀僚僚，徐 宏，魏子昂，柯宇昊，官文英，朱璋元

(1.長(zhǎng)安大學(xué) 運(yùn)輸工程學(xué)院，陜西 西安 710064；2.中鐵一局集團(tuán)有限公司，陜西 西安 710054)

識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)是網(wǎng)絡(luò)科學(xué)的重要研究?jī)?nèi)容之一[1]。由于復(fù)雜網(wǎng)絡(luò)具有非同質(zhì)拓?fù)浣Y(jié)構(gòu)的本質(zhì)特征，少數(shù)關(guān)鍵節(jié)點(diǎn)失效就會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)的全局崩潰[2]。挖掘網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，對(duì)人們分析網(wǎng)絡(luò)拓?fù)湫再|(zhì)以及控制傳播過程具有重要意義。盡管關(guān)于復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的研究很多，但目前學(xué)術(shù)界對(duì)于關(guān)鍵節(jié)點(diǎn)的定義及其衡量指標(biāo)沒有統(tǒng)一的標(biāo)準(zhǔn)。關(guān)于關(guān)鍵節(jié)點(diǎn)的定義主要集中于如下3種[3]：社會(huì)網(wǎng)絡(luò)學(xué)者認(rèn)為，關(guān)鍵節(jié)點(diǎn)是對(duì)其他節(jié)點(diǎn)及整個(gè)網(wǎng)絡(luò)有顯著影響作用的節(jié)點(diǎn)；系統(tǒng)科學(xué)學(xué)者認(rèn)為，關(guān)鍵節(jié)點(diǎn)是指遭受攻擊后，使得網(wǎng)絡(luò)效率降低甚至癱瘓的重要性最高的一類節(jié)點(diǎn)；而信息傳播領(lǐng)域的學(xué)者則提出，關(guān)鍵節(jié)點(diǎn)是信息傳播能力最高的一類節(jié)點(diǎn)。與此對(duì)應(yīng)，關(guān)于衡量指標(biāo)也主要集中于3個(gè)方面[4]：一是節(jié)點(diǎn)的顯著性等價(jià)于節(jié)點(diǎn)的重要性；二是節(jié)點(diǎn)的破壞性等價(jià)于節(jié)點(diǎn)的重要性；三是節(jié)點(diǎn)的重要性取決于節(jié)點(diǎn)的傳播能力和鄰居節(jié)點(diǎn)的重要性。

衡量節(jié)點(diǎn)重要性常用的方法是基于節(jié)點(diǎn)屬性和位置提出的節(jié)點(diǎn)中心性算法[5]，包括度中心性、介數(shù)中心性、緊密度中心性、特征向量中心性、K-shell、Page Rank、結(jié)構(gòu)洞等[6-7]。上述方法已被應(yīng)用到社交網(wǎng)絡(luò)[8]、生物網(wǎng)絡(luò)[9]、交通網(wǎng)絡(luò)[10]、電力網(wǎng)絡(luò)[11]、信息網(wǎng)絡(luò)[12]、代謝網(wǎng)絡(luò)[13]等各種現(xiàn)實(shí)網(wǎng)絡(luò)分析中，并且取得了較為準(zhǔn)確的評(píng)價(jià)結(jié)果。但各類方法在使用過程中優(yōu)劣勢(shì)并存[14]，具體匯總梳理如表1所示。

在交通網(wǎng)絡(luò)中，從社會(huì)經(jīng)濟(jì)活動(dòng)層面來看，出行活動(dòng)將關(guān)鍵節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)緊密聯(lián)系在一起，使得節(jié)點(diǎn)重要性與其鄰居節(jié)點(diǎn)重要性顯著相關(guān)；從物理拓?fù)渚W(wǎng)絡(luò)層面來看，交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)是連接、支撐整個(gè)交通系統(tǒng)的重要橋梁，在全局網(wǎng)絡(luò)中居于樞紐地位。因此，為保證交通網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別結(jié)果能同時(shí)表征節(jié)點(diǎn)間的流量作用關(guān)系和節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)連通性的影響作用，交通網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別方法要綜合考慮節(jié)點(diǎn)局部屬性和全局屬性兩個(gè)因素[15]。但現(xiàn)有方法大多都不能滿足這一訴求，基于此，筆者將對(duì)這一問題進(jìn)行分析。

1 算法改進(jìn)

目前，對(duì)交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別算法的研究較多，大多都是在復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法基礎(chǔ)上進(jìn)行擴(kuò)展，從節(jié)點(diǎn)局部屬性角度或全局屬性角度對(duì)節(jié)點(diǎn)進(jìn)行評(píng)價(jià)，部分學(xué)者將兩者進(jìn)行結(jié)合，并運(yùn)用多種性能指標(biāo)來衡量節(jié)點(diǎn)的重要程度。例如，諶微微等[16]基于節(jié)點(diǎn)度值、接近中心性、中介中心性 3 個(gè)指標(biāo)評(píng)價(jià)軌道交通網(wǎng)絡(luò)節(jié)點(diǎn)的重要度，然后以重慶市軌道交通網(wǎng)絡(luò)為例對(duì)重要站點(diǎn)進(jìn)行分析；梁青槐等[17]結(jié)合主客觀集成賦權(quán)法思想，融合了度中心性、接近中心性和介數(shù)中心性指標(biāo)，以此構(gòu)建了城市軌道交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別模型。然而上述方法在評(píng)估交通網(wǎng)絡(luò)中的節(jié)點(diǎn)重要度時(shí)，不能說明節(jié)點(diǎn)負(fù)載流量差異對(duì)節(jié)點(diǎn)重要度產(chǎn)生的影響。因此，筆者將利用Page Rank的思想，融合網(wǎng)絡(luò)的結(jié)構(gòu)洞特征，用相鄰節(jié)點(diǎn)的結(jié)構(gòu)洞重要性指標(biāo)來表征交通網(wǎng)絡(luò)相鄰節(jié)點(diǎn)間的客流貢獻(xiàn)關(guān)系，體現(xiàn)節(jié)點(diǎn)的局部重要性。同時(shí)，Page Rank算法體現(xiàn)了交通節(jié)點(diǎn)在網(wǎng)絡(luò)中的全局重要性。綜合相鄰節(jié)點(diǎn)間的約束度和節(jié)點(diǎn)全局位置信息，筆者提出了一種基于“結(jié)構(gòu)洞”的Page Rank改進(jìn)算法。該算法不僅能同時(shí)表征交通節(jié)點(diǎn)的局部特性和全局環(huán)境，而且考慮到了節(jié)點(diǎn)流量、位置和鄰居節(jié)點(diǎn)重要性的影響作用，時(shí)間復(fù)雜度較低。而表1中其他算法的融合在兼顧局部特性和全局環(huán)境的基礎(chǔ)上，無法同時(shí)體現(xiàn)節(jié)點(diǎn)流量、節(jié)點(diǎn)位置的影響作用以及排序惟一、時(shí)間復(fù)雜度低的優(yōu)勢(shì)。

1.1 Page Rank算法

Page Rank算法是Google創(chuàng)始人Sergey Brin 和 Larry Page在構(gòu)建早期搜索系統(tǒng)原型時(shí)提出的鏈接分析算法。該算法不僅是谷歌網(wǎng)頁排序的關(guān)鍵技術(shù)，還被改進(jìn)應(yīng)用到其他領(lǐng)域。參考學(xué)術(shù)論文以引用量評(píng)估重要性的方法，Page Rank的基本思想是根據(jù)網(wǎng)頁的鏈接結(jié)構(gòu)來進(jìn)行排序[18]，被鏈接數(shù)量越多，網(wǎng)頁重要程度越高。同時(shí)，Page Rank算法還將指向目標(biāo)頁面的其他頁面自身重要度考慮在內(nèi)，認(rèn)為重要頁面對(duì)被鏈接頁面重要性的提升作用遠(yuǎn)遠(yuǎn)大于普通頁面。因此，網(wǎng)頁的重要性取決于指向它的其他網(wǎng)頁的數(shù)量和重要性。指向它的網(wǎng)頁的重要性越高，數(shù)量越多，則該網(wǎng)頁越重要，相應(yīng)的Page Rank值越高。計(jì)算方法如下所示：

(1)

Page Rank算法給出了網(wǎng)頁的全局重要性排序，不過其缺點(diǎn)在于無法體現(xiàn)主題的相關(guān)性，沒有區(qū)分頁面內(nèi)的導(dǎo)航鏈接、廣告鏈接和功能鏈接等，容易對(duì)廣告頁面有過高評(píng)價(jià)。也就是說，忽略了網(wǎng)絡(luò)中節(jié)點(diǎn)自身的屬性。從拓?fù)浣Y(jié)構(gòu)角度考慮，Page Rank算法弱化了局部屬性對(duì)節(jié)點(diǎn)的影響，從而使用戶通常以相等概率隨機(jī)跳轉(zhuǎn)到相鄰節(jié)點(diǎn)，然而實(shí)際生活中多數(shù)網(wǎng)絡(luò)均普遍具有異質(zhì)性特征，該方法在一定程度上對(duì)節(jié)點(diǎn)異質(zhì)性的體現(xiàn)不足[19]。

1.2 “結(jié)構(gòu)洞”理論

結(jié)構(gòu)洞理論最初由Ronald Burt提出，并應(yīng)用于社會(huì)網(wǎng)絡(luò)競(jìng)爭(zhēng)關(guān)系研究中。從社會(huì)學(xué)角度看，Burt 認(rèn)為結(jié)構(gòu)洞是“兩個(gè)行動(dòng)者之間的非冗余關(guān)系”。如圖1所示，D與A、B、C中的任意兩者之間的關(guān)系結(jié)構(gòu)就是一個(gè)結(jié)構(gòu)洞。對(duì)于A、B、D三者來說，A和B都與D有關(guān)，但是兩者之間卻不存在關(guān)系，相當(dāng)于有一個(gè)空洞，洞兩邊的聯(lián)系人可以帶來累加而非重疊的網(wǎng)絡(luò)收益，從而使占據(jù)結(jié)構(gòu)洞位置的個(gè)體獲得更多的競(jìng)爭(zhēng)優(yōu)勢(shì)與累加收益。從復(fù)雜網(wǎng)絡(luò)角度看，擁有較多結(jié)構(gòu)洞的網(wǎng)絡(luò)節(jié)點(diǎn)能夠獲取更關(guān)鍵的信息，更有利于信息的傳播[20]。

圖1 結(jié)構(gòu)洞示意圖

Burt提出，可以用網(wǎng)絡(luò)約束系數(shù)來衡量網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)之間的依賴關(guān)系以及網(wǎng)絡(luò)節(jié)點(diǎn)形成結(jié)構(gòu)洞時(shí)所受到的約束。約束系數(shù)越小，節(jié)點(diǎn)之間的依賴性越弱，則越有可能形成結(jié)構(gòu)洞，能力就越大。網(wǎng)絡(luò)約束系數(shù)的計(jì)算方法如下所示：

(2)

(3)

其中，Cij是i在j身上投資的精力，即約束度；Pij表示節(jié)點(diǎn)i為維持與節(jié)點(diǎn)j的鄰居關(guān)系所投入的精力占總精力的比例；Piq和Pqj分別是節(jié)點(diǎn)i，j與共同鄰居q維持關(guān)系投入的精力占其總精力的比例；Γ(i)表示i的鄰居集合；aij為

(4)

由于節(jié)點(diǎn)之間約束度越小，則表示兩節(jié)點(diǎn)間的交互能力越強(qiáng)，因此定義節(jié)點(diǎn)i與節(jié)點(diǎn)j之間依賴關(guān)系重要度指標(biāo)Lij為

Lij=1-Cij。

(5)

約束系數(shù)只衡量了節(jié)點(diǎn)與其最近鄰節(jié)點(diǎn)間的關(guān)系，沒有進(jìn)一步考慮鄰居節(jié)點(diǎn)與其余節(jié)點(diǎn)相連的拓?fù)浣Y(jié)構(gòu)對(duì)該節(jié)點(diǎn)的影響，該指標(biāo)不能發(fā)現(xiàn)一些重要的“橋接”節(jié)點(diǎn)[21]。

1.3 基于“結(jié)構(gòu)洞”的Page Rank算法改進(jìn)

根據(jù)以上分析，將局部指標(biāo)“結(jié)構(gòu)洞”和全局指標(biāo)Page Rank結(jié)合，可以同時(shí)彌補(bǔ)這兩種方法的缺陷。筆者提出一種基于“結(jié)構(gòu)洞”的Page Rank算法改進(jìn)方法，即ST-Page Rank算法。從網(wǎng)絡(luò)約束系數(shù)來看，交通網(wǎng)絡(luò)中的流量流動(dòng)時(shí)節(jié)點(diǎn)會(huì)將交通流按依賴關(guān)系大小分配給相鄰節(jié)點(diǎn)，同時(shí)依賴關(guān)系越強(qiáng)的鄰居節(jié)點(diǎn)將會(huì)得到更多的流量。

定義交通網(wǎng)絡(luò)中節(jié)點(diǎn)Vi的影響力指標(biāo)Ii為

(6)

其中，Lij表示交通節(jié)點(diǎn)Vi與Vj之間的依賴關(guān)系大小，n為交通網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)，Q為跳轉(zhuǎn)概率，Ij表示交通節(jié)點(diǎn)Vj的影響力指標(biāo)值，N(i)為節(jié)點(diǎn)Vi的鄰居節(jié)點(diǎn)集合。節(jié)點(diǎn)初始重要性為結(jié)構(gòu)洞指標(biāo)值。

ST-Page Rank算法的具體步驟如下所示。

算法1基于“結(jié)構(gòu)洞”和Page Rank關(guān)鍵節(jié)點(diǎn)的識(shí)別方法。

輸入：G=(V，E)。

輸出：rank list。

① for all connected nodesVi、Vj∈Vdo

② calculateCijusing the formula(2)

③ end for

④ for allCijbetween neighbor nodes ofVi、Vj∈Vdo

⑤ normalizeLijusing the formula(5)

⑥ end for

⑦ for allVi∈Vdo

⑧ calculateIibased on Page Rank algorithm and Constraint coefficient ratio obtained at the second of the algorithm using the formula(6)

⑨ rank list.put(Vi，Ii)

⑩ end for

2 實(shí)例仿真

2.1 仿真設(shè)計(jì)

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

選擇無向無權(quán)的美國航空網(wǎng)絡(luò)US Air[22]進(jìn)行驗(yàn)證。網(wǎng)絡(luò)詳細(xì)信息如表2所示。

表2中，網(wǎng)絡(luò)節(jié)點(diǎn)代表機(jī)場(chǎng)，網(wǎng)絡(luò)連邊表示機(jī)場(chǎng)間有直飛的航線。網(wǎng)絡(luò)結(jié)構(gòu)特征量包括節(jié)點(diǎn)數(shù)|v|、邊數(shù)|E|、平均度〈k〉、最大度kmax、平均聚類系數(shù)C、平均路徑長(zhǎng)度L和理論傳播閾值βth。

表2 網(wǎng)絡(luò)結(jié)構(gòu)特征信息

2.1.2 算法性能評(píng)估

在交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別研究中，很多學(xué)者利用信息傳播領(lǐng)域?qū)W者的觀點(diǎn)來驗(yàn)證節(jié)點(diǎn)重要度排序結(jié)果的可靠性。例如，文獻(xiàn)[23-24]中通過比較節(jié)點(diǎn)中心性算法排序結(jié)果和SIR模型排序結(jié)果的Kendall 相關(guān)系數(shù)值τ來評(píng)估算法的準(zhǔn)確性。故筆者選擇SIR模型和Kendall 相關(guān)系數(shù)評(píng)價(jià)ST-Page Rank算法的性能及有效性。

(1)SIR 模型

在SIR模型中，所有節(jié)點(diǎn)存在 3 種狀態(tài)：易感狀態(tài)S，指未受感染但缺乏免疫能力，容易被其他節(jié)點(diǎn)感染；感染狀態(tài)I，指感染節(jié)點(diǎn)以β的概率感染其他節(jié)點(diǎn)，以γ的概率恢復(fù)到免疫狀態(tài)；免疫狀態(tài)R，由感染狀態(tài)恢復(fù)且具有免疫能力，不會(huì)再次被感染。

將種子節(jié)點(diǎn)Vi經(jīng)t步感染后網(wǎng)絡(luò)中感染節(jié)點(diǎn)及恢復(fù)節(jié)點(diǎn)的平均數(shù)量定義為該節(jié)點(diǎn)的SIR傳播能力，用來評(píng)價(jià)節(jié)點(diǎn)的傳播重要性：

(7)

(2)Kendall相關(guān)系數(shù)

采用Kendall相關(guān)系數(shù)τ評(píng)價(jià)兩個(gè)序列的相關(guān)程度。在文中的兩個(gè)序列集合X，Y分別指通過 SIR 模型識(shí)別的關(guān)鍵節(jié)點(diǎn)排序結(jié)果和通過中心性方法得到的排序結(jié)果。τ的定義如下：

(8)

其中，X，Y表示兩個(gè)不同的序列，τ(X，Y)表示序列X和Y的肯德爾相關(guān)系數(shù)值，C為具有一致性排序順序的元素對(duì)數(shù)，D為具有不一致性排序順序的元素對(duì)數(shù)，T是排序向量中的元素個(gè)數(shù)。τ的取值在[-1，1]之間。τ=1，為完全正相關(guān)；τ=-1，為完全負(fù)相關(guān)；τ=0，為不相關(guān)。τ值越大，則兩個(gè)序列相似性越高；反之，相似性越低。

2.2 結(jié)果分析

為了驗(yàn)證上述算法的準(zhǔn)確性，在實(shí)驗(yàn)過程中選取度中心性(DC)、介數(shù)中心性(BC)、緊密中心性(CC)、特征向量中心性(EC)、K-shell分解法(Ks)、Page Rank(PR)以及結(jié)構(gòu)洞(ST)這7個(gè)經(jīng)典算法作為對(duì)照實(shí)驗(yàn)。在美國航空網(wǎng)絡(luò)中計(jì)算出文中算法以及另外7個(gè)傳統(tǒng)算法的排序結(jié)果，然后在特定的感染率β=βth=0.02，γ=0.01下進(jìn)行SIR傳播實(shí)驗(yàn)。利用式(7)和式(8)計(jì)算出SIR模型排序結(jié)果，將筆者提出的算法以及對(duì)照算法排序結(jié)果的肯德爾相關(guān)系數(shù)列在表3。τ值越大，則表明相關(guān)節(jié)點(diǎn)重要性識(shí)別方法越準(zhǔn)確。從表3的實(shí)驗(yàn)結(jié)果可以看出，筆者提出方法的肯德爾相關(guān)系數(shù)τ值高于其他7個(gè)經(jīng)典算法。因此，ST-Page Rank算法在識(shí)別網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)時(shí)具有一定優(yōu)越性。

表3 SIR傳播模型與各中心性指標(biāo)排序結(jié)果的肯德爾相關(guān)系數(shù)表

為了更好地驗(yàn)證算法的準(zhǔn)確性，減少感染率β對(duì)實(shí)驗(yàn)結(jié)果的影響，在實(shí)驗(yàn)過程中，β的取值范圍設(shè)置為0.01～0.10，分別計(jì)算不同的β下的肯德爾相關(guān)系數(shù)τ。實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

圖2 新算法與經(jīng)典局部屬性算法對(duì)比圖

圖3 新算法與經(jīng)典全局屬性算法對(duì)比圖

從圖2及圖3實(shí)驗(yàn)結(jié)果中可以得出，在美國航空網(wǎng)絡(luò)中，當(dāng)β取0.01時(shí)，結(jié)構(gòu)洞算法的識(shí)別效果最優(yōu)，緊跟其后的分別是K-shell、度中心性和新算法，介數(shù)中心性識(shí)別效果最差，介于它們之間的有接近中心性、特征向量中心性和Page Rank。此時(shí)，新算法的肯德爾系數(shù)值居于中間地位。當(dāng)β從0.01上升到0.02時(shí)，除特征向量中心性和Page Rank之外，其他算法的肯德爾系數(shù)都逐漸減小，且新算法的τ值排名從第4名迅速上升到第1名。之后，隨著β繼續(xù)增大到0.05，各算法在不同感染率下的肯德爾系數(shù)都有較大波動(dòng)，整體上呈現(xiàn)出先下降后上升的趨勢(shì)。其中，新算法的肯德爾系數(shù)整體上高于其他算法，識(shí)別效果最優(yōu)；特征向量中心性、結(jié)構(gòu)洞、Page Rank這3種算法的肯德爾系數(shù)較為接近，識(shí)別效果差異不大，但明顯優(yōu)于度中心性、接近中心性、K-shell和介數(shù)中心性。當(dāng)β從0.05上升到0.07時(shí)，各算法的肯德爾系數(shù)變化趨勢(shì)相似且較為穩(wěn)定，新算法的識(shí)別效果略遜于結(jié)構(gòu)洞。當(dāng)β從0.07上升到0.10時(shí)，各算法的識(shí)別效果并不穩(wěn)定。當(dāng)β取0.07和0.10時(shí)，K-shell識(shí)別效果最優(yōu)。當(dāng)β取0.08時(shí)，接近中心性識(shí)別效果最優(yōu)。當(dāng)β取0.09時(shí)，Page Rank識(shí)別效果最優(yōu)，介數(shù)中心性識(shí)別效果依然排在末位。

綜上所述，當(dāng)感染率β在0.02附近時(shí)，新算法明顯優(yōu)于其余7個(gè)經(jīng)典方法；當(dāng)感染率β較大時(shí)，新算法的值并不完全優(yōu)于其余算法，但與最優(yōu)算法差異不大。這充分說明了較一些經(jīng)典的關(guān)鍵節(jié)點(diǎn)識(shí)別算法，筆者提出的基于“結(jié)構(gòu)洞”的Page Rank改進(jìn)算法能更準(zhǔn)確地識(shí)別網(wǎng)絡(luò)中有影響力的節(jié)點(diǎn)。

3 總 結(jié)

筆者提出了一種局部特性與全局環(huán)境融合的交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別算法。該方法結(jié)合了“結(jié)構(gòu)洞”和“Page Rank”的優(yōu)點(diǎn)，同時(shí)考慮了節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)全局特征。為了驗(yàn)證所提算法的有效性，首先，選取7個(gè)經(jīng)典方法和筆者提出的算法進(jìn)行對(duì)比，在美國航空網(wǎng)絡(luò)中計(jì)算各種方法的排序結(jié)果；然后，利用 SIR傳播模型模擬不同感染率β下的傳播過程，使用肯德爾相關(guān)系數(shù)分別計(jì)算這8種算法的排序結(jié)果和SIR傳播模型得到的排序結(jié)果的相關(guān)性。實(shí)驗(yàn)結(jié)果表明，基于“結(jié)構(gòu)洞”的Page Rank改進(jìn)算法(ST-Page Rank)在交通網(wǎng)絡(luò)中能夠準(zhǔn)確地識(shí)別網(wǎng)絡(luò)中有影響力的節(jié)點(diǎn)。