基于站点线路数的城市公交网络鲁棒性研究

谢怡燃，李国华，杨 波*

(1. 昆明理工大学数据科学研究中心 昆明 650500；2. 昆明理工大学理学院 昆明 650500)

公交系统作为城市的基础设施，对城市功能的正常运转有着重要作用。城市公交系统的研究涵盖多个方面，包括公交网络的布局优化[1-2]、可达性研究[3-4]和公交起讫点分布[5]等。小世界[6]和无标度[7]网络的提出，推动了各类实证网络的研究[8-11]，交通网络作为现实生活中的重要网络受到广泛关注。近年来，研究者已经对航空[12-16]、铁路[10,17]、地铁[18-19]、公交[20-27]及多种交通工具耦合的多层合作网络[28]开展了一系列研究。

目前针对公交网络的研究主要包括拓扑特性、静态鲁棒性和动态鲁棒性3 个方面。在公交网络拓扑特性方面，文献[20]针对波兰22 座城市的公交网络的研究发现，尽管各城市公交网络规模不同，但部分拓扑特征拥有普适性规律。如各城市公交网络都具有小世界特性，公交站点网络的度分布服从幂律分布，最短路径长度服从非对称单峰型分布等。文献[21]对北京、上海和南京的公交站点，线路和换乘网络的研究发现，公交站点和公交线路网络的度分布近似服从幂律分布；公交换乘网络累积度分布近似服从指数分布；公交站点网络和换乘网络具有小世界特性。文献[22]对北京和扬州的公交线路合作网络的研究发现，北京和扬州公交线路网络的度分布分别近似服从指数分布和幂律分布。文献[23]对北京的加权有向公交站点网络的研究发现，网络中节点的度和强度分布极不均匀，强度分布近似服从幂律分布，具有小世界和无标度特性。

在日常运营中，道路施工、交通拥堵、自然灾害等因素可能导致公交站点在短期内失去功能，进而影响整个公交网络。网络的静态鲁棒性是指，依据某种规则依次移除网络中部分节点或边后，网络仍能保持主要功能的能力。在公交网络静态鲁棒性方面，文献[24]采用度值攻击和随机故障对北京、上海、南京和杭州的公交网络进行了研究，发现公交网络在随机故障下的鲁棒性强于度值攻击；度值较大的站点对维持网络稳定性具有重要作用。文献[25]采用度值攻击和随机故障对沈阳市公交站点网络、换乘网络、线路网络、站点−线路双层网络、线路−换乘双层网络的研究发现，单层网络中线路网络的鲁棒性最强；双层网络中站点网络中的节点失效对线路网络影响较大；线路网络中的节点失效对换乘网络的影响较大。文献[26]采用度值攻击和随机故障对重庆市公交−地铁双层网络进行的研究表明，双层网络的鲁棒性强于单层网络。

网络的动态鲁棒性是指节点出现故障引发级联失效时，网络仍能保持主要功能的能力。在公交网络动态鲁棒性方面，文献[27]基于负载−容量级联失效模型[29]，采用随机故障和负载攻击对北京市公交地铁关联网络的研究发现：网络在负载攻击下的鲁棒性最弱，随机故障下鲁棒性最强；增加地铁站点容量能更有效地增强关联网络的动态鲁棒性；当站点容量较小时，网络效率存在非平衡的相变现象。尽管围绕公交网络已开展了大量研究，但仍有很多有趣的问题有待进一步探索。

本文首次研究了依据站点线路数(途经某车站的公交线路总数)失效后公交站点网络的鲁棒性。其主要原因是：大部分公交站点被多条公交线路停靠，仅仅考虑节点度值忽略了这一特性；此外，考虑到同一公交线路对始发站和终点站加权度的贡献为1 而对中间车站加权度的贡献为2，由于城市公交线路数较多，从而导致站点线路数与节点加权度间存在显著差异。因此，站点线路数是区别于度值和加权度值的新参量，研究依据站点线路数失效后公交站点网络的鲁棒性具有实际意义。另一方面，人们对站点重要性的理解也存在差异。度值侧重于网络的连通性，即可到达的相邻站点越多节点越重要，而站点线路数则更多关注在某车站是否有大量的换乘可能，即停靠车次是否较多。

1 网络拓扑结构分析

1.1 网络模型的构建

公交网络主要有站点网络、换乘网络和线路网络3 种类型。表1 显示了不同类型公交网络的节点和连边的定义。本文以公交站点网络为研究对象，从8684 公交查询网(https://www.8684.cn/)分别获取成都、重庆、昆明、贵阳和拉萨5 个城市的公交线路数据(截止2021 年7 月23 日)，建立公交站点网络模型。

表1 不同类型公交网络的定义

表2 显示了网络的基本拓扑特性。其中，N表示公交站点数，M表示公交线路数，D表示网络直径，r表示网络同配系数， 〈k〉表 示平均度， 〈L〉表示平均路径长度， 〈C〉表示平均聚类系数。显然，公交站点网络具有同配性；相比而言，贵阳公交站点网络的平均度和聚类系数偏大，网络直径偏小，说明该网络的连接相对紧凑；拉萨公交站点网络的平均度和同配系数较小，平均路径长度仅次于成都，说明该网络的连接相对松散；此外，成都公交站点网络的平均聚类系数偏小，平均路径长度和网络直径较大，显示网络规模大，连接范围广。

表2 公交站点网络的基本拓扑特性

1.2 累积度分布

度值选择性失效下，网络鲁棒性的研究是通过逐步移除度值较大的节点后，观察网络连通性的变化实现的。为描述该移除过程中网络累积度值的变化，定义网络的累积度分布为：

图1 显示了5 个城市公交站点网络的累积度分布的半对数拟合曲线。结果显示：累积度分布近似服从指数分布，即P(k)～e−βk，拟合曲线的指数见表3。累积度分布为指数意味着，在网络形成过程中，新增站点与已有站点之间的连接可近似视为随机连接[30]。曲线的斜率描述了在逐步移除较大度值节点的过程中，度分布变化快慢的趋势。斜率越大，变化越剧烈，对网络的影响也越大。从图1中可以看出，拉萨的累积度分布指数最大，贵阳的最小。

图1 半对数坐标下公交站点网络的累积度分布

表3 累积度分布和累积站点线路数分布拟合曲线的指数

1.3 累积站点线路数分布

站点线路数是指途经某车站的公交线路总数。本文考虑该值的动机源于，公交站点网络仅描述了站点间的连接关系而没有考虑站点被多条公交线路重复经过的情况，且该过程不能通过加权公交站点网络描述(主要原因是城市公交网络线路数较多，始发站和终点站对加权网络的贡献与中间车站不同)，因此本文首先对途经站点i的公交线路数量ni进行了统计。然后类比累积度分布定义累积站点线路数分布：

图2 显示了5 个城市公交站点网络的累积站点线路数分布的半对数曲线。显然，各城市累积站点线路数分布近似服从指数分布P(n)～e−βn，与累积度分布相比，曲线的斜率存在明显差异，累积站点线路数分布拟合曲线的指数见表3。拉萨的指数较大，昆明和成都次之，其次是重庆，最后是贵阳。

图2 半对数坐标下累积站点线路数分布

1.4 最短路径长度分布

在公交站点网络中，最短路径长度是指从任意初始站点i出发，到达任意目的站点j所经过的最少边数，记为dij。网络的平均路径长度定义为网络中任意两节点间最短距离的平均值，表达式为：

式中，N为网络的节点总数。图3 显示了5 个城市公交站点网络最短路径长度的分布曲线。显然，重庆、昆明、贵阳和拉萨的最短路径具有高斯分布特性，而成都的最短路径长度分布具有长尾特性，出现该特性的原因是成都的公交站点网络包含了很多郊区线路，导致部分站点间的最短路径长度值较大。此外，拉萨的最短路径长度也较大，在距离值为30 的附近表现出一个下降较为缓慢的平台期。

图3 公交站点网络的最短路径长度分布

1.5 介数分布

公交站点网络中站点i的介数是指经过该站点的最短路径数所占的比例，记为BCi。定义如下：

式中，gst代表从节点s到节点t的最短路径数目；代表从节点s到节点t的最短路径中经过节点i的数量。由式(4)可知，归一化介数值的取值较为分散，无法直接得到介数的分布情况。为进一步研究介数选择性失效下网络中累积介数的变化，定义累积介数分布为：

累积介数分布如图4 所示，可以看到，相同介数值时，拉萨的累计值较大；昆明、贵阳次之；成都、重庆较小。在公交站点网络中，介数较大意味着该站点被很多线路的最短路径途经，所以，累积介数值大小显示了一个城市对部分站点的依赖程度。

图4 公交站点网络的累积介数分布

2 网络静态鲁棒性分析

2.1 失效方式与评价指标

网络静态鲁棒性分析是依据某种规则依次移除网络中部分节点或边后，研究网络连通性和网络效率发生的变化。考虑到现实生活中，交通拥堵、道路维修和自然灾害等事故会造成公交站点短期内失去功能，因此本文研究不同的站点失效方式下，公交站点的网络鲁棒性。具体可分为节点的随机失效和选择性失效[31]，随机失效(RA)模拟自然灾害对公交网络的影响，选择性失效模拟公交枢纽站点堵塞和维修对公交网络的影响。由于任意节点的失效都伴随网络拓扑结构的变化从而引发失效指标值的改变，可将选择性失效细分为静态选择性失效和动态选择性失效。静态选择性失效是指在初始网络中计算各节点的选择性失效的指标值，按降序依次移除节点，包括静态度值选择性失效(DA)、静态介数值选择性失效(BA)和站点线路数选择性失效(NBLS)。动态选择性失效是指依据当前网络的选择性失效指标值移除节点后，重新计算新网络的指标值作为下一轮移除节点的依据，包括动态度值选择性失效(UDA)和动态介数值选择性失效(UBA)。

当某个节点失效时，移除该节点将引发网络连通性的改变。为描述这一变化，研究者选取网络最大连通子图的相对大小S作为网络鲁棒性的评价指标，表达式如下：

式中，N表示初始网络中的节点总数；N'表示移除节点后网络中最大连通子图的节点总数。

网络的鲁棒性可以通过网络完全崩溃时(S=0)移除节点比例的临界值来衡量。然而，当多个网络的最大连通子图相对大小的变化曲线交错或临界值相近时，仅通过观察很难分辨优劣。本文引入描述全局鲁棒性的评价指标R，表达式为[32]：

式中，Q表示失效的节点数量；S(Q)表示移除Q个节点后最大连通子图的相对大小。

本文设置每次移除0.01N数量的公交站点，在选择性失效下，当多个站点的失效指标值相同时，随机移除其中之一。为获得稳定的计算结果，需要对计算结果进行平均，选择性失效取10 次平均后的结果，随机失效取5 000 次平均后的结果。

2.2 结果分析

在公交站点网络中，站点失效将引发网络连通性的改变。图5 依次显示了站点线路数选择性失效、随机失效、度值、动态度值、介数值和动态介数值选择性失效下，不同城市的最大连通子图相对大小S随移除节点比例f的变化关系。显然，相同的失效方式下，不同城市表现出不同的变化趋势。

图5a 和图5c 展现出不一样的变化规律，说明站点线路数并非重复的平庸参数。图5c 与图1 存在对应关系，即累积度分布曲线斜率越大，度值选择性失效下最大连通片占比变化越快，网络的鲁棒性越差。产生该现象是因为度值是网络结构的直观描述，度值选择性失效直接反映了网络连通性的变化。相应的图5a 和图2 的对应关系相对弱一些，除贵阳的鲁棒性表现较为突出外，其他城市随着移除节点比例的增加网络鲁棒性变化各异。图5e 和图4 的对应关系更差，很难从累积介数分布曲线推演网络的鲁棒性。综上，度值、站点线路数和介数值选择性失效对最大连通片占比的影响存在差异，本文认为这主要与站点失效方式对网络刻画角度的不同有关，度值是公交站点网络的直观描述，站点线路数是网络中公交线路运行状态的描述，而介数以被最短路径通过为标准。图5b 描述了随机失效下，不同城市最大连通片占比随移除节点比例的变化关系。当移除少部分站点时，成都的最大连通子图相对大小S下降较快，而随着移除站点数的增加，拉萨快于成都。该现象可能是由公交站点网络的拓扑结构差异引起的，成都公交网络相对松散，包含很多郊区线路，随机移除节点对郊区线路的影响较大。拉萨由于城市规模的限制，对城市中心节点的依赖较为明显。此外，随机失效下，S随着移除节点比例f的变化趋势较为平缓，几乎不存在突然跳变现象。这表明选择性失效对公交站点网络的破坏性强于随机失效。

图5d 和图5f 为动态度值选择性失效和动态介数值选择性失效下，不同城市的最大连通片占比随移除节点比例的变化关系。可以看到不同城市的变化曲线几乎坍缩在一起，这说明不断修正选择性失效指标可以部分消除不同网络结构对鲁棒性的影响。

图5 公交站点网络最大连通子图的相对大小S 与移除节点比例f 的关系

为进一步比较不同节点失效方式对同一网络结构的影响，图6 和表4 分别显示了5 个城市在不同失效方式下的最大连通子图相对大小S随移除节点比例f的变化关系和R值的大小。显然，不同网络结构在随机失效下R值最高，S随着移除节点比例f的变化趋势最平缓，鲁棒性最好。动态选择性失效(UDA 和UBA)下，R值较低，网络鲁棒性较差。静态选择性失效的鲁棒性因网络结构的不同而异。总之，表4 中的数据与图片中曲线的变化趋势相符，随机失效对网络的破坏弱于选择性失效；选择性失效下，动态选择性失效对网络破坏强于静态选择性失效。

表4 公交站点网络在不同失效方式下的R 值

图6 各城市公交站点网络最大连通子图的相对大小S 与移除节点比例f 的关系

3 网络动态鲁棒性分析

在分析网络静态鲁棒性时，假设各站点发生故障是相互独立的。但在现实生活中，网络各节点相互关联，一个节点的故障可能会导致相邻节点的故障，甚至引发网络中部分节点无法正常工作，这一现象称为级联失效。网络动态鲁棒性是指，节点出现故障引发级联失效时，网络仍能保持正常功能的能力。

3.1 负载−容量级联失效模型

假设网络中每个站点都拥有负载量和容量两个值，容量是站点所能承载的最大负载量，当负载量小于等于容量时，站点正常工作；当负载量超过容量时站点失效。考虑到站点负载分布与网络度分布高度相关[29,33]，假设公交站点i的初始负载量Li由下式确定[34]：

式中，β 是节点负载控制参数。

站点容量Ci是站点i可承载的最大负载量，根据负载−容量级联失效模型[29]，假设站点容量与负载由下式确定：

式中，α 表示节点负载容忍参数。

当某个站点i失效时，该站点的负载Li会依据邻居站点容量进行重新分配。i的邻居站点j获得的分配负载∆Li→j为[34]：

式中，τi表示i的邻居集合。站点j的当前负载量包括初始负载和分配负载。若当前负载超过容量将引发站点j失效，失效站点将继续分配负载给邻居站点。

3.2 算法描述

负载−容量级联失效算法如下：

1) 初始化公交站点网络，输入参数α、β 的值，设置失效站点数a为0，依据式(8)和式(9)分别计算各节点的初始负载量和容量，依据式(6)计算当前网络最大连通子图的相对大小S。

2) 选择节点的失效方式，移除失效节点，失效站点数a的值加1。计算当前网络中各节点的负载量，判断是否产生过载站点，若产生则执行步骤3)和4)；若不产生则执行步骤5)。

3) 过载站点依据式(10)将负载分配给邻居站点，然后移除该站点。

4) 重新计算当前网络各节点的负载量，判断是否产生过载节点，若产生则回到步骤3)；若没有则执行步骤5)。

5) 计算当前网络最大连通子图的相对大小S，判断S是否为0，若S≠0 则回到步骤2)；若S=0 则算法结束。

运用选择性失效和随机失效两种方式分别对5 个城市公交站点网络的动态鲁棒性进行研究。选择性失效包括：NBLS、DA、BA、UDA 和UBA。选择性失效时，若存在多个站点失效指标值相同的情况，则随机移除其中一个站点。为确保最终结果的准确性，需要对计算结果进行平均，BA 和UBA 取10 次平均后的结果，其余选择性失效取100 次平均后的结果，随机失效取5 000 次平均后的结果。

3.3 结果分析

图7 显示了在α=1，β=1.5 时，不同失效方式下，不同城市公交站点网络最大连通子图的相对大小S随失效站点数a的变化关系。随着失效站点数a的增加，网络的连通性逐渐降低，最大连通子图的相对大小逐渐减小。选择性失效存在连通性的突然跃变，只需移除少部分节点就能触发级联失效，由于网络结构的差异导致跃变点存在差异。随机失效下，网络连通性的变化则相对平缓且能够承受的失效站点数较多，如图7b 所示。对比图7c 和图7d 发现，度值失效对网络的破坏性强于更新度值，该结果与静态鲁棒性相反，其原因可能是，网络的初始负载和容量由最初的网络结构确定，部分站点失效后，网络中最大度节点不一定拥有最大的负载和容量值。考虑到不同城市可能具有不同的α 和β 值，此处不再对不同城市公交站点网络的鲁棒性进行对比分析。

图7 公交站点网络最大连通子图的相对大小S 与失效站点数a 的关系

为进一步研究不同失效方式对同一网络结构的影响，图8 分别显示了5 个城市的公交站点网络在不同失效方式下，最大连通子图的相对大小S随失效站点数a的变化关系。可以看出，随机失效下的鲁棒性远远强于选择性失效，动态选择性失效强于静态选择性失效的结论已经不再适用。

图8 各城市公交站点网络最大连通子图的相对大小S 与失效站点数a 的关系

为探究负载容忍参数α 与负载控制参数β 对网络动态鲁棒性的影响，本文进一步针对UDA 策略下，网络最大连通子图的相对大小首次达到0.01时所需的失效站点数进行了研究。图9 为α 和β 参数空间内失效站点数相对大小的热力图。当β 值相同时，失效站点数a随着α 的增加而增加。这是因为α 变大导致网络中各站点的容量增加，提高了网络的动态鲁棒性。当α 值相同时，失效站点数a随着参数β 的增加而减少。这是因为β 变大导致网络中负载的异质性增强，站点间负载量差距变大。少量负载较大的站点失效可能导致整个网络的崩溃，网络的动态鲁棒性变差。

图9 公交站点网络最大连通子图的相对大小S 首次达到0.01 时需要失效的节点比例

4 结 束 语

本文基于站点线路数(途经某车站的公交线路总数)研究了成都、重庆、昆明、贵阳和拉萨公交站点网络的拓扑特性、静态鲁棒性和动态鲁棒性。将站点线路数选择性失效与广泛研究的随机失效、度值、介数值、动态度值和动态介数值选择性失效进行了比较。结果表明：各城市公交站点网络的累积站点线路数分布和累积度分布近似服从指数分布，指数的取值不同；重庆、昆明、贵阳和拉萨的最短路径长度分布具有高斯分布特性，成都的最短路径长度分布具有长尾特性；网络的静态鲁棒性与网络的拓扑结构密切相关，累积度分布曲线斜率越大，度值选择性失效下最大连通片占比变化越快，网络的鲁棒性越差，站点线路数和介数值对最大连通片占比的影响较度值弱一些；对于静态鲁棒性而言，动态选择性失效对网络的破坏性强于静态选择性失效，但该结论不适用于动态鲁棒性；不论是静态鲁棒性还是动态鲁棒性，随机失效下的鲁棒性都强于选择性失效下的鲁棒性；增加负载容忍参数α或减少负载控制参数β 可提高网络的动态鲁棒性。