基于改进LeaderRank算法的高速铁路网络关键站点识别方法研究

陈锦渠，刘 杰，殷 勇，孙靖翔

基于改进LeaderRank算法的高速铁路网络关键站点识别方法研究

陈锦渠，刘 杰，殷 勇，孙靖翔

（1. 西南交通大学，交通运输与物流学院，成都 611756；2. 综合交通运输智能化国家地方联合工程实验室，成都 611756；3. 综合交通大数据应用技术国家工程实验室，成都 611756）

综合运用多种方法研究了高铁网络关键站点的识别问题，分别基于站点度值、站点介数及改进LeaderRank算法识别了高铁网络中的关键站点, 采用改进SIR模型模拟关键站点列车运行晚点后全网站点列车的运行晚点情况, 结合晚点情况对比分析了不同关键站点识别方法的准确性及有效性。研究结果表明, 改进LeaderRank算法能有效克服传统识别方法的局限性, 综合利用站点局部信息及网络全局信息进行关键站点的识别，发现2030年中国高铁网络中最重要的站点是长沙, 最重要的地区是西南地区。快速有效地对关键站点进行识别和防护, 对于保证网络的正常运营及提高网络应对威胁的能力具有重要意义。

改进LeaderRank算法；高速铁路网络；关键站点；度值；介数；SIR模型

0 引 言

截至2017年底，中国高速铁路（以下简称：高铁）营业里程达到了2.5万km，高铁以其快速、绿色、便捷舒适的优点，在旅客中长距离运输中发挥着重要的作用。高铁的日常运营与站点密切相关，高铁网络的关键站点表示对网络功能具有重大影响的站点，一旦关键站点失效，将有可能导致运输网络的瘫痪。因此，识别高铁网络的关键站点对于保证网络正常运营及提升网络应对威胁的能力具有重要意义。

节点重要度是用于衡量节点重要程度的指标，节点重要度越高，节点在网络中的重要程度越大。目前研究学者主要从以下四方面来计算节点的重要度，并识别网络的关键站点：第一类研究中，研究学者采用站点度值、半局部中心性及节点重要度评价矩阵等作为站点重要度指标，并结合相应领域的实际网络验证了所建立指标的有效性[1-4]；第二类研究着重强调节点在节点间连接路径上所发挥的作用，建立了介数中心性、接近中心性等节点重要度指标[5, 6]；第三类研究通过移除和收缩相应的节点，采用网络凝聚度等作为指标，衡量网络遭受破坏前后指标的变化情况来计算站点重要度，并识别关键站点[7, 8]；第四类研究中，研究学者在计算节点重要度时，不仅考虑了邻居节点数量的影响，还考虑了邻居节点质量对节点重要度的影响[9, 10]。

分析文献可知，现有节点重要度计算方法存在未全面利用网络信息、引入主观因素权重、算法时间复杂度高等缺点，这些缺点影响了识别结果的准确性。对比其他识别方法，LeaderRank算法[11]能全面利用网络信息，不需要人为干预，具有鲁棒性强和收敛速度快的优点，识别结果具有较高的准确性。因此，本文在构建高铁网络的基础上，选取站点度值、站点介数及改进LeaderRank算法的计算结果作为高铁网络站点重要度，结合站点重要度识别网络关键站点，最后结合改进SIR模型模拟全网站点的晚点情况来分析关键站点识别结果的准确性。

1 关键站点识别

1.1 构建高铁网络

构建高铁网络时，以城市为站点，即若某城市存在多个高铁车站，则将多个车站合并为一个站点（例如，将北京站、北京西站、北京南站及北京北站合并为北京站）。结合2016年国家发改委发布的《中长期铁路网规划》，构建2030年中国高铁网络拓扑结构，如图1所示[12]，所构建的高铁网络包含386个站点、547条边，对站点进行编号得到站点邻接矩阵及站间邻接距离矩阵。

图1 2030年中国高铁网络

1.2 基于拓扑结构的关键站点识别

1.2.1 度中心性

站点的度反映与站点直接相连的站点数量，度值越大说明站点直接相连的站点越多，站点在高铁网络中的重要程度就越高。根据站点度值确定2030年中国高铁网络最重要的五个站点如表1所示。

表1 基于站点度值的高铁网络最重要的五个站点

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

由表1可知，合肥为2030年高铁网络中度值最大的站点，这是因为合肥地处东部发达地区，位于京沪、京港（台）及沿江通道的衔接处，连接着多条高铁线路，站点周边线路密集程度高。但对合肥所连接的高铁线路进行分析发现，衔接线路多为城际线路，而城际线路运输能力有限，仅承担区域内部的客流交换任务。说明虽然合肥的度值很大，但只能反映合肥在局部区域的重要程度，无法从全局角度反映合肥的重要程度。因此通过度值识别网络中的关键站点时，不能保证识别结果的准确性。

1.2.2 介数中心性

站点介数被定义为网络所有最短路径中经过该站点的数目占全网最短路径总数的比例，站点介数越大说明该站点所能影响的最短路径越多，站点在高铁网络中的重要程度就越大。根据站点介数确定2030年中国高铁网络最重要的五个站点如表2所示。

表2 基于站点介数的高铁网络最重要的五个站点

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

分析表2可得，天津是2030年高铁网络中介数最大的站点，说明通过天津的最短路径数目最多。这是因为天津位于京沪通道和沿海通道的交点，是连接东部和东北地区的枢纽。但进一步分析发现，天津地处渤海湾地区，受限于地理位置的原因，天津所衔接的高铁线路较少，线路密集程度较低。说明通过介数识别关键站点时，并未考虑站点的局部信息，识别结果存在误差，不能保证识别结果的准确性。

1.3 改进LeaderRank算法

利用LeaderRank算法识别有向网络关键节点的主要步骤为如下。

1.4 改进LeaderRank算法的识别结果

结合改进LeaderRank算法识别2030年高铁网络的关键站点，根据站点重要度值，绘制得到图2所示的站点重要度分布图。

图2 站点重要度

根据计算结果对站点重要度进行排序，得到2030年中国高铁网络最重要的五个站点如表3所示。根据表3可得，长沙是2030年高铁网络中最重要的站点，这是因为长沙是京港澳、沪昆及厦渝通道的交点，同时站点周围还连接着武汉、贵阳等重要度高的站点；随着“八纵八横”网络的建成，贵阳将成为西南地区与东部、北部地区联系的枢纽，是网络中仅次于长沙的重要站点；作为19个综合铁路枢纽之一的成都，是西南地区与西北及中部地区联系的主要站点，衔接着多个方向，具有较高的影响力；武汉位于“八纵八横”网络的中心，是沿江通道与京港澳通道的衔接点，是大量东西向、南北向乘客的必经站点；西安是西北地区对外衔接的关键站点，是路桥、京昆及包海通道的交点，具有十分重要的枢纽作用。

表3 基于站点重要度的高铁网络最重要的五个站点

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

根据站点地理区位信息将站点按地区进行分类，计算不同地区所含站点数量及站点重要度均值，计算结果如表4所示。分析表4可知，2030年西南地区的站点重要度均值最大，这是因为呼南通道等八大高铁主通道以西南地区为终点，地区线路等级高，线路稠密；同时西南地区拥有成都、重庆及贵阳等综合铁路枢纽，多核心站点的存在显著提高了该地区站点的重要度。东北地区的站点重要度均值最小，主要原因在于东北地区的高铁主通道较少，线路密集程度不高，线路空间分布不均匀，北部高铁线路稀疏南部稠密；同时东北地区仅有沈阳这一综合铁路枢纽，核心站点少，导致整个地区站点的重要度偏低。

表4 地区重要度

Tab.4 Regional importance

2 站点传播能力仿真

2.1 SIR模型

在高铁复杂的运输环境下，高铁列车运行过程中不可避免地会受到自然灾害、线网故障等突发事件的影响，从而导致列车发生运行晚点事件。运行晚点事件会以一定的概率传播给其他站点，造成其他站点运行的列车也发生运行晚点；同时在某站点运行晚点的列车也有一定的概率转为正点，转为正点运行的列车将不再传递列车运行晚点信息。上述过程类似于传染病的传播，列车晚点信息类似于病毒[14]，可以运用SIR（Susceptible Infected Recovered，SIR）模型[15]模拟全网列车的运行晚点情况。

SIR模型是经典的传染病动力学模型，能够有效模拟网络受事件影响的情况。在模型中，“S”表示易感染者，即能被感染者感染的人。“I”表示感染者，即携带病毒的人。“R”表示免疫者，即不携带病毒且不会被感染者感染的人。一定概率条件下，易感染者会变为感染者，感染者会变为免疫者，网络的传播能力可以用网络中被感染人数的占比来表示。经典SIR模型的计算公式为：

step2迭代循环，计算结果。根据改进SIR模型，在传播时间步长范围内运行仿真，计算每个时间步长内发生列车运行晚点事件的站点数量。

2.2 仿真结果及分析

图3 站点传播晚点能力仿真结果

分析图3可知，站点重要度越高的站点发生运行晚点事件，晚点信息所能传播的站点越多，说明此类站点具有更强的传播能力，在网络中具有更高的重要程度，一定程度上说明了改进LeaderRank算法识别结果具有更高的准确性。分析长沙、贵阳及成都的站点传播晚点能力曲线可以发现，时间步长超过一定值时，发生列车运行晚点事件的站点数量迅速增加，这将对高铁网络列车的正点运行产生巨大的影响。换言之，如果能在较短时间内有效解决列车运行晚点问题，则能有效缩小列车运行晚点信息传播的范围，将列车运行晚点所造成的损失控制在最小。分析SIR模型相关参数可知，加强高铁列车运输组织，降低站点传播列车运行晚点信息的概率，以及科学调度指挥，保证充分的列车运行时间冗余，都能达到有效缩小列车运行晚点信息传播范围的目的。

2.3 识别方法比较

利用改进SIR模型对基于站点度值、站点介数及改进LeaderRank算法所识别的关键站点进行站点传播晚点能力仿真，分别设置列车在每种识别方法得到的5个关键站点发生列车运行晚点事件，计算每个时间步长内发生列车运行晚点事件的站点数量的平均值。平均值越大，该方法识别关键站点的准确性越高，仿真结果如图4所示。

图4 不同识别方法对比分析

分析图4可得，当传播时间步长大于25时，基于改进LeaderRank算法所识别的5个关键站点传播列车运行晚点信息的能力最大，说明综合利用节点局部信息及网络全局信息的改进LeaderRank算法所识别的关键站点在网络中具有更大的影响力，识别结果具有更高的准确程度；基于度值所识别的5个关键站点传播列车运行晚点信息的能力最小，这是因为度值只利用了节点的局部信息，网络信息利用程度不高，识别结果的准确性较差。对比三条曲线可以发现，综合利用网络信息越多的识别方法，对应识别结果具有更高的准确性。因此，在进行高铁网络关键站点识别时，应充分利用节点的局部信息及网络的全局信息，以提高识别结果的准确性。

3 结 论

（1）利用改进LeaderRank算法计算2030年中国高铁网络站点的重要度，并识别了网络中的关键站点。识别结果表明：长沙是最重要的站点，西南地区是最重要的地区。通过对比不同识别方法的识别结果，发现相比于基于节点特性的传统关键站点方法，改进LeaderRank算法的识别结果具有更高的准确性。

（2）利用改进SIR模型对站点的晚点信息传播能力进行仿真，发现列车在关键站点发生晚点时将会对整个高铁网络列车的正点运行产生巨大影响。因此提高对关键站点的关注力度，科学调度指挥，是保证高铁网络正常运输的有效措施。

（3）城市的发达程度决定站点所承担的客流量，客流量越大的站点，在网络全局的重要度越大。本文只从网络的拓扑结构角度对关键站点进行识别，未考虑站点及线路所承担的客运量，如何将网络的客运量与LeaderRank算法相结合，将是接下来所要研究的方向。

[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] 于宝, 冯春, 朱倩, 等. 中国高速铁路网络脆弱性分析[J]. 中国安全科学学报, 2017, 27(9): 110-115.

[3] 张锦, 秦东. 快递企业配送网络的鲁棒性及其提升对策研究[J]. 交通运输工程与信息学报, 2018, 16(3): 7-13+58.

[4] 王露, 郭强, 刘建国. 基于加权方法的节点重要性度量[J]. 计算机应用研究, 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] 王班, 马润年, 王刚, 等. 加权网络节点重要性评估的改进节点收缩法[J]. 计算机应用研究, 2016, 33(7): 2122-2124.

[8] 刘建强, 兰巨龙, 邬江兴. 基于节点疏远方法的网络节点重要性评价[J]. 计算机工程与科学, 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] 许评, 李玉鹏, 莫宇迪, 等. 基于复杂网络的复杂机械产品关键零件识别[J]. 组合机床与自动化加工技术, 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] 国家发展和改革委员会, 交通运输部, 中国铁路总公司. 中长期铁路网规划[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

国家重点研发计划项目（2017YFB1200701）

陈锦渠（1995—）；男，西南交通大学硕士研究生，研究方向：交通运输规划与管理，E-mail：Chengjingqu@my.swjtu.edu.cn

陈锦渠，刘杰，殷勇，等. 基于改进LeaderRank算法的高速铁路网络关键站点识别方法研究[J]. 交通运输工程与信息学报，2020，18（1）：83-90.

（责任编辑：刘娉婷）