顾及动态介数优先的城市路网抗毁性分析

黄丞甫，刘 刚,2，牟 标

（1.成都理工大学地球科学学院，四川成都 610059；2.地质灾害防治与地质环境保护国家重点实验室(成都理工大学)，四川成都 610059）

城市道路网络是城市社会经济运行的重要载体，同时也是城市空间形态结构特征的体现，其可靠性或者抗毁性直接关系到城市的安全和可持续发展.城市交通系统功能对维持城市生态系统至关重要[1].面对随机事件（如突发灾害、交通事故、交通拥堵等）或者恶意攻击（即人为蓄意破坏关键道路），路网的连通性或者性能都会受到不同程度的影响，故如何系统分析实际路网的抗毁性一直以来都是复杂网络、交通、地理信息系统等研究的热点和重点问题[2-8].

近年来，学者们针对不同复杂系统的抗毁性进行了广泛讨论[9-11].研究认为，具有无标度特性的复杂网络系统，其抗毁性表现出“鲁棒而又脆弱”的特征，即面对随机攻击具有很强的鲁棒性，但对于蓄意攻击却又非常脆弱[12].随机攻击大量节点，无标度网络可能仍然能保持全局连通；但恶意攻击少量节点，就可能破坏网络的整体连通性并导致系统瘫痪[13-14].公路网的脆弱性表现为运行状态脆弱性和结构脆弱性，可以从网络拓扑结构和运行状态两个因素角度评价路网的整体脆弱性[15-17].从连通度、最大连通子图、网络效率等角度，相关研究探讨了公路网按节点度、点介数和边介数大小进行攻击的鲁棒性[4].从拓扑结构上，连接度和介数中心性都能较好地描述节点或者边在网络中的重要性[18].研究表明，对于公路交通网络，无论是攻击节点还是边，考虑介数优先的攻击策略引起网络功能下降速度最快，攻击效果更好，因此广泛用于路网的鲁棒性分析[19].在攻击策略的选择中，Holme采用了四种不同的攻击策略：根据移除过程中初始网络或当前网络的度和介数中心性降序进行移除.研究发现，动态计算的度和介数中心性的攻击策略，往往比基于初始网络的攻击策略更有害[20].聂廷远等在此基础上探寻了度和介数的相关性，并应用基于初始网络和动态计算的两种攻击策略验证了其效率[21].在抗毁性度量指标方面，平均测地线距离、最大连通子图和网络效能都是常用的评价指标，而网络效能指标在道路网络分析中具有显著优势，其评价效果优于平均路径长度、连通度等指标，进而得到广泛应用[22].

路网抗毁性分析主要是研究路网在不同攻击强度下网络功能的变化，恶意攻击更能揭示重要道路的破坏对路网整体功能的影响.然而，针对城市路网的抗毁性分析，现有的恶意攻击方法主要还是从道路或者节点的原始中心性来考虑其重要度，即基于静态中心性的攻击策略.以介数中心性为例，传统方法关注静态介数情况下的恶意攻击，没有考虑攻击过程中节点或者边介数中心性的变化，导致攻击的目标可能并非当前网络中介数中心性最大的或者最重要的.原始路网中所有道路的介数中心性是确定的，但遭受攻击后，剩余路网的拓扑结构将发生改变，故道路的中心性或重要性也将随之变化.恶意攻击的思想是破坏路网中最为关键的道路，如果整个过程都是按照原始路网的介数中心性进行攻击，难以保证后续攻击的道路是当前路网中最为重要的.

为此，本文将从节点和边的介数中心性角度，顾及在攻击过程中介数中心性的变化，提出基于动态介数优先的公路网抗毁性分析方法.通过动态计算每次攻击后当前网络上所有元素的介数，重新评估节点或者边的重要性，进而确保每次恶意攻击都移除的是当前网络中最为重要的节点或者边，提升恶意攻击的效果，为路网抗毁性分析提供更为科学的参考依据.

1 复杂路网模型拓扑表达方法

为深入研究路网的抗毁性情况，本文利用复杂网络理论从尺度角度设计了两种交通网络模型：基于道路-道路关系的路网拓扑模型、基于节点-节点关系的路网拓扑模型.传统的几何路网模型虽然较好地保留了路网空间形态结构，但不便于利用复杂网络理论研究其拓扑结构特征及实施交通流等动态过程的模拟.同时，外部攻击对路网的破坏可能也存在尺度上的不同，比如单次攻击可能只破坏一个路口（节点）或者一个路段，也可能破坏整条道路.所以，从单次攻击尺度上研究路网在不同攻击尺度下的性能变化，能更加准确刻画路网的抗毁性.

图1所示是两种路网拓扑模型的建模原理.在基于道路-道路关系的路网拓扑模型中，将一条道路抽象为一个节点，如果两条道路相互连接，则在二者对应的两个节点之间产生一条边[23-24].在基于节点-节点关系的路网拓扑模型中，几何路网中的节点对应于该拓扑模型的节点，路段对应于模型中的边且其权重即等于路段的长度.对于前者而言，采用的是对偶图的方式进行复杂路网建模，有助于分析道路之间的连接关系以及整个路网的连通性.对于后者而言，可以准确地计算路网上每个路口和路段的中心性情况.

图1 路网拓扑表达方法Fig.1 Topological representations of an urban road network

2 基于动态介数优先的城市路网抗毁性分析方法

复杂网络的抗毁性指网络功能在各种攻击策略下持续作用的能力，通常被定义为网络上部分节点或边失效后网络整体性能的下降值.理论上，随着公路网上越来越多的节点或者路段失效，路网的整体性能必然呈连续下降趋势.因此，为评价路网的抗毁性，必须对网络的功能或者性能进行合理的度量.传统方法常用网络的平均路径长度（L）来度量网络的功能：

在由N个节点和K条边组成的网络G中，dij表示从节点i到j所需要经过边的最小次数，在网络节点或边被毁坏后，平均路径长度会增大，故网络抗毁性就可以由平均路径长度的增加值来衡量.显然，平均路径长度增加越多，说明网络整体的连通度越不好，所以网络性能显著下降，其抗毁性就越差.然而，实际研究表明，利用平均路径长度表征网络功能变化存在明显缺失，因为随着破坏程度的加剧，平均路径长度呈现“先增后减”的趋势，主要是由于攻击后期网络规模太少导致的，故从全局意义上平均路径长度不适宜用于网络的抗毁性分析[15].研究发现，网络整体效能指标在刻画网络抗毁性分析方面具有更加显著的优势，该指标描述的网络性能随攻击程度呈稳定连续下降趋势.故本文利用该指标进行网络抗毁性分析.

2.1 网络整体效能指标

为准确刻画路网在遭受不同程度破坏下整个网络的抗毁性情况，利用网络整体效能(E()G)指标来进行网络抗毁性的定量分析.一般地，两个节点之间的效能定义为该两点之间时间或距离的倒数：

式中：εij为节点i和j之间的效能，tij为从节点i和j之间的时间成本，dij为两个节点之间的距离成本.这里，默认以距离成本进行效能计算.

则E(G)定义为该网络上所有节点对间效能的平均值：

式中：E(G)为网络G的整体效能，N为网络节点个数.网络整体效能指标广泛应用于网络抗毁性分析，效果优于网络的平均最短路径长度等指标，避免了其他指标随网络破坏程度的加大出现的先变大后变小的缺陷，保证路网抗毁性分析的稳定性和准确性.

2.2 基于动态介数优先的城市路网抗毁性分析算法

2.2.1 基本思想

路网的抗毁性分析通常研究路网在随机攻击和恶意攻击两种模式下网络性能的变化.随机攻击是随机破坏路网上的节点、道路或者路段，恶意攻击一般是破坏路网上连接度较大、介数中心性较大等相关重要的节点、道路或者路段.针对恶意攻击，现有方法是通过对原始路网的所有节点或路段按照某个中心性指标进行重要度排序，然后按重要度从高到低进行攻击.

对于原始路网而言，对节点或者道路的中心性排序确实可以客观地描述其重要程度.然而，在实施恶意攻击后，路网上节点或者道路的中心性将发生变化，难以保证后续攻击的目标为当前网络中最重要的节点或道路，因此动态计算网络元素的重要度并作为下一次攻击的依据更能体现恶意攻击的总体思想和目标.

为进一步阐述该方法，本文设计了一个示意图（图2）以及利用该方法攻击节点后路网上节点重要度（基于介数中心性）排序的变化情况（表1）.

图2 介数中心性动态变化的方法示意图Fig.2 Schematic diagram of method based on dynamic changes of betweenness centrality

根据图2和表1可知：当65号节点被攻击后，在原始路网（图2a）中介数中心性排名第2的节点（编号68），其动态介中心值排名在剩余路网（图2b）中排名下降到第17位，而在原始路网中排名第12位的节点（编号76）上升到第1位；当76号节点被攻击后，在图2b路网中重要度排名第2的节点（编号89）在剩余路网（图2c）中下降到第13位，而之前排名第12的节点（编号94）上升到第1位；当94号节点被攻击，图2c中排名第2的节点（编号87）在剩余路网（图2d）中下降到第8位.经过三次攻击，编号为48的节点从原始路网中排名26上升到排名第1，即图2d中最为关键的节点；反之，原始路网中排名第3的节点（编号84）在经过两次攻击后直接下降到第118位（图2c），即成为剩余路网中不重要的节点.根据该例子可知，实际路网在遭受恶意攻击后，介数中心性的变化非常大，原始路网中一些非常重要的节点在少数几次攻击后就可能变得不重要；而一些之前不重要的节点在剩余路网中会迅速变得很重要.因此，充分考虑路网在遭受攻击后网络节点或者边的重要性变化，其路网抗毁性分析将更为科学、合理.

表1 动态介数优先的恶意攻击方法下节点重要度变化（攻击图2路网节点）Table 1 Changes in the importance of nodes under the targeted attack method based on dynamic changes of betweenness centrality(attacking nodes in the road network in Fig.2)

2.2.2 算法描述

根据上述基本思想，本文提出一种基于动态介数中心性度量的公路网抗毁性评价方法.对于基于道路-道路关系的对偶图和基于节点-节点关系的路网拓扑模型，都可以采用该算法进行抗毁性分析.以基于节点-节点关系的路网拓扑模型为例，抗毁性分析算法的具体过程描述如下：

（1）针对初始路网拓扑模型G=(V,E)，计算路网的整体效能指标E(G)；

（2）根据介数中心性方法计算当前路网中所有节点的介数中心性指标，进而按照介数大小对所有节点进行排序；

（3）攻击当前路网中介数最大的节点vk，从网络中移除该节点及其连接的所有边，更新网络拓扑结构G'=(V',E')；

（4）重新计算剩余路网的整体效能指标E(G')；

（5）回到步骤（2），直到攻击完所有节点.

图3所示为该算法的流程图.在具体的抗毁性分析过程中，如果原始路网规模很大（比如上万个节点），每次攻击若只针对单个点或边，效率会非常低.所以，一般可以采取按比重r攻击，即按照路网规模的一定比例设施单次攻击.这里，比重r的取值对结果有一定影响，r太大（如30%）不能反映路网效能的变化趋势，r太小（如0.01%）计算量会很大.为准确刻画路网整体效能与攻击程度之间的关系，本文认为r取值在1%左右较为合适，这样能在可控的计算规模下得到路网整体效能随攻击程度的连续变化.

图3 基于动态介数优化的路网抗毁性分析算法流程图Fig.3 The flowchart chart of the algorithm with dynamic betweenness centrality priority

3 实验与讨论

3.1 实验数据

以成都市道路网络（图4）为例，根据上述路网拓扑建模方法进行两种网络建模.基于道路-道路关系对偶拓扑模型共包含1484个节点（对应1484条道路）和5073条边；基于节点-节点关系的路网拓扑模型共包含5162个节点和8943条边（对应8943条路段）.本文将针对两种路网拓扑模型进行实验分析，并讨论在不同攻击策略下路网的抗毁性情况.

图4 成都市城市道路网络Fig.4 The road network of Chengdu

3.2 路网抗毁性分析场景设计

为系统分析公路网在不同攻击下网络整体效能的变化，针对基于节点-节点关系的路网拓扑模型，从攻击方式（随机、静态或动态）、攻击目标（节点或边）角度设计了6种攻击场景，具体如下：

（1）随机攻击节点策略.每次攻击实验均随机选择网络上的节点，并计算在不同破坏程度下的网络整体效能损失比例，进而分析路网效能损失比例与攻击比重之间的关系.为保证随机攻击的准确性，进行100组随机攻击试验，并计算每个攻击比重下网络整体效能损失比的平均值.

（2）随机攻击路段策略.即随机攻击网络边，计算在不同破坏程度下的网络整体效能损失比例，分析路网效能损失比例与攻击比重之间的关系.同样，进行100组随机攻击试验并取平均值.

（3）基于静态介数优先的节点攻击策略.根据初始路网计算所有节点的介数中心性，并按照介数从大到小进行节点攻击，计算不同攻击程度下路网的整体效能.该策略下，所有节点的介数中心性是静态的.

（4）基于静态介数优先的路段攻击策略.根据初始路网计算所有路段的介数中心性，并对其进行排序，然后从中心性从高到低进行路段攻击，计算路网整体效能的变化.

（5）基于动态介数优先的节点攻击策略.该攻击场景下，主要根据本文方法进行攻击实验，即每次攻击后都需要重新计算所有节点的介数中心性，并以剩余路网中介数中心性最高的节点作为攻击目标.

（6）基于动态介数优先的路段攻击策略.即根据本文方法动态计算每次攻击后路网上所有路段的介数中心性，确保下一次攻击目标是剩余路网中最重要的路段.

针对基于道路-道路关系的路网拓扑模型，仍然从攻击目标和攻击方式角度采用上述6种攻击策略进行公路网的抗毁性分析.因此，本文共设计了12种攻击场景（表2）.

表2 公路网抗毁性分析攻击场景设计Table 2 Scenarios of the attack experiment

3.3 结果与讨论

3.3.1 基于道路-道路关系的路网拓扑模型抗毁性分析结果

针对成都市道路网络的对偶拓扑模型，完成了上述6种场景下的抗毁性分析实验（图5、图6）.结果表明：①无论是攻击节点还是边，随机攻击策略对路网整体效能影响最小，攻击效果最差，而基于动态介数优先的恶意攻击效果最好.以攻击节点为例，当破坏比重为20%时，随机攻击下路网整体效能降低约为45%，静态介数优先的恶意攻击下路网整体效能降低约为70%，动态介数优先的恶意攻击下路网整体效能降低超过90%.实验结果证实了公路交通网络面对随机攻击的鲁棒性和面对恶意攻击的脆弱性.②对于随机、静态和动态三种攻击策略，攻击节点比攻击边对路网整体效能的影响更为显著.以动态介数优先攻击为例，当攻击比重为15%时，攻击边造成路网整体效能降低约36%，而攻击节点将导致整个路网的效能损失约87%，这是由于在路网对偶图中节点代表的是道路，攻击一条主干道将破坏较多的连接关系，故造成的影响会很大.

图5 基于路网对偶图的随机和恶意去点攻击对比Fig.5 Comparison of random attack and two targeted attacks on nodes based on the dual topological model of road network

图6 基于路网对偶图的随机和恶意去边攻击对比Fig.6 Comparison of random attack and two targeted attacks on edges based on the dual topological model of road network

可见，相比于传统的静态恶意攻击策略，考虑路网动态中心性动态变化的恶意攻击方式能达到更好的攻击效果，其根据原因在于本文方法顾及了在攻击过程中道路、节点或者路段的重要性的变化，能够确保后续的恶意攻击始终破坏的是当前路网中最为关键的部分.这为做好公路网安全防控提供了有力支撑.

3.3.2 基于节点-节点关系的路网拓扑模型抗毁性分析结果

利用本文方法，针对基于节点-节点关系的路网拓扑模型进行了抗毁性实验分析（图7、图8）.与基于道路-道路关系的对偶网络相比，该路网模型是对原始路网的精细表达，即每个路段（弧段）都有一条边与之对应.所以，两种路网模型的攻击尺度（单次攻击破坏程度）存在较大差异：对于道路级别的对偶图，攻击节点将破坏整条道路及其与邻接道路之间的连接关系，攻击边将破坏两条道路之间的连接关系；对于路段级别的网络，攻击节点只破坏该路口及与之连接的多个路段，攻击边只破坏单个路段（而包含该路段的道路上的其他路段不受影响）.基于节点-节点关系的路网模型抗毁性结果表明：①无论是攻击节点还是路段，动态介数优先的恶意攻击策略的攻击效果最好；②对于三种策略，攻击节点比攻击路段能更快地破坏整个路网.当节点攻击比重为15%，动态介数优先的恶意攻击方式下路网效能损失达到80%以上，而静态介数优先方式的破坏程度为65%，随机攻击方式的破坏程度不足40%.当边攻击比重为15%，动态介数优先方式下路网效能损失为55%，而静态介数优先方式的破坏程度为35%，随机攻击方式的破坏程度为15%.

图7 基于节点-节点关系的路网拓扑的随机和恶意去点攻击对比Fig.7 Comparison of random attack and two targeted attacks on nodes based on the node-node topological model

图8 基于节点-节点关系的路网拓扑的随机和恶意去边攻击对比Fig.8 Comparison of random attack and two targeted attacks on edges based on the node-node topological model

根据两种路网模型的攻击实验可知：与随机攻击相比，恶意攻击方式下路网整体效能降低更快；与静态介数优先的恶意攻击相比，基于动态介数优先的恶意攻击方式能更快地破坏路网结构，攻击效果最好.

3.3.3 讨论

城市路网抗毁性分析有助于揭示路网在各种攻击下的可靠性，挖掘攻击各路段后对整个路网的影响，但如何合理地评价公路网的抗毁性是很重要的.面对随机攻击（无论攻击节点还是边），公路网表现出较强的鲁棒性；反之，面对恶意攻击，公路网则表现得非常脆弱.该现象是无标度网络系统通常具有的特性.然而，如果要分析在给定破坏程度（网络整体效能损失比）条件下最佳的攻击策略，即具体破坏哪些关键道路且破坏道路数量尽可能少?随机攻击方式无法解决该问题.但基于网络元素重要度变化的恶意攻击是解决此类问题的一个优解，本文所提出的恶意攻击方法体现了该思想，其抗毁性分析结果也表明该策略对路网整体效能破坏更快，攻击效果比传统恶意攻击策略更为显著.从两种路网模型的抗毁性分析结果可知，在基于道路尺度的对偶图中直接攻击节点对路网造成的影响更大，本质上此时破坏的是一整条道路，从结构上该道路的损毁将破坏许多道路的连通关系，所以导致剩余路网中道路的中心性可能变化较大，这也是在路网对偶图中实施动态介数优先恶意攻击策略产生的影响尤为显著的原因所在.该结论将为评估路网的鲁棒性提供重要理论依据.

4 结语

城市路网抗毁性分析对整个城市交通系统的运行、城市安全以及理解城市功能具有重要意义.传统方法主要从道路、路段或节点的静态重要度角度进行抗毁性分析，然而在实际恶意攻击中路网上各要素的重要度会变化，导致后续攻击目标可能并非是当前网络中最为重要的.针对该问题，本文提出一种基于动态介数中心性优先的城市抗毁性分析方法.该方法通过动态计算路网在遭受攻击后的中介中心值，重新评估各节点和道路在剩余路网中的重要性，为后续攻击提供了依据.为检验该方法的有效性，以实际城市路网为例，分别针对基于道路-道路关系的对偶拓扑模型和基于节点-节点关系的路段网络模型进行面向随机攻击、静态介数优先的恶意攻击和动态介数优先的恶意攻击试验.结果表明，对于两种路网拓扑，无论是攻击节点还是边，动态介数优先的恶意攻击策略表现出更好的攻击效果.该方法为进一步揭示城市路网功能及识别关键道路提供了新的研究思路.