基于改進LeaderRank算法的高速鐵路網(wǎng)絡(luò)關(guān)鍵站點識別方法研究

陳錦渠，劉 杰，殷 勇，孫靖翔

基于改進LeaderRank算法的高速鐵路網(wǎng)絡(luò)關(guān)鍵站點識別方法研究

陳錦渠，劉 杰，殷 勇，孫靖翔

（1. 西南交通大學(xué)，交通運輸與物流學(xué)院，成都 611756；2. 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，成都 611756；3. 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室，成都 611756）

綜合運用多種方法研究了高鐵網(wǎng)絡(luò)關(guān)鍵站點的識別問題，分別基于站點度值、站點介數(shù)及改進LeaderRank算法識別了高鐵網(wǎng)絡(luò)中的關(guān)鍵站點, 采用改進SIR模型模擬關(guān)鍵站點列車運行晚點后全網(wǎng)站點列車的運行晚點情況, 結(jié)合晚點情況對比分析了不同關(guān)鍵站點識別方法的準(zhǔn)確性及有效性。研究結(jié)果表明, 改進LeaderRank算法能有效克服傳統(tǒng)識別方法的局限性, 綜合利用站點局部信息及網(wǎng)絡(luò)全局信息進行關(guān)鍵站點的識別，發(fā)現(xiàn)2030年中國高鐵網(wǎng)絡(luò)中最重要的站點是長沙, 最重要的地區(qū)是西南地區(qū)?？焖儆行У貙﹃P(guān)鍵站點進行識別和防護, 對于保證網(wǎng)絡(luò)的正常運營及提高網(wǎng)絡(luò)應(yīng)對威脅的能力具有重要意義。

改進LeaderRank算法；高速鐵路網(wǎng)絡(luò)；關(guān)鍵站點；度值；介數(shù)；SIR模型

0 引 言

截至2017年底，中國高速鐵路（以下簡稱：高鐵）營業(yè)里程達到了2.5萬km，高鐵以其快速、綠色、便捷舒適的優(yōu)點，在旅客中長距離運輸中發(fā)揮著重要的作用。高鐵的日常運營與站點密切相關(guān)，高鐵網(wǎng)絡(luò)的關(guān)鍵站點表示對網(wǎng)絡(luò)功能具有重大影響的站點，一旦關(guān)鍵站點失效，將有可能導(dǎo)致運輸網(wǎng)絡(luò)的癱瘓。因此，識別高鐵網(wǎng)絡(luò)的關(guān)鍵站點對于保證網(wǎng)絡(luò)正常運營及提升網(wǎng)絡(luò)應(yīng)對威脅的能力具有重要意義。

節(jié)點重要度是用于衡量節(jié)點重要程度的指標(biāo)，節(jié)點重要度越高，節(jié)點在網(wǎng)絡(luò)中的重要程度越大。目前研究學(xué)者主要從以下四方面來計算節(jié)點的重要度，并識別網(wǎng)絡(luò)的關(guān)鍵站點：第一類研究中，研究學(xué)者采用站點度值、半局部中心性及節(jié)點重要度評價矩陣等作為站點重要度指標(biāo)，并結(jié)合相應(yīng)領(lǐng)域的實際網(wǎng)絡(luò)驗證了所建立指標(biāo)的有效性[1-4]；第二類研究著重強調(diào)節(jié)點在節(jié)點間連接路徑上所發(fā)揮的作用，建立了介數(shù)中心性、接近中心性等節(jié)點重要度指標(biāo)[5, 6]；第三類研究通過移除和收縮相應(yīng)的節(jié)點，采用網(wǎng)絡(luò)凝聚度等作為指標(biāo)，衡量網(wǎng)絡(luò)遭受破壞前后指標(biāo)的變化情況來計算站點重要度，并識別關(guān)鍵站點[7, 8]；第四類研究中，研究學(xué)者在計算節(jié)點重要度時，不僅考慮了鄰居節(jié)點數(shù)量的影響，還考慮了鄰居節(jié)點質(zhì)量對節(jié)點重要度的影響[9, 10]。

分析文獻可知，現(xiàn)有節(jié)點重要度計算方法存在未全面利用網(wǎng)絡(luò)信息、引入主觀因素權(quán)重、算法時間復(fù)雜度高等缺點，這些缺點影響了識別結(jié)果的準(zhǔn)確性。對比其他識別方法，LeaderRank算法[11]能全面利用網(wǎng)絡(luò)信息，不需要人為干預(yù)，具有魯棒性強和收斂速度快的優(yōu)點，識別結(jié)果具有較高的準(zhǔn)確性。因此，本文在構(gòu)建高鐵網(wǎng)絡(luò)的基礎(chǔ)上，選取站點度值、站點介數(shù)及改進LeaderRank算法的計算結(jié)果作為高鐵網(wǎng)絡(luò)站點重要度，結(jié)合站點重要度識別網(wǎng)絡(luò)關(guān)鍵站點，最后結(jié)合改進SIR模型模擬全網(wǎng)站點的晚點情況來分析關(guān)鍵站點識別結(jié)果的準(zhǔn)確性。

1 關(guān)鍵站點識別

1.1 構(gòu)建高鐵網(wǎng)絡(luò)

構(gòu)建高鐵網(wǎng)絡(luò)時，以城市為站點，即若某城市存在多個高鐵車站，則將多個車站合并為一個站點（例如，將北京站、北京西站、北京南站及北京北站合并為北京站）。結(jié)合2016年國家發(fā)改委發(fā)布的《中長期鐵路網(wǎng)規(guī)劃》，構(gòu)建2030年中國高鐵網(wǎng)絡(luò)拓撲結(jié)構(gòu)，如圖1所示[12]，所構(gòu)建的高鐵網(wǎng)絡(luò)包含386個站點、547條邊，對站點進行編號得到站點鄰接矩陣及站間鄰接距離矩陣。

圖1 2030年中國高鐵網(wǎng)絡(luò)

1.2 基于拓撲結(jié)構(gòu)的關(guān)鍵站點識別

1.2.1 度中心性

站點的度反映與站點直接相連的站點數(shù)量，度值越大說明站點直接相連的站點越多，站點在高鐵網(wǎng)絡(luò)中的重要程度就越高。根據(jù)站點度值確定2030年中國高鐵網(wǎng)絡(luò)最重要的五個站點如表1所示。

表1 基于站點度值的高鐵網(wǎng)絡(luò)最重要的五個站點

Tab.1 The five most important stations in the high-speed railway network based on stations’ degree

由表1可知，合肥為2030年高鐵網(wǎng)絡(luò)中度值最大的站點，這是因為合肥地處東部發(fā)達地區(qū)，位于京滬、京港（臺）及沿江通道的銜接處，連接著多條高鐵線路，站點周邊線路密集程度高。但對合肥所連接的高鐵線路進行分析發(fā)現(xiàn)，銜接線路多為城際線路，而城際線路運輸能力有限，僅承擔(dān)區(qū)域內(nèi)部的客流交換任務(wù)。說明雖然合肥的度值很大，但只能反映合肥在局部區(qū)域的重要程度，無法從全局角度反映合肥的重要程度。因此通過度值識別網(wǎng)絡(luò)中的關(guān)鍵站點時，不能保證識別結(jié)果的準(zhǔn)確性。

1.2.2 介數(shù)中心性

站點介數(shù)被定義為網(wǎng)絡(luò)所有最短路徑中經(jīng)過該站點的數(shù)目占全網(wǎng)最短路徑總數(shù)的比例，站點介數(shù)越大說明該站點所能影響的最短路徑越多，站點在高鐵網(wǎng)絡(luò)中的重要程度就越大。根據(jù)站點介數(shù)確定2030年中國高鐵網(wǎng)絡(luò)最重要的五個站點如表2所示。

表2 基于站點介數(shù)的高鐵網(wǎng)絡(luò)最重要的五個站點

Tab.2 The five most important stations in the high-speed railway network based on stations’ betweenness

分析表2可得，天津是2030年高鐵網(wǎng)絡(luò)中介數(shù)最大的站點，說明通過天津的最短路徑數(shù)目最多。這是因為天津位于京滬通道和沿海通道的交點，是連接?xùn)|部和東北地區(qū)的樞紐。但進一步分析發(fā)現(xiàn)，天津地處渤海灣地區(qū)，受限于地理位置的原因，天津所銜接的高鐵線路較少，線路密集程度較低。說明通過介數(shù)識別關(guān)鍵站點時，并未考慮站點的局部信息，識別結(jié)果存在誤差，不能保證識別結(jié)果的準(zhǔn)確性。

1.3 改進LeaderRank算法

利用LeaderRank算法識別有向網(wǎng)絡(luò)關(guān)鍵節(jié)點的主要步驟為如下。

1.4 改進LeaderRank算法的識別結(jié)果

結(jié)合改進LeaderRank算法識別2030年高鐵網(wǎng)絡(luò)的關(guān)鍵站點，根據(jù)站點重要度值，繪制得到圖2所示的站點重要度分布圖。

圖2 站點重要度

根據(jù)計算結(jié)果對站點重要度進行排序，得到2030年中國高鐵網(wǎng)絡(luò)最重要的五個站點如表3所示。根據(jù)表3可得，長沙是2030年高鐵網(wǎng)絡(luò)中最重要的站點，這是因為長沙是京港澳、滬昆及廈渝通道的交點，同時站點周圍還連接著武漢、貴陽等重要度高的站點；隨著“八縱八橫”網(wǎng)絡(luò)的建成，貴陽將成為西南地區(qū)與東部、北部地區(qū)聯(lián)系的樞紐，是網(wǎng)絡(luò)中僅次于長沙的重要站點；作為19個綜合鐵路樞紐之一的成都，是西南地區(qū)與西北及中部地區(qū)聯(lián)系的主要站點，銜接著多個方向，具有較高的影響力；武漢位于“八縱八橫”網(wǎng)絡(luò)的中心，是沿江通道與京港澳通道的銜接點，是大量東西向、南北向乘客的必經(jīng)站點；西安是西北地區(qū)對外銜接的關(guān)鍵站點，是路橋、京昆及包海通道的交點，具有十分重要的樞紐作用。

表3 基于站點重要度的高鐵網(wǎng)絡(luò)最重要的五個站點

Tab.3 The five most important stations in the high-speed railway network based on station’s importance

根據(jù)站點地理區(qū)位信息將站點按地區(qū)進行分類，計算不同地區(qū)所含站點數(shù)量及站點重要度均值，計算結(jié)果如表4所示。分析表4可知，2030年西南地區(qū)的站點重要度均值最大，這是因為呼南通道等八大高鐵主通道以西南地區(qū)為終點，地區(qū)線路等級高，線路稠密；同時西南地區(qū)擁有成都、重慶及貴陽等綜合鐵路樞紐，多核心站點的存在顯著提高了該地區(qū)站點的重要度。東北地區(qū)的站點重要度均值最小，主要原因在于東北地區(qū)的高鐵主通道較少，線路密集程度不高，線路空間分布不均勻，北部高鐵線路稀疏南部稠密；同時東北地區(qū)僅有沈陽這一綜合鐵路樞紐，核心站點少，導(dǎo)致整個地區(qū)站點的重要度偏低。

表4 地區(qū)重要度

Tab.4 Regional importance

2 站點傳播能力仿真

2.1 SIR模型

在高鐵復(fù)雜的運輸環(huán)境下，高鐵列車運行過程中不可避免地會受到自然災(zāi)害、線網(wǎng)故障等突發(fā)事件的影響，從而導(dǎo)致列車發(fā)生運行晚點事件。運行晚點事件會以一定的概率傳播給其他站點，造成其他站點運行的列車也發(fā)生運行晚點；同時在某站點運行晚點的列車也有一定的概率轉(zhuǎn)為正點，轉(zhuǎn)為正點運行的列車將不再傳遞列車運行晚點信息。上述過程類似于傳染病的傳播，列車晚點信息類似于病毒[14]，可以運用SIR（Susceptible Infected Recovered，SIR）模型[15]模擬全網(wǎng)列車的運行晚點情況。

SIR模型是經(jīng)典的傳染病動力學(xué)模型，能夠有效模擬網(wǎng)絡(luò)受事件影響的情況。在模型中，“S”表示易感染者，即能被感染者感染的人。“I”表示感染者，即攜帶病毒的人。“R”表示免疫者，即不攜帶病毒且不會被感染者感染的人。一定概率條件下，易感染者會變?yōu)楦腥菊?，感染者會變?yōu)槊庖哒撸W(wǎng)絡(luò)的傳播能力可以用網(wǎng)絡(luò)中被感染人數(shù)的占比來表示。經(jīng)典SIR模型的計算公式為：

step2迭代循環(huán)，計算結(jié)果。根據(jù)改進SIR模型，在傳播時間步長范圍內(nèi)運行仿真，計算每個時間步長內(nèi)發(fā)生列車運行晚點事件的站點數(shù)量。

2.2 仿真結(jié)果及分析

圖3 站點傳播晚點能力仿真結(jié)果

分析圖3可知，站點重要度越高的站點發(fā)生運行晚點事件，晚點信息所能傳播的站點越多，說明此類站點具有更強的傳播能力，在網(wǎng)絡(luò)中具有更高的重要程度，一定程度上說明了改進LeaderRank算法識別結(jié)果具有更高的準(zhǔn)確性。分析長沙、貴陽及成都的站點傳播晚點能力曲線可以發(fā)現(xiàn)，時間步長超過一定值時，發(fā)生列車運行晚點事件的站點數(shù)量迅速增加，這將對高鐵網(wǎng)絡(luò)列車的正點運行產(chǎn)生巨大的影響。換言之，如果能在較短時間內(nèi)有效解決列車運行晚點問題，則能有效縮小列車運行晚點信息傳播的范圍，將列車運行晚點所造成的損失控制在最小。分析SIR模型相關(guān)參數(shù)可知，加強高鐵列車運輸組織，降低站點傳播列車運行晚點信息的概率，以及科學(xué)調(diào)度指揮，保證充分的列車運行時間冗余，都能達到有效縮小列車運行晚點信息傳播范圍的目的。

2.3 識別方法比較

利用改進SIR模型對基于站點度值、站點介數(shù)及改進LeaderRank算法所識別的關(guān)鍵站點進行站點傳播晚點能力仿真，分別設(shè)置列車在每種識別方法得到的5個關(guān)鍵站點發(fā)生列車運行晚點事件，計算每個時間步長內(nèi)發(fā)生列車運行晚點事件的站點數(shù)量的平均值。平均值越大，該方法識別關(guān)鍵站點的準(zhǔn)確性越高，仿真結(jié)果如圖4所示。

圖4 不同識別方法對比分析

分析圖4可得，當(dāng)傳播時間步長大于25時，基于改進LeaderRank算法所識別的5個關(guān)鍵站點傳播列車運行晚點信息的能力最大，說明綜合利用節(jié)點局部信息及網(wǎng)絡(luò)全局信息的改進LeaderRank算法所識別的關(guān)鍵站點在網(wǎng)絡(luò)中具有更大的影響力，識別結(jié)果具有更高的準(zhǔn)確程度；基于度值所識別的5個關(guān)鍵站點傳播列車運行晚點信息的能力最小，這是因為度值只利用了節(jié)點的局部信息，網(wǎng)絡(luò)信息利用程度不高，識別結(jié)果的準(zhǔn)確性較差。對比三條曲線可以發(fā)現(xiàn)，綜合利用網(wǎng)絡(luò)信息越多的識別方法，對應(yīng)識別結(jié)果具有更高的準(zhǔn)確性。因此，在進行高鐵網(wǎng)絡(luò)關(guān)鍵站點識別時，應(yīng)充分利用節(jié)點的局部信息及網(wǎng)絡(luò)的全局信息，以提高識別結(jié)果的準(zhǔn)確性。

3 結(jié) 論

（1）利用改進LeaderRank算法計算2030年中國高鐵網(wǎng)絡(luò)站點的重要度，并識別了網(wǎng)絡(luò)中的關(guān)鍵站點。識別結(jié)果表明：長沙是最重要的站點，西南地區(qū)是最重要的地區(qū)。通過對比不同識別方法的識別結(jié)果，發(fā)現(xiàn)相比于基于節(jié)點特性的傳統(tǒng)關(guān)鍵站點方法，改進LeaderRank算法的識別結(jié)果具有更高的準(zhǔn)確性。

（2）利用改進SIR模型對站點的晚點信息傳播能力進行仿真，發(fā)現(xiàn)列車在關(guān)鍵站點發(fā)生晚點時將會對整個高鐵網(wǎng)絡(luò)列車的正點運行產(chǎn)生巨大影響。因此提高對關(guān)鍵站點的關(guān)注力度，科學(xué)調(diào)度指揮，是保證高鐵網(wǎng)絡(luò)正常運輸?shù)挠行Т胧?/p>

（3）城市的發(fā)達程度決定站點所承擔(dān)的客流量，客流量越大的站點，在網(wǎng)絡(luò)全局的重要度越大。本文只從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)角度對關(guān)鍵站點進行識別，未考慮站點及線路所承擔(dān)的客運量，如何將網(wǎng)絡(luò)的客運量與LeaderRank算法相結(jié)合，將是接下來所要研究的方向。

[1] LIU B, LI Z, CHEN X, et al. Recognition and vulnerability analysis of key nodes in power grid based on complex network centrality[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2017, 65(3): 346-350.

[2] 于寶, 馮春, 朱倩, 等. 中國高速鐵路網(wǎng)絡(luò)脆弱性分析[J]. 中國安全科學(xué)學(xué)報, 2017, 27(9): 110-115.

[3] 張錦, 秦東. 快遞企業(yè)配送網(wǎng)絡(luò)的魯棒性及其提升對策研究[J]. 交通運輸工程與信息學(xué)報, 2018, 16(3): 7-13+58.

[4] 王露, 郭強, 劉建國. 基于加權(quán)方法的節(jié)點重要性度量[J]. 計算機應(yīng)用研究, 2018, 35(5): 1426-1428.

[5] JIANG L, JING Y, HU S, et al. Identifying Node Importance in a Complex Network Based on Node Bridging Feature[J]. Applied Sciences, 2018, 8(10): 1914-1-1914-14.

[6] OPSAHL T. Node centrality in weighted networks: generalizing degree and shortest paths[J]. Social Networks, 2010, 32(3): 245-251.

[7] 王班, 馬潤年, 王剛, 等. 加權(quán)網(wǎng)絡(luò)節(jié)點重要性評估的改進節(jié)點收縮法[J]. 計算機應(yīng)用研究, 2016, 33(7): 2122-2124.

[8] 劉建強, 蘭巨龍, 鄔江興. 基于節(jié)點疏遠方法的網(wǎng)絡(luò)節(jié)點重要性評價[J]. 計算機工程與科學(xué), 2011, 33(3): 13-17.

[9] LI K, HE Y. Evaluating nodes importance in complex network based on PageRank algorithm[C]//AIP Conference Proceedings. AIP Publishing, 2018, 1955(1): 040122-1- 040122-4.

[10] 許評, 李玉鵬, 莫宇迪, 等. 基于復(fù)雜網(wǎng)絡(luò)的復(fù)雜機械產(chǎn)品關(guān)鍵零件識別[J]. 組合機床與自動化加工技術(shù), 2018(10): 51-54.

[11] Lü L, ZHOU T. Link prediction in complex networks: A survey[J]. Physica A: statistical mechanics and its applications, 2011, 390(6): 1150-1170.

[12] 國家發(fā)展和改革委員會, 交通運輸部, 中國鐵路總公司. 中長期鐵路網(wǎng)規(guī)劃[EB/OL]. http: //www. ndrc. gov. cn/zcfb/zcfbtz/201607/t20160720_811696. html.

[13] 黃德才, 戚華春. PageRank算法研究[J]. 計算機工程, 2006(4): 145-146, 162.

[14] 殷勇, 劉杰, 劉慶. 基于SIR模型車站晚點傳播能力仿真研究[J]. 綜合運輸, 2017, 39(7): 60-65, 84.

[15] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of mathematical sociology, 1972, 2(1): 113-120.

Research on the Identification Method of Key Stations in the High-speed Railway Network Based on the Improved LeaderRank Algorithm

CHEN Jin-qu，LIU Jie，YIN Yong，SUN Jing-xiang

(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu 611756, China; 3. National Engineering Laboratory of Integrated Transportation Big Data Application Technology, Chengdu 611756, China)

The key stations of high-speed railway network are identified by multiple methods here, high-speed railway network’s key stations are identified by their degree, betweenness and the improved LeaderRank algorithm. The propagation of train late in the network due to delays at key stations is simulated by improved SIR model, the accuracy and effectiveness of different methods are demonstrated based on the simulation results. The result shows that the improved LeaderRank algorithm can effectively overcome the limitations of traditional identification methods. It can use both local information of stations and global information of the network to identify key stations comprehensively. The identification result shows that Changsha and Southwest of China are the most important station and region, respectively, in China’s 2030 high-speed railway network. The result also reveals that rapid, effective identification and protection of key stations is immensely significant to ensure normal operation of the network and improve the network’s ability to overcome threats.

improved LeaderRank algorithm; high-speed railway network; key stations; degree; betweenness; SIR (Susceptive-Infected-Removed) model

U291.3

A

10.3969/j.issn.1672-4747.2020.01.011

1672-4747（2020）01-0083-08

2018-12-02

國家重點研發(fā)計劃項目（2017YFB1200701）

陳錦渠（1995—）；男，西南交通大學(xué)碩士研究生，研究方向：交通運輸規(guī)劃與管理，E-mail：Chengjingqu@my.swjtu.edu.cn

陳錦渠，劉杰，殷勇，等. 基于改進LeaderRank算法的高速鐵路網(wǎng)絡(luò)關(guān)鍵站點識別方法研究[J]. 交通運輸工程與信息學(xué)報，2020，18（1）：83-90.

（責(zé)任編輯：劉娉婷）