王碧瑶 朱大鹏
(兰州交通大学交通运输学院 兰州 730070)
城市轨道交通是城市公共交通体系的重要组成部分,其促进了城市经济的快速发展,具有绿色、迅速、运量大和准时等优点,是可持续发展的必然选择。但洪水、火灾、地震等自然灾害及公共卫生事件等因素,都会影响城市轨道交通网络的连通性,进而影响客流运输效率。因此,基于复杂网络相关理论研究城市轨道交通网络脆弱性具有很重要的现实意义。
目前,国内外已有众多学者对各类运输网络的脆弱性和鲁棒性展开研究。Yang等[1]认为轨道交通网络的脆弱性是其面对恶意攻击时的生存性。牟能治等[2]基于复杂网络相关知识构建重要度评价模型,研究全国快递网络的脆弱性。张振江等[3]考虑线路等级计算关键节点,分析级联失效情况下铁路快捷货运网络的脆弱性。Rodríguez—Núez等[4]发现边的位置和客流是影响公交网络脆弱性的重要因素。冯树民等[5]考虑了网络受到攻击的严重程度,探索城市轨道交通网络的抗毁性。张兰霞等[6]通过构建高铁服务网、车流网和地理网模型,分析其网络特性及地理网络的可靠性,从规划和运输组织的角度提出保证网络稳定性的建议。Dellible等[7]研讨了多个城市轨道交通网络的鲁棒性,针对不同规模的轨道交通网络提出相应措施以提高其鲁棒性。李搏志等[8]采用LeaderRank算法识别高速铁路网络关键节点,并对网络进行优化。吕文红等[9]论述了通过复杂网络相关理论分析各类交通运输网络可靠性的研究现状。
许多学者通过探索网络中的重要部分研究网络的脆弱性。Luathep等[10]认为脆弱性分析需要识别网络的关键部分,分析这部分受攻击时对网络的影响。Sun等[11]通过计算轨道交通网络特征参数寻找关键节点,构建模型分析级联失效时加权网络的客流分配。于宝等[12]通过构建重要度综合评价指标,识别不同时期高铁网络的关键节点,探索其突发事件下的抗毁性和可靠性。文略等[13]通过构建我国西北地区铁路网络拓扑结构,识别关键节点并分析网络可靠性。薛峰等[14]利用TOSIS法和灰色关联构建节点重要度评价体系,为寻找关键节点提供参考。赵志刚等[15]通过多种攻击策略识别复杂供应链的关键节点并研究其鲁棒性。
既有研究多采用攻击节点的方式研究轨道交通网络的脆弱性,攻击方式过于单一。基于此,笔者结合节点重要度和边重要度计算方法,提出一种基于重要度的混合攻击方法,并构建北京轨道交通网络拓扑结构图,识别关键节点和关键边,模拟节点攻击、边攻击和混合攻击时最大连通子图和网络效率的变化,分析轨道交通网络的脆弱性。
针对节点的攻击也被称为节点攻击,节点攻击会造成对应节点失效,导致与该节点连接的边均失效,攻击后应将与该节点连接的边移除。一个简单网络的节点攻击如图1所示。
针对边的攻击也被称为边攻击,边攻击会造成对应边失效,将该边从网络中移除即可。一个简单网络的边攻击如图2所示。
图2 边攻击前后网络拓扑变化
除上述节点攻击和边攻击,章鹏等[16]提出了一种混合攻击策略,同时攻击网络中一条边和两端节点,避免两端节点通过其他路径连通。这种攻击下,边失效会造成两端节点失效,从而导致与两端节点连接的边均失效。一个简单网络的混合攻击如图3所示。
图3 混合攻击前后网络拓扑变化
2.1 重要度计算方法
复杂网络可以抽象为集合G=(V,L),该网络为无向网络,其中V={v1,v2,…,vn}表示网络中节点的集合,L={l1,l2,…,lm}表示网络中边的集合。
现有研究中蓄意攻击一般按照节点度和节点介数攻击节点,按照边介数攻击边,但仅考虑一个参数不够全面。根据文献[17]中描述的方法,使用重要度衡量各节点和边的重要性,综合考虑节点度和节点介数两个参数。以下为节点重要度确定方法。
首先计算网络的节点度和节点介数,分别对它们进行线性归一化处理。归一化处理公式如下:
(1)
(2)
(1)(2)式中:D(i)和B(i)表示节点vi的度和介数;D"(i)和B"(i)表示归一化后的节点vi度和介数;Dmax和Bmax表示节点度和节点介数的最大值。
将归一化后节点度的1/2次幂和归一化后的节点介数按权重相加,得到节点重要度,节点重要度表示为:
(3)
(3)式中:α表示加权系数,且α∈[0,1];NI(i)表示节点vi重要度。
既有研究中的边攻击一般分为随机边攻击和按照边介数的边攻击。文献[18]认为复杂网络边重要度与两端节点度的乘积呈正相关,两端节点为vi和vj的边重要度表示为:
(4)
(4)式中:EI(i,j)表示基于节点度的边重要度。
通过改进文献中的方法,根据公式(3)计算出的节点重要度,认为复杂网络的边重要度与两端节点的重要度呈正相关,两端节点为vi和vj的边重要度如下:
(5)
(5)式中:EI"(i,j)表示基于节点重要度的边重要度。
2.2 脆弱性评价指标
2.2.1 网络效率
复杂网络节点vi和vj之间距离dij的倒数可以表示两节点间的效率,将vi和vj作为一个节点对,复杂网络的网络效率E(G)则为所有节点对效率的平均值,即所有节点间距离的倒数平均值。城市轨道交通网络的网络效率用来表示客流运输效率,并且0≤E(G)≤1,网络效率越高,客流运输效率越好,当E(G)=0时,网络不连通,当E(G)=1时,网络中任意两个节点都是直接相连的。网络效率E(G)表示为:
(6)
2.2.2 最大连通子图比
复杂网络的节点或边受到连续攻击时,连通的网络会被分割为多个独立的子网络,其中节点数最多、规模最大的网络被称为最大连通子图。复杂网络受到攻击后最大连通子图的节点数nmax和初始连通网络的节点数n的比值被称为最大连通子图比,用来表示复杂网络的连通性。城市轨道交通网络的最大连通子图比是用来衡量城市轨道交通网络遭受攻击后网络连通性和网络规模大小的重要指标。最大连通子图比C表示为:
(7)
2.3 攻击步骤
采用节点重要度和边重要度计算方法,选用节点攻击、边攻击和混合攻击三种攻击策略,对复杂网络进行攻击,计算脆弱性评价指标,研究复杂网络的脆弱性。步骤如下:
1.计算网络中节点度和节点介数,并对其进行归一化处理;
2.计算所有节点的重要度;
3.判断采用的攻击方式是否为节点攻击,若是则转步骤4,否则转步骤6;
4.按照节点重要度对网络中所有节点进行降序排列,并分析排序结果;
5.采用节点攻击策略,根据步骤4的排序结果连续攻击对应节点,并计算网络效率和最大连通子图比,计算完成后转步骤11;
6.计算所有的边重要度;
7.按照边重要度对网络中所有边进行降序排列,并分析排序结果;
8.判断采用的攻击方式是否为边攻击,若是则转步骤9,否则为步骤10;
9.采用边攻击策略,根据步骤7的排序结果连续攻击对应边,并计算网络效率和最大连通子图比,计算完成后转步骤11;
10.采用混合攻击策略,根据步骤7的排序结果连续攻击对应边和节点,并计算网络效率和最大连通子图比,计算完成后转步骤11;
11.结束攻击。
以上攻击流程如图4所示。
图4 基于重要度的蓄意攻击流程图
以北京轨道交通网络为例,模拟节点攻击、边攻击和混合攻击三种攻击策略对复杂网络产生的影响,模拟突发事件造成轨道交通网络车站或线路失效的情况,分析城市轨道交通网络的脆弱性。
北京轨道交通网络如图5所示,将轨道交通网络中的车站作为复杂网络的节点,车站与车站之间的线路作为复杂网络的边,二者结合构建城市轨道交通网络拓扑图。北京城市轨道交通网络特征参数如表1所示。
表1 北京轨道交通网络拓扑特性基本指标
3.1 城市轨道交通网络重要度分析
根据上一章提到的方法计算北京轨道交通网络中各节点重要度和边重要度。权重系数α∈[0,1],取小数点后一位,共有11个值,对比不同取值时攻击后的网络效率大小,取攻击后网络效率最小时对应的权重,此时权重系数α=0.1。此时各节点重要度特征和边重要度特征如表2和表3所示,其累计概率分布图如图6和图7所示。按照节点重要度和边重要度从大到小的顺序依次排列,找出重要度最大的10个节点和10条边,并标记它们,如图5所示。
表2 北京轨道交通网络节点重要度特征分析重要度区间节点特征(0.3,0.4)连接一个方向,即交通网络中始末站(0.5,0.6)连接两个方向,即交通网络的中间站(0.6,0.7)大部分连接三个方向,即两条线路的枢纽站(0.7,0.8)连接四个方向,即两条线路的换乘站(0.8,1.0)大部分连接五到六个方向,即三条线路的换乘站表3 北京轨道交通网络边重要度特征分析重要度区间边特征(0.10,0.20)一端为新路的始末站,一端为中间站(0.20,0.31)两端均为连接两个方向的中间站(0.31,0.38)一端为中间站,一端为连接三个方向的枢纽站(0.38,0.44)大部分一端为换乘站,一端为中间站(0.44,1.00)大部分两端均为换乘站或枢纽站
3.2 攻击方式
通过对复杂网络进行攻击研究城市轨道交通网络的脆弱性,攻击或干扰复杂网络节点或边可以降低复杂网络的效率连通性,攻击方式可以分为随机攻击和蓄意攻击。攻击方式特征对比如表4所示。
表4 攻击方式特征对比
采用节点攻击、边攻击和混合攻击三种攻击策略,每种攻击策略下又分为四种攻击方式,分别是随机攻击、节点度攻击、边介数攻击和重要度攻击,分别模拟轨道交通网络受到攻击后的指标变化情况,对比分析轨道交通网络在不同攻击时的脆弱性。
3.3 节点攻击结果分析
节点攻击时北京轨道交通网络最大连通子图比变化图和网络效率变化图如图8和图9所示。
图9 节点攻击下北京轨道交通网络网络效率E(G)的变化情况
随着攻击节点比例逐步增加,C和E(G)不断降低。四种攻击方式下,随机攻击对C和E(G)影响较小,按照重要度攻击时C和E(G)下降最快,攻击50个节点,即攻击节点比例达到13.6%时,C已下降至0.1以下,E(G)下降至0.01以下,网络彻底瘫痪。
3.4 边攻击结果
边攻击下北京轨道交通网络最大连通子图比变化图和网络效率变化图如图10和图11所示,其中节点度攻击表示基于节点度的边重要度攻击策略,重要度攻击表示基于节点重要度的边重要度攻击策略。
图10 边攻击下北京轨道交通网络最大连通子图比C的变化情况图11 边攻击下北京轨道交通网络网络效率E(G)的变化图情况
在四种攻击方式下,随机攻击和边介数攻击时C和E(G)变化较为平缓,按照重要度攻击时C和E(G)下降最快。按照重要度累计攻击170条边,即攻击比例达到40%时,C下降至0.1以下,E(G)下降至0.01以下,轨道交通网络彻底崩溃。对比节点攻击,可以发现边攻击下C和E(G)变化较为平缓,攻击次数相同时,节点攻击的效率高于边攻击的效率。这是由于节点攻击会导致与该节点连接的所有边失效,边攻击只会使对应边失效,而95%的节点连接两个及两个以上的方向,从而导致两种攻击策略效率不同。
3.5 混合攻击结果
混合攻击下北京轨道交通网络最大连通子图比变化图和网络效率变化图如图12和图13所示,其中节点度攻击表示基于节点度的边重要度攻击策略,重要度攻击表示基于节点重要度的边重要度攻击策略。可以明显看出相比随机攻击,蓄意攻击时C和E(G)的下降速度更快。三种蓄意攻击下,按照重要度攻击时C和E(G)变化最快,攻击至35次,即按照边重要度攻击35对相邻的节点,C下降至0.1以下,E(G)下降至0.01以下,网络瘫痪。对比节点攻击可以发现,攻击次数相同的情况下,混合攻击的效率高于节点攻击,这是由于单次混合攻击和节点攻击的节点数目,因此两种攻击策略效率不同。
图12 混合攻击下北京轨道交通网络最大连通子图比C的变化情况图13 混合攻击下北京轨道交通网络网络效率E(G)的变化情况
3.6 城市轨道交通脆弱性分析
相比随机攻击,蓄意攻击对轨道交通网络的破坏程度更大。三种蓄意攻击方式下,边介数攻击对轨道交通网络的影响最小,节点度攻击次之,略高于重要度攻击,重要度攻击下轨道交通网络最容易崩溃。这是由于关键节点或边受到攻击会严重破坏网络的连通性,从而迅速降低网络效率和最大连通子图比。
比较三种攻击策略的结果分析发现,在相同的攻击次数下,混合攻击时轨道交通网络更加容易崩溃,节点攻击次之,边攻击对轨道交通网络的破坏最小。由此认为混合攻击的攻击效率优于节点攻击和边攻击。
(1)基于复杂网络相关理论,构建城市轨道交通网络拓扑结构,分析北京轨道交通网络的脆弱性。结果表明:三种攻击策略下,蓄意攻击对轨道交通网络的破坏程度一般高于随机攻击。
(2)结合节点度和节点介数构造重要度计算方法,找到北京轨道交通网络中的关键节点和关键边,发现关键节点和关键边持续失效会造成网络迅速崩溃,应加强对应车站和区间的应急防护,制定车站和区间失效的应急策略,降低突发事件对轨道交通网络连通性和运输效率的影响。
(3)相比节点攻击和边攻击,混合攻击的攻击效率更高,轨道交通网络更加容易崩溃,但混合攻击的攻击成本高于其他两种攻击方式。
(4)虽分析了三种攻击策略,但均未建立统一的指标度量攻击成本,也未考虑客流对车站和线路重要性的影响,为此进一步研究这些因素对轨道交通网络脆弱性的影响将具有实际意义。
猜你喜欢 介数子图脆弱性 临界完全图Ramsey数同济大学学报（自然科学版）(2019年2期)2019-04-02煤矿电网脆弱性评估电子制作(2017年10期)2017-04-18杀毒软件中指令虚拟机的脆弱性分析电信科学(2016年10期)2016-11-23基于频繁子图挖掘的数据服务Mashup推荐电子科技大学学报(2016年2期)2016-08-31基于攻击图的工控系统脆弱性量化方法自动化学报(2016年5期)2016-04-16基于电气介数的电力系统脆弱线路辨识通信电源技术(2016年3期)2016-03-26树形网络的平均介数*网络安全与数据管理(2014年3期)2014-11-10不含2K1+K2和C4作为导出子图的图的色数华东师范大学学报（自然科学版）(2014年1期)2014-04-16基于电流介数的电力系统脆弱性评估电测与仪表(2014年12期)2014-04-04基于电气介数的继电保护定值在线校核电测与仪表(2014年8期)2014-04-04