局部特性與全局環(huán)境融合的節(jié)點排序算法

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

(1.長安大學 運輸工程學院，陜西 西安 710064；2.中鐵一局集團有限公司，陜西 西安 710054)

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

衡量節(jié)點重要性常用的方法是基于節(jié)點屬性和位置提出的節(jié)點中心性算法[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)實網(wǎng)絡(luò)分析中，并且取得了較為準確的評價結(jié)果。但各類方法在使用過程中優(yōu)劣勢并存[14]，具體匯總梳理如表1所示。

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

1 算法改進

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

1.1 Page Rank算法

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

(1)

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

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

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

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

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

(2)

(3)

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

(4)

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

Lij=1-Cij。

(5)

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

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

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

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

(6)

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

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

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

輸入：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 實例仿真

2.1 仿真設(shè)計

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

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

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

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

2.1.2 算法性能評估

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

(1)SIR 模型

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

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

(7)

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

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

(8)

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

2.2 結(jié)果分析

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

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

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

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

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

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

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

3 總 結(jié)

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