基于贪心介数的地铁-公交复合网络关键车站识别算法
2022-07-12夏永跃王运明李卫东
汪 军,夏永跃,王运明,李卫东
(大连交通大学自动化与电气工程学院,大连 116028)
引言
城市轨道交通具有快速、大运量和污染小等优势，能有效缓解城市交通拥堵问题。随着城市化进程快速发展，大中型城市构建了以轨道交通为骨架，快速公交、常规公交等相融合的地铁-公交复合交通网络体系。地铁-公交复合网络作为重要的城市交通基础设施，极大地方便了人们出行，提高了整个城市的运转效率。然而，网络规模的扩大，增加了网络的复杂性，对地铁-公交复合网络的鲁棒性提出了更高要求。尤其是关键车站发生故障会极大影响交通网络的运输效率，甚至引发网络瘫痪。因此，识别地铁-公交复合网络的关键车站不仅对指导线网规划、线站位布局以及运营管理具有重要意义，还可为应对大型群众活动、自然灾害等突发公共事件引发的集群式人员流动提供科学的疏导策略。
近年来，复杂网络理论在交通网络领域得到了广泛引用，分析了交通网络的特征与规律。学者们提出了Space L、Space P、Space R等多种交通网络建模方法。LI等[1]采用Space L、Space P方法分别构建地铁网络、公交网络和地铁-公交复合网络模型，发现地铁-公交复合网络具有更强的鲁棒性。DING等[2]采用复杂网络建立城市地铁网络模型，并分析了网络特征。LUO等[3]采用Space L和Space P方法构建北京市地铁-公交复合网络及其子网络模型，分析表明网络具备小世界和无标度特性，复合网络可增强乘客的换乘效率。沈黎等[4]通过L、P、R空间建立城市公共交通网络模型并分析网络特征。KUNT等[5]提出基于网络聚集的关键车站识别方法，通过考虑节点的度和位置确定关键车站。CAO等[6]分析了关键节点对公交网络健壮性的影响，发现采用介数中心性方法识别的关键车站对网络破坏性最严重。严开等[7]提出了基于Pagerank的道路交通关键车站识别方法。江成等[8]提出通过计算最小二阶路径内连通节点对的个数判断节点重要性。LIU等[9]结合交通流量特征，提出基于加权中心性的关键节点识别算法，提高城市交通网络的关键站点识别精度。刘菁[10]提出了考虑节点连通可靠度的关键节点识别算法，分析了交通效能的变化情况。薛锋[11]提出灰色关联和TOPSIS相结合的关键站点识别方法。陈诗等[12]从时序网络拓扑结构和动力学角度，系统地分析了现有的关键节点识别方法。ADDIS等[13]提出基于贪心策略的关键节点识别算法。YE等[14]提出了贪心随机动态组合选择算法，从局部最优中寻找最优子集的极值，加强迭代之间的链接，提高关键车站的识别精度。KIM[15]改进贪婪控制方法对特定交通条件下的流量限制，提高了搜索效率。蔡盼等[16]提出了一种基于贪心策略的最近邻算法。
为挖掘地铁-公交复合网络的关键车站，提高关键车站的识别精度，采用复杂网络理论建立地铁-公交复合网络模型，提出基于贪心介数的地铁-公交复合网络关键车站识别算法。考虑删除某些重要车站后，剩余车站的重要度排序发生动态变化的特点，在介数中心性算法的基础上，引入贪心算法，选择当前最关键的车站，扩大关键车站的影响力。以成都市地铁-公交复合网络为例，验证该算法的可行性与有效性，提高网络的鲁棒性。
1 地铁-公交复合网络模型
为准确描述地铁-公交复合交通网络的相互关系，采用复杂网络理论建立地铁-公交复合网络模型。交通网络主要有Space L和Space P两种建模方法。Space L方法将车站抽象为节点，若两个车站地理位置相邻并有同一个车次通过，则节点之间有连边；Space P方法也将车站抽象为节点，若车站之间有直达的车次，则节点之间有连边。
地铁-公交复合交通网络是由不同的车站和线路构成的复杂网络，采用Space L方法构建网络模型，将地铁-公交复合网络分为层内网络和层间网络，其中层内网络为公交和地铁两个独立的复杂网络，层间网络为地铁网络和公交网络的车站之间存在耦合关系而形成的网络。地铁-公交复合网络表示为GB-S={GB，GS，RB-S}。
地铁网络描述为GS
在城市规划建设中，为增强城市交通系统的运输效率和运输范围，一般1个地铁车站周围会设置多个公交车站，形成一对多的耦合关系，即∀si∈VS，∃bj∈VB，使得si→bj。设矩阵R为层间网络的耦合矩阵，矩阵元素rij表示节点si和bj之间的耦合关系，则R=[rij]NP×NF，其中si→bj时，rij=1；否则rij=0。
城市地铁-公交复合网络进一步表示为GB-S
地铁-公交复合网络的拓扑结构如图1所示，上层为公交网络，下层为地铁网络，两层之间的连接为层间耦合关系。地铁网络的车站S2周围存在3个公交车站B1、B2、B3，乘客步行就可到达并换乘(限定200 m)，两者建立层间耦合关系s2→(b1，b2，b3)。
图1 地铁-公交复合网络的拓扑结构
2 基于贪心介数的复合网络关键车站识别算法
2.1 贪心策略
王翔等[17-18]最早提出的贪心算法用于解决网络的影响力最大化问题。在问题求解时，使用贪心策略做出在当前最好的选择。主要思想是每一步迭代都将重新计算当前未被激活的节点加入种子节点集后的边际效益，选择使得边际效益增加最大的节点作为下一个种子节点。具体过程如下：
(1)输入网络图D=(aij)n×n，利用重要度(如：度、PR值、接近中心性等)计算方法计算节点重要程度并进行排序；
(2)初始化一个空集L=∅，将重要度最大的节点记录于集合L，并从网络中删除该节点，此时，最大连通分支记为CV；
(3)选择CV中重要度最大的节点记录于集合L，并删除该节点；
(4)调用Warshall算法判断是否存在连通子图，若存在，重复步骤(3)，直至网络不存在连通子图，或网络剩余节点都成为孤立节点，贪心策略结束。
贪心算法具有较高的鲁棒性，算法在解决影响力最大化问题中准确率最低也可以达到63%。但是，较高的准确率带来的却是非常高的时间复杂度，在小规模的网络中，贪心算法可以发挥出其优异的性能，但对于规模较大的网络，算法的时间复杂度过高。
2.2 介数中心性
介数中心性表示网络中节点间最短路径经过某节点的数目，是刻画节点网络结构特征的重要指标之一。节点介数中心性越大，网络中经过该节点的最短路径条数越多，说明节点对网络的信息传播或流通控制能力越强，该节点在网络中也就越重要。定义为
(1)
2.3 基于贪心介数的关键车站识别算法
为提高关键车站的识别精度，考虑删除某些重要车站后，剩余车站的重要度排序发生动态变化的特点，引入贪心算法，提出基于贪心介数的地铁-公交复合网络关键车站识别算法。
该算法的设计思想是：首先计算地铁-公交复合网络中每个车站的介数值，删除网络中车站介数最大的节点，并将其记录到车站重要性序列表中；如果剩余车站构成的节点集合还存在连通性，则再次计算剩余车站构成的网络最大连通分支以及最大连通分支中每个车站的介数值，删除最大连通分支中车站介数最大的节点，并将其记录到车站重要性序列表中；如此反复，直至车站重要性序列表的车站个数为网络节点总数或剩余车站都为孤立节点。
算法的具体过程描述如下：
(1)输入地铁-公交复合网络的邻接矩阵D=(aij)n×n，初始化重要度序列L=∅、最大连通分支节点集合CV=∅、孤立节点集合CS=∅；
(2)计算当前网络各节点的介数值，介数最大节点序号记录到重要度序列L=L∪{i}；
(3)删除网络中介数最大的节点i，删除后网络中的孤立节点记录到集合CS中；
(4)调用Warshall算法判断删除节点后的网络是否存在连通子图，若存在，将最大连通分支节点集合记录到CV，并返回至(2)；若不存在，则结束。
3 仿真分析
为验证本文提出的地铁-公交复合网络关键车站识别算法的可行性和有效性，根据百度地图网站提供的成都市市区地铁-公交复合网络数据，利用复杂网络理论，将公交、地铁的车站抽象为节点，车站之间的连接关系抽象为边，建立成都市地铁-公交复合网络模型。考虑部分近邻公交站点的重复性，合并处理相距100 m的重名站点，限定地铁车站周边200 m范围内的公交站点为有效站点，与地铁车站建立连边。该网络包含886个公交车站的162条公交线路和只考虑市区范围内42个地铁车站的5条地铁线路。利用Gephi软件建立的成都市地铁-公交复合网络拓扑结构如图2所示。
图2 成都市地铁-公交复合网络拓扑结构
成都市地铁-公交复合网络与独立网络的各类特征指标对比结果如表1所示。地铁-公交复合网络的平均度4.287最高，说明复合网络中任意车站的邻接车站数高于地铁和公交网络。因所选取地铁网络数据中有5个换乘车站，10个边缘站点，所以地铁平均度为2，地铁网络的平均聚集系数为0。因为任意一个地铁车站的邻接车站并不会通过地铁线路再相互连接，只能通过地面公交中转，地铁和公交相互衔接、配合可有效提高出行效率。复合网络的平均路径长度7.237小于公交网络9.188，说明复合网络中客流从一个车站到另一车站出行的平均距离比单独使用公交出行要小。交通网络中度值大于2的站点一般为换乘车站，起到枢纽作用，聚集系数超过0.05，表明此车站应是居住型、商业、旅游景点等人群密集型车站，其中复合网络聚集系数为0.216远高于地铁、公交网络，具有很强的聚集特性。通过对网络拓扑特性的分析，表明地铁-公交复合网络具备无标度和小世界特性。
表1 成都市地铁-公交复合网络拓扑静态指标
最大连通子图、网络效率、圈数率、连通度等指标是衡量复杂网络中关键节点识别精度重要指标[19-20]，因此，本文采用这些指标评价基于贪心介数的地铁-公交复合网络关键节点识别算法的优势。运用软件Matlab进行仿真分析。
地铁-公交复合交通网络中存在大量度为2的节点，攻击此类节点易形成独立子集团，使得最大连通子图能够很好地评估关键节点识别的精度。网络的最大连通子图比例定义为网络的最大连通子图节点数与网络总节点数的比值，反映被删除节点对网络结构的影响。如果被删除的是边缘节点，则最大连通子图的节点个数依然接近网络初始节点数；如果被删除的节点是关键节点，网络会被划分成多个子网，新的最大连通子图节点个数较少。为增强最大连通子图的区分度，提出最大连通子图相对大小的概念，定义为
(2)
式中，n为最大连通子图的节点数；N为初始网络节点数；f为移除节点的比例。
采用不同策略删除网络中节点对最大连通子图相对大小的影响，如图3所示。
图3 最大连通子图相对大小变化曲线
从图3可知，随着攻击车站比例f的增加，地铁-公交复合网络最大连通子图逐渐下降。当攻击比例达到15%时，随机攻击时，最大连通子图相对大小曲线下降为0.813 9，速度最为缓慢；蓄意攻击时，最大连通子图相对大小曲线均快速下降，表明攻击关键节点对网络结构鲁棒性产生较大影响。其中，攻击贪心介数算法识别出的关键节点时，最大连通子图相对大小曲线下降至0.031 25，下降最快；其次是贪心度中心攻击下降至0.393 3、介数攻击下降至0.575 4、度中心攻击下降至0.813 9。说明贪心介数算法识别地铁-公交复合网络的关键节点准确率最高。
网络效率一般定义为所有节点对之间效率的平均值，能够从全局性的角度分析网络效率对网络性能的影响，表示为
(3)
式中，N为网络的节点数量；dij为节点i和j之间的最短路径长度。
采用不同策略删除网络中节点对网络效率的影响如图4所示。
图4 网络效率变化曲线
由图4可以看出，随着攻击车站比例f增加，地铁-公交复合网络的网络效率逐渐下降，且蓄意攻击比随机攻击下降迅速，蓄意攻击15%以内的车站，贪心介数网络效率下降至0.005，贪心度攻击下降至0.01，介数下降至0.024，度中心性下降至0.046，随机攻击下降最为缓慢降至0.1。本文提出的基于贪心介数的关键车站识别算法相比其他攻击策略，网络效率下降的更快，对地铁-公交复合网络的抗毁性影响更大，说明本文提出的关键车站识别精度更高。
圈数描述了城市公共交通网络的可替代路径的提供能力。城市公共交通网络规模逐渐扩大后，圈数相应增加，但网络规模越大并不代表网络的鲁棒性越强。采用圈数率反映地铁-公交复合网络的鲁棒性，表示为
(4)
式中，圈数μ=|D|-|Vd|+1；D为网络的边数；Vd为网络的节点数目。
采用不同策略删除网络中节点对圈数率的影响如图5所示。
图5 网络圈数率变化曲线
由图5可以看出，随着攻击车站比例f增加，随机攻击策略时，圈数率下降最为缓慢，蓄意攻击策略下仅攻击少量车站，圈数率从0.13快速下降至0，其中贪心介数的攻击策略在攻击比例达到15%时，地铁-公交复合网络圈数率降至0.003，下降速度最快，网络最先瘫痪；其次是贪心度攻击下降至0.005、介数攻击下降至0.006、度中心性攻击下降至0.01、随机攻击下降至0.07。通过对比说明，采用本文提出的关键车站识别算法攻击地铁-公交复合网络，对网络的抗毁性影响最大，关键车站的识别效果更好。
网络连通度是网络实际边数目与理论最大边数目的比值。与聚集系数的区别在于连通度是面向整个网络，而不是网络中某个节点的域。连通度的计算公式如下
(5)
式中，D为城市公共交通拓扑网络的边数；Vd为城市公共交通网络的节点数目。
采用不同策略删除网络中节点对网络连通度的影响如图6所示。
图6 网络连通度变化曲线
由图6可以看出，随着攻击车站比例f增加，随机攻击时，网络连通度下降最为缓慢，蓄意攻击策略下，网络连通度下降幅度最大。当攻击比例达到15%时，贪心介数攻击策略下网络连通度下降至0.001、贪心度中心攻击下降至0.138 8、介数攻击下降至0.153 5、介数攻击下降至0.288 9、度中心性攻击下降至0.288 9、随机攻击策略下降至0.796 4。在4种蓄意攻击策略中，贪心介数中心性策略对网络连通度的影响最大，说明关键车站的识别精度更准确。
4 结语
为挖掘地铁-公交复合网络中的关键车站并提高网络鲁棒性，采用Space L方法，建立了地铁-公交复合网络模型，提出了基于贪心介数的地铁-公交复合网络关键车站识别算法。以成都市地铁-公交复合网络为例，分析表明网络具有无标度和小世界特性，在多种攻击策略中，贪心介数蓄意攻击对网络性能影响最大，表明本文提出的关键车站识别算法具有较高的精度。
文中主要分析地铁-公交无权复合网络的性能，未考虑车站的不同类型对网络的影响，因此，建立加权网络模型并分析网络特征将是今后需进一步研究的重点。
