基于超图的公交超网络拓扑特性及鲁棒性分析

罗海秀，赵海兴，肖玉芝，冶忠林，马海瑛，李发旭

1. 青海师范大学 计算机学院，西宁 810016； 2. 青海省藏文信息处理与机器翻译重点实验室，西宁 810008；3. 藏文信息处理教育部重点实验室，西宁 810008

现实社会中存在着大量复杂交错的网络结构，如科研合作网络、 电力资源分配网络、 交通运输网络、 社会融合网络等．20世纪末，Watts[1]和Barabasi[2]提出的小世界网络模型和无标度网络模型在学术界掀起了复杂网络的研究热潮．随着网络规模的复杂化和结构的多样化，研究者们发现基于普通图的复杂网络中节点只能描述相邻节点或边的连接关系，并不能同时体现出节点和边的依赖关系，也无法通过复杂网络模型精准地识别重要节点和边．因此，复杂网络的研究重心逐渐向超网络结构特性的探索研究过渡，超网络以其自身独具的多层性、 多维度、 多属性等特性，在保证节点同质性的同时，可以直接体现任意多个节点和超边间的复杂关系，吸引了众多学者的目光．Wang等[3]采用增长和优先连接机制逐步生成超网络动态演化模型并对网络属性进行分析．Ernesto等[4]研究了超网络的子图中心性和聚类系数等问题．胡枫等[5-6]构建了BA无标度超网络和随机超网络演化模型，并分析了蛋白质超网络和科研合作超网络的拓扑属性．郭进利等[7-10]研究了非均匀超网络中无标度涌现问题，并在舆情传播以及超网络演化的内在驱动力问题上进行了探索．在交通网络的实际应用中，黎耕等[11]通过计算分析成渝城市群功能多中心度，得出通过培育城市群多中心，能够有效促进城市群内其他城市的发展．在超网络的实际应用中，孙琳等[12]采用超网络的研究方法分析了欧洲航空超网络的特征．陆睿敏等[13]构造了上海市公交超网络并对网络的拓扑特性以及鲁棒性进行了分析.

复杂网络性能研究中，网络的抗毁性是系统在遭到针对性的蓄意攻击或随机攻击时网络仍能保持畅通且稳定工作的能力．目前基于图论的网络抗毁性指标有：连通度、 完整度、 离散度、 粘聚度以及网络效率等[14]，但这些指标在网络规模、 计算复杂度以及结果的精确性上皆有局限性，并不适合结构复杂的大规模网络．随后，吴俊等[15-17]引入了自然连通度指标来衡量复杂网络的抗毁性，该测度能精准客观地刻画网络的抗毁性．此外，马秀娟等[18]结合超图理论知识，仿真分析了无标度超网络上的相继故障问题．结果表明，超网络在遭受外部攻击时，表现出既鲁棒又脆弱的特性．因此，基于节点和超边重要性的公交超网络鲁棒性的研究也颇有意义.

城市公共交通是市民快捷、 环保且低价出行的首要选择，公交系统的髙效便捷对城市市民的出行、 运输效率、 环境保护、 绿色出行以及经济发展都有重要意义[19-20]．本文基于超图理论，构造了城市公交超网络模型，相较于现有的研究工作，本文的主要贡献在于结合超图的2-section图和线路理论进一步分析城市公交超网络的特性，基于节点度、 超度以及介数中心性3个拓扑指标识别超网络中的关键节点，用超边度识别超网络中的关键超边．此外，还构造了与公交超网络相依赖的以美团商家为节点，公交站点为超边的美团超网络，探究了站点的分布对城市经济发展的影响．此外，基于自然连通度指标分析了公交超网络的节点和超边在随机和蓄意两种攻击方式下，超网络的抗毁性，并结合网络的抗毁性结果，提出了站点减压策略来缓解蓄意攻击对公交超网络的影响．本文以青海省西宁市为例，其研究方法也适用于其他城市公交超网络的研究与应用，本文的研究结果可为城市交通系统的建设提供一定的理论依据.

1 超网络相关概念

1.1 超图定义

近年来，超网络的理论研究与发展日渐完善，超网络的知识也逐渐应用到现实社会中，研究内容主要有超网络演化模型的构建和超网络动力学研究两方面[3-6，8-13，17].

目前，超网络的定义主要有两种，一种是基于超图理论的超网络，另一种是由不同类型的网络相互连接构成的超网络．前者的网络节点连边演化为超边，超边内部允许多个节点存在，超边之间通过公共节点彼此连接，其中关联矩阵是描述超网络最直接的表现形式．后者的概念最早由Denning[21]提出，指的是规模庞大，由多个网络相互嵌套构成的超级网络，又称“多层网络”或“多级网络”[22]，此类超网络可以刻画多个不同类型网络之间错综复杂的多重关联关系.

1.2 超图理论的2-section图和线图分析方法

超图的2-section图和线图的概念最早由Bretto[24]提出．超图H=(V，E)的2-section图记为[H]2，其中[H]2的节点集为H的节点集．若两个节点在[H]2中有连边当且仅当这两个节点包含在超图的同一条超边中，因此，[H]2中的每一条超边内所有节点间是全连接的．超图的2-section图结构显示了网络中所有节点之间的连接关系，相同超边内的节点之间全连接，不同超边中的节点通过公共节点也可以间接连接，通过2-section图的邻接矩阵，可以求得网络中节点的度分布情况，也可以求得网络的聚集系数和节点的介数值，从而判断出网络整体的稀疏性以及网络中的关键节点.

在文献[3]中，线图被称为超网络的投影网络，记为L(H)=(V′，E′)，令超图H没有重复超边，那么V′∶=E，并且如果H中的两条超边ei与ej满足ei∩ej≠φ，那么在L(H)中节点ei与ej相邻．线图结构显示了网络中超边之间的连接关系，线图的邻接矩阵可用于求解网络中超边度分布．图1给出了具有14个节点，7条超边的超图结构，对应的2-section图结构以及对应的线图结构.

图1 超图的2-section图与线图的结构特征

2 超网络拓扑特性

2.1 节点度和超度

超图H=(V，E)中，节点的度是节点vi相邻其他节点的总数，记为ki，节点vi的超度d(vi)指节点vi所在的超边数目．定义超图H的邻接矩阵为A=(aij)N×N，关联矩阵为C=(cij)N×M．节点vi的度和超度表示如下：

(1)

(2)

其中节点vi的度分布p(ki)是超图H中节点度ki占所有节点总数的概率大小．记为

(3)

节点vi的超度分布p(d(vi))是指在超图H中节点超度d(vi)占所有节点总数的概率大小，即：

(4)

2.2 超边度和超边超度

超图H=(V，E)中，超边度定义为与超边ej至少存在1个公共节点的超边的数目，记为d(ej)．超边超度[7]指超边ej中所有节点总数，记为ds(ej)．公交超网络中，超边超度是线路中所包含站点的总数．在关联矩阵C中，超边ej的超边超度ds(ej)为C的第j列所有元素之和，即：

(5)

2.3 介数中心性

复杂网络的介数中心性简称介数[25]，表示网络中节点i恰好经过所有最短路径的数目与最短路径总数的比值．介数值在公交超网络中可以反映站点的拥堵情况以及对换乘情况的影响．基于超图理论，将超网络转化为2-section图形式，计算节点的介数值，表达式如下：

(6)

其中，gpq代表网络中所有的最短路径的数目总和，gpq(i)表示节点i正好经过所有最短路径的数目，1/(n-1)(n-2)是归一化因子.

3 城市公交超网络

3.1 公交超网络构建算法

基于超图的公交超网络中，节点为公交站点，超边代表一条线路中所有的站点集合．采用Java编程程序将数据进行整合，通过算法控制，构建了该公交超网络节点的邻接矩阵和超边的邻接矩阵，以及节点和超边间非对称的关联矩阵．之后采用Python应用程序，基于各矩阵特征，分别分析了网络的度分布、 超度分布、 超边度分布、 聚集系数、 介数值等特征属性.

城市公交超网络构建步骤如下：

1) 初始化：定义超网络中节点集合为vi，超边集合为ek，其中i=1，2，…，n，k=1，2，…，m.

2) 检查超网络中全部的节点，若遍历得到节点vi和vj出现在同一条线路中，那么将节点vi和vj添加到对应的超边ek中.

3) 循环执行步骤2)，直至所有站点和线路数据全部被检索完毕，算法结束.

3.2 公交超网络特性分析

依据超网络的构建算法，本文对西宁市公交站点和线路数据进行收集、 清洗和整理完善，最终得到540个公交站点以及91条公交线路，并分析其拓扑特性．在西宁市公交超网络中，一条线路中最多包含62个站点，一个站点上最多可经过27条线路，该超网络的网络规模适中，其中超度值较大的站点承担公交超网络中大部分的换乘工作.

1)节点度及度分布

公交超网络的站点度值越大表明该站点在整个网络中的连通性就越好．图2是西宁市公交超网络的度分布，其中，少部分节点拥有较高的度值，而大部分节点度值相对较小，整体分布极其不均匀，表明网络中只有少数节点发挥着关键作用．最大的两个度值分别为337和317，对应于五岔路口站和昆仑桥站，这两个站点为西宁市的核心站点，地处城市中心位置，人员流动密集并且道路通达性较好.

图2 西宁市公交超网络的度分布

2) 节点的超度及超度分布

站点的超度值由站点和线路两个数据集同时分析得到，它表示所有线路中途经该站点的线路数目．图3为节点的超度分布，图4是双对数坐标系下超度分布曲线的拟合，结果显示公交超网络的超度分布趋于幂律分布，幂指数Slope=-2.038 3，网络具备BA无标度特性．此外，分析数据集可知，最大的两个超度值为27和26，同样是五岔路口和昆仑桥站，这表明经过这两个站点的公交线路数目较多，该公交站点的换乘量较大，换乘选择更多．结合表1数据得到，站点的超度值和度值是正相关的，节点重要性对于交通拥堵、 换乘选择、 交通网络系统整体的通达性以及抗毁性能等方面都有着重要的意义.

图3 节点的超度分布

表1 站点超度值与度值比较

图4 双对数下的超度分布拟合

3) 超边度及超边超度

超网络模型不仅能识别关键节点，还可以识别关键超边．公交超网络中，如果一条线路邻接其他线路的数量越多，那么通过该线路，乘客换乘到其他站点或是线路的选择性就会更多．超边超度反映的是一条超边中节点的总数，即单条线路所包含的公交站点的总数量，该公交超网络的平均超边超度值为23，即平均每条线路包含23个站点．如图5所示，超边度分布近似于正态分布，说明网络中线路分布较为均匀，表2是超边度值排名前20的线路，分析表中数据得到，超边超度的值也会影响超边度值，因为线路中站点数目越多，其线路邻接其他线路的数量就越多．因此，超边超度值较大的路线，它的超边度值也较大.

图5 超边度分布

表2 超边度值排名前20的线路

关键线路对于市民日常的出行选择以及交通系统对客运量的安排规划有着一定的指导作用.

4) 平均路径长度和聚集系数

平均路径长度描述了从某一站点任意到达其他站点之间的距离，即从站点i抵达站点j时中途需要换乘的线路数量．通过数据计算得到西宁市公交超网络的平均路径长度约为1.91892，近似为2，由此可知，在西宁市从某一站点到另一站点平均换乘两次便可到达．聚集系数反映出线路之间的紧密程度，计算得到该超网络的聚集系数约为0.6953，较大的聚集系数和较小的平均路径长度均表明西宁市交通超网络具有小世界特性.

5)介数

除了节点的度和超度，节点的介数也是衡量节点重要性的指标之一．表3列出了西宁市公交超网络介数值排名前12名的站点．由表1可知，介数值较大的站点的度值和超度值也较高，通过衡量这3个测度，可以准确地识别网络的关键节点．西宁市公交超网络的关键节点分别是昆仑桥站、 五岔路口站．这些关键节点承载了公交超网络大部分的客运量，客流压力较大，如果在这些关键节点处发生交通拥堵或者交通事故，将对整个交通系统的正常运行造成危害，甚至可能会导致整个交通网络瘫痪．结合交通拥堵指数，进一步验证了关键节点对交通拥堵情况的影响．智能CT实时数据显示，西宁市的交通拥堵延时指数为1.47，平均速度为29.41 km/h，按照区域拥堵排名，在四区中最拥堵区域为城西区，拥堵指数为1.75，平均速度为24.81 km/h； 其次为城中区，拥堵指数为1.65，平均速度为25.45 km/h．按照城市商圈拥堵排名，最拥堵区域为虎台区域，拥堵指数为2.02，平均速度为18.38 km/h．在城西区，超度值和介数值较大的站点均占41%以上，而虎台商圈也位于城西区．结果证实，这些关键站点对整片区域甚至整个交通网络的拥堵状况影响甚大，为改善交通拥堵状况，应在这些核心节点处实行分流策略，降低站点处的车流量，缓解交通压力.

表3 介数值排名前12名的站点

本文应用超图的2-section图和线图的理论知识，将公交超网络转化为超图的形式，目的是借助它的2-section图和线图的邻接矩阵，分析得出该公交超网络的度分布、 介数中心性等拓扑属性．学者陆睿敏所构造的公交超网络中，站点为超边，线路为节点，通过与上海市公交超网络的实验结果对比，发现这两个公交超网络均符合小世界特性，有着较大的聚集系数和较小的平均路径长度，线路分布较为均匀，站点分布呈现幂律分布．因此，应用超图的2-section图和线图的理论知识，同样也能准确地分析超网络的结构属性.

4 美团超网络

4.1 美团超网络模型构建

现实世界中，基于网络的超网络更能全面描述整个城市不同类型网络之间的相互连接和制约关系，它的涵盖面更广，节点种类更加丰富，连边关系更加复杂多样．该超网络最早由Kurant等[26]提出，但真正掀起网络科学中相互依存网络研究热潮的是Buldyrev[27]等在2010年Nature上发表的关于相互依存网络级联失效问题的研究，这种相互依存超网络中蕴含着很多的数据信息，在当今大数据时代，超网络为探索不同类型群体之间的相互作用和相互制约等关系提供了有利的分析工具．通过采集现实网络的数据信息，再结合数学图论、 统计学以及动力学等知识就可以构造相互依存超网络，对相互依存超网络进行特性分析，能够挖掘出很多对社会发展有用的重要信息，发现新的商机，对城市经济效益和社会效益等诸多方面带来更大的提升.

基于相互依存网络的理论知识，构造了与公交超网络相依存的美团超网络．该超网络以站点为超边，站点周围2km范围内的美团美食商家为节点，其拥有540条超边和10311个节点，该美团超网络模型的构建算法与公交超网络构造算法一致.

4.2 美团超网络特性分析

对比分析公交站点的超度值以及美团超网络的超边超度值，即站点周围的美团美食商家数目，得出站点的分布与城市经济发展之间的关系．图6显示了站点的超度值与美团商家数目的比较，得到超度值与商家数目成正比关系，即超度值较大的站点周围有较多的商家，经济发展也较为繁华．但也有例外，比如五岔路口站，它的超度值为27，但是附近美团美食商家数仅有两家，这是因为该站点地处五条道路汇聚口，道路繁杂，周边几乎都是道路，只存在少量商户，所以在分析站点超度值和美团商家数的对应关系时，还应该切合实际，结合理论和实际两方面来阐述社会现象．通过两个超网络之间的关联关系，得出站点的分布对于城市经济发展有较大影响，因此，超网络的特性更能反映现实系统之间的关联关系，对真实世界多维系统的研究也更有意义.

图6 站点超度值与美团商家数目对比图

5 公交超网络鲁棒性分析

5.1 超网络的自然连通度

超图的2-section图[H]2中，节点集为V={v1，v2，…，vn}，若在超图H中，两个节点包含在同一条超边中，则这两个节点在[H]2中用一条普通边相连接，因此，该超网络的邻接矩阵A=(aij)N×N就是相对应2-section图的邻接矩阵．由于该矩阵为对称矩阵，则令λ1≥λ2≥…≥λN为A(H)的特征根，称集合{λi}为超图H的邻接矩阵特征谱．在超网络中，该指标结合网络的内部结构，通过计算网络中不同长度闭合路径数目的加权和来刻画网络中替代途径的冗余性，并且该指标在删除节点和超边上是严格单调的，这就能清楚地识别网络在经历每一次攻击后，自然连通度值的细微变化，从而有效地分辨在不同攻击下，网络抗毁性的强弱．更重要的是该测度在网络不连通时仍然有效[7].

由于节点之间的抗毁性来源于网络中替代途径的冗余性，则网络中所有的闭途径数目用超网络邻接矩阵的特征值进行表示，这样网络的鲁棒性就可以通过其邻接矩阵的特征值计算得到，定义超网络的自然连通度为

(7)

其中，λi为超网络邻接矩阵的特征根.

5.2 基于自然连通度的超网络抗毁性分析

本文将自然连通度值作为衡量公交超网络抗毁性的度量指标，结合python程序求解该超网络的自然连通度值并分析实验结果，绘制实验对比图．实验分别设计了在随机攻击和蓄意攻击两种攻击策略下，网络自然连通度值的变化趋势.

1) 随机攻击策略

随机攻击中，分别讨论了节点和超边失效下网络的抗毁性．首先，对节点和超边编号并随机排序； 考虑两种失效方式：① 节点失效下，依据节点编号随机删去10个节点，记录一次数据，直至网络中所有节点删除完毕，实验终止．② 超边失效下，依据超边编号随机删去一条超边，记录数据，直至网络中所有超边删除完毕，实验终止.

2) 蓄意攻击策略

蓄意攻击中，同样考虑了节点和超边两种失效方式．节点失效下，依据两个节点重要性指标，分别比较了节点在基于超度值和介数值两个指标攻击下网络的抗毁性．超边失效下，依据超边重要性指标，即超边度值来衡量网络的抗毁性．首先，依据节点的超度值以及介数值分别从大到小将节点进行排序，随后，从超度值较大的节点开始依次删除，每删除10个节点记录一次自然连通度值，直至所有节点删除完毕，实验结束．基于介数值的攻击同超度值一样．在超边攻击中，按照超边度值从大到小依次对超边进行排序，随后，依次删除1条超边度值较大的超边，每删除1条超边，记录一次实验结果，直至所有超边删除完毕，实验终止.

超网络抗毁性结果如图7所示，随机攻击策略下，分别统计了10次实验结果的数据，即当网络中100个节点失效时，自然连通度值下降了12，网络中10条超边失效时，自然连通度值下降了83．在蓄意攻击中，10次实验后，基于超度值攻击100个节点后自然连通度值下降了69，基于介数值攻击100个节点后自然连通度值下降了77，而基于超度值攻击了10条超边后，自然连通度值下降了76．从实验数据得知，节点攻击中，随机策略下网络抗毁性最强； 其次是对超度值的蓄意攻击，最弱的是基于介数值的蓄意攻击．而在超边攻击中，前14次实验并不能准确判断鲁棒性的强弱，攻击了14条超边后，随机攻击超边的抗毁性要强于基于超边度值的蓄意攻击.

图7 不同条件下自然连通度值比较

5.3 超网络蓄意攻击下的站点减压策略

城市交通网络中，基于站点和线路的蓄意攻击往往会影响交通网络的顺畅运行，小到妨碍市民出行，大到不可预估的经济损失，因此，如何制定策略来提升网络的抗毁能力，显得尤为重要．通过对比分析超网络在随机攻击与基于超度值和介数值的蓄意攻击下网络的受损情况以及核心站点的分布情况，本文提出对公交站点实行减压策略，减少较大超度值站点处的线路通行数量以及客运量，以此来应对蓄意攻击.

站点减压策略主要分为两个步骤：首先，线路实行站点隔站停靠方式，主要是在连续的几个超度值较大的站点之间实行分站停靠，以此来降低核心节点处的线路通行数量，降低网络拥塞几率； 其次，在超度值较小的站点之间可适当增设新的站点，多分配线路，这样可以增强网络的连通度，提升网络的冗余线路数量，为道路拥塞提供多条备选路径，以此缓解交通压力.

针对上述策略，本文对现有的公交超网络进行数据模拟，实验首先增设了100个新站点，分别位于连续的超度值较小的站点之间，同时，对超度值大于10的站点进行隔站线路停靠策略，在新的超网络构造完成之后，同样采取5.2中的攻击策略对新超网络进行攻击，结果如图8所示．通过与未加策略的蓄意攻击结果对比发现，本节提出的站点减压策略确实能有效缓解网络的崩溃压力，其中，基于超度攻击的网络抗毁性仍然强于基于介数的攻击.

图8 站点减压策略下自然连通度值比较

基于超图的公交超网络结构模型不同于普通网络的结构，超网络每条超边内部节点之间是全连接的，相比于普通网络，网络的紧密程度更大，网络中冗余链路也较多．因此，超网络的抗毁性比同规模的普通网络的抗毁性更强，一旦某些节点受到攻击，网络仍有许多备选路径，可维持网络畅通，这也是公交超网络的优势．但是一旦一些关键节点或线路发生交通堵塞或交通事故，就可能导致网络局部甚至全局流通性能下降．因此，通过对站点实行减压策略，再配合对网络规模的调整，就可以有效缓解网络的交通压力，增强网络的抗毁性.

6 结 语

本文基于超图理论构建了城市公交超网络模型，研究了该超网络的节点超度、 超边度、 超边超度、 聚集系数、 平均路径长度以及介数等拓扑属性，并进行了仿真实验，识别了该超网络的关键节点和超边，并基于节点重要性分析了关键节点对城市商圈地理位置的影响和该超网络的鲁棒性，提出了应对蓄意攻击的站点减压策略．实验结果表明，本文所构建的公交超网络具备小世界网络特性，站点的分布反映出城市经济的发展情况．从整体上看，超度值较大的站点周围美团商家数多，而更多的站点周围只有很少甚至没有美团商家，大部分站点附近经济发展力度不够．在公交超网络的抗毁性分析中，节点失效下，网络对随机攻击的承受能力较强，在基于介数值较大节点的蓄意攻击中，鲁棒性最弱．超边失效下，基于超边度值攻击的鲁棒性要弱于随机攻击的鲁棒性．针对这些属性，本文提出的站点减压策略，能够有效恢复蓄意攻击后的超网络，能为交通系统的统筹安排提供参考.