基于复杂网络理论的城市路网脆弱性研究

黄大荣，沈利兵，赵 玲

(1. 重庆交通大学 信息科学与工程学院，重庆 400074;2.杜伊斯堡-埃森大学 自动控制与复杂系统研究所, 杜伊斯堡 47057，德国)



基于复杂网络理论的城市路网脆弱性研究

黄大荣1,2，沈利兵1，赵 玲1

(1. 重庆交通大学 信息科学与工程学院，重庆 400074;2.杜伊斯堡-埃森大学 自动控制与复杂系统研究所, 杜伊斯堡 47057，德国)

首先，介绍了复杂网络的静态统计特性，并以新乡市区路网为例计算了映射后包括度、介数、聚类系数等在内的复杂网络统计特征值。然后，针对城市路网的拓扑特性，以复杂网络理论统计特性为基础，建立了路网脆弱性研究模型。以新乡市路网为例，研究了新乡市路网在随机性攻击和最大度攻击两种攻击策略下路网显示出的脆弱性。最后，通过逐个攻击网络节点的方法定量计算出路网中各个节点对于攻击表现出的脆弱性，通过该方法找到了路网中的关键路段，这对于后交通时代以维护为主体的路网保护具有重要的现实意义。

交通工程；城市路网；关键性路段；复杂网络；攻击策略；脆弱性

0 引 言

城市道路交通网络，不仅是城市的基础设施，也是城市最重要的生命线之一[1]。而稳健的城市交通道路网络则是保障居民顺畅出行和解决交通拥堵的有效手段。然而，当发生异常事件时，路网可能会受到某种程度的影响，直接造成整个城市路网的服务能力下降，从而对人们的生产生活造成不同程度的影响，因此，研究路网的脆弱性对于保障路网的健康畅通和缓解交通拥堵、提高路网的可靠性和健壮性都具有很强的现实意义。

近年来，城市路网脆弱性分析作为路网可靠性工程领域的一个研究热点，得到了很快的发展，一些国内外学者利用复杂网络理论做了相关研究。胡一竑，等[2]在GIS技术和复杂网络理论的基础上，不但对以杭州为代表的4个城市的路网的基本拓扑性质进行了分析，而且分析了城市街道网络的脆弱性，分析结果显示整个网络对选择性攻击表现出较高的脆弱性，但对随机攻击却表现出较好的鲁棒性；P. Luathe，等[3]在复杂网络理论的基础上提出了一种基于敏感性分析的脆弱性测度方法，该方法采用相对可访问性指数作为评测网络中线路重要性的指标，找出了路网中关键性的路段，并在苏福尔斯市和曼谷大都会区的大型路网中得到了应用，验证了该方法较传统研究方法更为快速高效；L. Zhang，等[4]对交通网络的脆弱性和易碎度进行了区分，认为路网的易碎度和网络中的链接有很大关系，而路网脆弱性则取决于路网中关键性的节点和链接。以上研究尽管取得了一定的成果，但是更多地侧重于对路网整体上拓扑特性的研究，缺乏在不同背景下路网以及各个路段脆弱性的定量化分析。

基于此，笔者在分析复杂网络静态统计特性的基础上，以新乡市区道路网络为例，研究了其在随机性攻击和最大度攻击两种攻击策略下路网所呈现的脆弱性，并通过逐个攻击网络中节点的方法定量计算出路网中各个节点对于攻击表现出的脆弱性，通过该方法找出了路网中的关键路线，而这些路线正是路网管理者应重点关注与维护的对象。

1 复杂网络理论统计特性简介

目前，已有大量研究表明交通网络属于复杂网络[5-6]。该网络通常用无向图G(V,E)表示，V代表节点集合，E代表边的集合。用邻接矩阵表示各节点之间相互连接的关系，若节点i和j相连接，则矩阵中的元素aij为1，否则aij为0。

一般而言，描述复杂网络拓扑结构基本特征参量有3个，分别是网络节点的度、节点的聚类系数以及网络平均路径长度[7]。以下对这上述基本参量逐一介绍。

1)节点Vi的度ki定义为与节点Vi有连接关系的路段的数目，其大小反映着该节点在网络中的影响程度，是一个描述网络局部特征的统计量，其度分布用分布函数p(k)来刻画。而网络的平均度则用网络中全部节点度的平均值来刻画。

(1)

式中：N为网络节点数。

3)节点的路径长度定义为从源节点到目的节点所要经历的路段数的最小值，也称作节点间最短路径长度。相应地，定义路网中所有OD对之间路径长度的平均值为网络的特征路径长度。这里用特征路径长度来表示网络的尺寸，具体计算公式为：

(2)

式中：dij为节点i和j之间路径长度。

2 城市道路网络拓扑映射

城市路网是一个特殊的复杂网络，用复杂网络的思想研究路网特性，首先要将真实的城市路网抽象为拓扑模型[8-10]。而构建城市交通网络拓扑模型较常用的方法有两种，原始法和对偶法[2]。其中，原始法是指以城市路网的交叉口为节点，在交通路段上相邻两个节点之间建立领边；对偶法则是指将道路映射为节点，交叉口映射为边。由定义可知，原始法仅仅代表了纯粹地理意义上的连接，而对偶法则高度抽象了道路间的相互联结关系。因此，笔者选取对偶法构建路网的拓扑结构。

以新乡市区道路网络为例，作真实交通网络的拓扑映射。首先在百度地图上截取新乡市区城市路网的结构(图1),包含36条主干道，68条次干道和支路，限于篇幅限制，下述仅仅画出了包含主干道的城市路网截图。

图1 新乡市城市路网主干道结构

由于城市道路交通网络系统极其复杂，要考虑所有对城市道路网络有影响的因素太困难，同时也为了研究的方便，对上图特做出如下假设：

1)只考虑城市路网中的主干道路，且不考虑上下线路区别，即将路网抽象为邻接矩阵中无向图，亦即无向网络。

2)不考虑不同道路的长度和宽度，即不考虑网络中权重问题，把主干道网络抽象为无权网络或者是把所有主干道抽象为权重1的网络。

3)当道路的车道数有两条以上的时候，以车道数是否相同来区分不同道路，若车道数相同则为相同道路，否则为不同道路。

利用Ucient 6.0和Pajek软件对上述包含次干道和支路在内的新乡市区真实路网结构图做拓扑映射，如图2。

图2 新乡市道路网络拓扑映射

对图2网络做如下处理：首先，根据网络拓扑利用对偶法写出邻接矩阵A。其次，编写程序在MATLAB中对A进行计算。最后，得到新乡市区路网复杂网络各统计特性值，如表1。

表1 新乡市城市路网复杂网络统计特性

根据统计结果，可以看出，网络的平均度只有5.5，少数节点的度大于10，说明新乡市路网的道路网络相互交叉的还不是很多；平均路径长度为3.52，说明从一条路段到目的路段大概要经过4条路段才能达到，这与新乡市道路网络建设的还不完善是相对应的。此外，对度做曲线拟合，发现其分布p(k)与幂律分布相似，又因为该网络的特征路径长度相对不大，但是网络的聚类系数较大，所以该网络小世界效应比较明显，于是可以认定这样的网络为典型的无标度网络。

3 路网脆弱性衡量指标的选取

网络脆弱性指标主要用于测度网络由于自身或者外部原因造成系统结构功能下降的程度，反映的是网络功能水平的变化，因而测度指标应具有全局性[11]。同时，某个路段由于受到攻击或自身原因而失效会使得该路段的流量流向其他路段，当流入该路段的流量超过了自身的容限，该路段就会变得拥堵，而该路段的拥堵又会造成流量流向其他路段，造成整个网络的连锁拥堵。因此，找出这些由于路段的失效造成其他路段严重拥堵的潜在路段，可以提前预防整个路网的连锁拥堵。基于此，笔者用网络效率的变化来衡量由于路网失效造成的路网流量和路网结构功能的变化。

网络中任意两个不同节点i和j之间的效率用εij表示：

(3)

式中：dij为节点i和j之间的距离。

当节点i和j不连接时，或i和j有任何一方受到攻击，使原本连接的两个节点变为非连接状态，dij变为∞，此时εij=0，因此，可以用εij=0来表示i和j之间的连接情况。整个网络的效率E用网络所有节点效率的平均值表示，即：

(4)

令ΔE=E攻击前-E攻击后，式中ΔE表示网络性能的下降程度，网络效率相对下降率为：

(5)

式中：e表示网络效率的下降程度。

另外，在仿真过程中会发现，有的网络平均路径指标开始随着遭受攻击节点的比例f的增加会逐渐增大，但是某个时候又会逐渐减少，因此，不宜直接选取网络平均路径作为路网脆弱性度量的指标，基于此，笔者选取网络效率作为度量路网脆弱性的指标。

4 攻击策略的选择

研究证明城市道路交通网络是典型的无标度网络[12-13]。一般地，该网络主要面临两种异常事件的影响：选择性攻击与随机性攻击。随机性攻击通常是指随机选择网络的一个节点进行攻击，然后再攻击其他节点中的一个，直至将所有节点全部攻击完为止。选择性攻击是指有选择地对网络中的节点逐个进行攻击[14-15]。因为节点在网络中的影响程度可以用节点的度来表示，所以笔者选取节点的度的大小作为攻击网络节点的指标。具体策略是首先选取网络中度最大的节点作为第一攻击目标，攻击完以后重新计算网络各节点的度量等级，依旧对度量等级最高的节点进行攻击，这样重复下去，直到网络中所有的节点全部被攻击完为止。通过比较攻击前后网络效率E的改变量ΔE,分析网络功能和结构的变化。

依照随机性攻击和选择性攻击的攻击策略，利用MATLAB软件做仿真结果，见图3、图4。

图3 攻击节点数目N和网络效率

图4 随机性攻击和选择性攻击下网络效率相对变化率

从图3可以看出，与城市路网在随机性攻击的情况相比，在选择性攻击同样数量的道路情况下，其网络效率下降的更快。当蓄意攻击节点数量达到10个的时候，整个网络的效率已经下降到了最初的一半；当选择性攻击节点数量到达50个的时候，整个网络几乎全部瘫痪。而在随机攻击情况下，当攻击节点数量达到30个左右的时候，网络效率才下降到原来的一半；当攻击节点数目达到100个的时候，网络几乎瘫痪。这说明新乡市区道路网络面对选择性攻击表现出更强的脆弱性。

从图4可以看出，随机攻击下的网络效率下降值相对选择性攻击下的网络效率下降值变化的较平缓。在攻击节点数目不至于使网络瘫痪的情况下，选择性攻击网络效率下降值更大，这是因为每次都是选择网络中度最大的节点进行攻击的，这样对网络效率带来的影响也更大，这与图3中选择性攻击情况下的网络效率斜率大于随机性攻击情况下的网络效率的斜率相符合。

5 关键路段的确定

分析道路拥堵的原因可知，由于节点间存在着紧密的耦合关系，一个或某些关键性节点故障的存在，可能会引起网络中其他节点发生故障，最终引起网络中部分节点故障，更严重的后果是引起整个网络的崩溃。因此，找出这些关键性的结点，并注意保护，这对于以信息维护为主体的后交通时代具有重要的现实意义。

对于节点重要度的评价，我们选择的策略是首先攻击网络第1个节点，分析节点攻击后网络的效率E以及网络效率变化量e，与网络没有受到攻击时的E和e的变化情况，然后攻击第2个节点，此时保持第1个节点健全(不受攻击)，分别分析第2个节点受到攻击后网络效率E、网络效率变化量e和网络健全时E，e的变化情况，依此类推，直至网络中所有节点全部被攻击完为止。结果如图5、图6。

图5 攻击节点及其对应的网络效率的变化

图6 攻击节点及其对应网络效率相对变化率

从图5和图6可以看出，攻击不同的节点，网络效率变化量和相对变化量大小是不同的。比如，攻击节点2、节点4和节点1引起的网络效率和网络效率相对值下降都是很大的，这些节点一旦损坏对网络造成的损害都是很大的，因此，这些节点是关键性节点。表2列出了所有节点中相对重要的前20个节点，并对这些节点进行了定量地数值计算。

表2 相对重要的前20个节点统计

表2列出了对网络效率及相对效率改变量最大的20条路段，这些路段一旦发生故障将会对整个城市路网带来很大影响，同时，由表2可以看出，某些度数和聚类系数大的路段引起的网络效率E改变量，小于度数和聚类系数小的路段引起的网络效率E的改变量，这说明路段重要性与该路段的度数和聚类系数没有直接的关系。另外，从表上也可以看出，前20条重要路段中包含了15条主干道路，占到了关键性路段的75%，这说明对于城市路网来说，应注意保护关键性路段，尤其是主干道路，而不用把全部精力和资金放在所有路段上，这会更加有利于路网的畅通与高效运行。

6 结 语

城市路网脆弱性分析对于城市路网可靠性工程来说，是一项既重要又很急迫的工作，对于城市路网的管理维护起着越来越大的支撑作用。在复杂网络理论的基础上研究了城市路网的脆弱性，并以新乡市路网为例，利用复杂网络所特有的两种攻击策略对新乡市道路网络进行攻击；结果表明，新乡市道路网络对选择性攻击表现出更强的脆弱性；最后通过逐个去除路段的方法确定了新乡市区道路网络中的关键性路段，这对交通管理部门进行路段保护维护具有重要的现实意义。

但是，这也仅仅是从理论角度推导出的结论，鉴于文中路段受到攻击即被认为是该路段彻底发生了故障，而真实情况是路段受到攻击时该条道路可能只是部分失效而不至于全部瘫痪，这正是笔者研究的不足之处，也是下一步要解决的重点问题，限于篇幅，在此不做研究，将另文给出。

[1] 涂颖菲,杨超,陈小鸿. 路网拓扑脆弱性及关键路段分析[J]. 同济大学学报：自然科学版, 2010,38(3):364-367. Tu Yingfei, Yang Chao, Chen Xiaohong. Analysis of road network topology vulnerability and critical links [J]. Journal of Tongji University: Natural Science, 2010, 38(3): 364-367.

[2] 胡一竑,吴勤旻,朱道立.城市道路网络的拓扑性质和脆弱性分析[J].复杂系统与复杂性科学, 2009,6(3):69-76. Hu Yihong, Wu Qinmin, Zhu Daoli. Topological Properties and vulnerability analysis of spatial urban street network [J]. Complex Systems and Complexity Science, 2009, 6(3): 69-76.

[3] Luathe P , Sumalee A, Ho H W, et al. Large-scale road network vulnerability analysis: a sensitivity analysis based approach [J]. Transportation, 2011, 38(5): 799-817.

[4] Zhang L, Levinson D. Investing for reliability and security in transportation network [J].Transportation Research Record: Journal of the Transportation Research Board, 2008, 2041: 1-10.

[5] Crucitti P, Latora V, Marchiori M, et al. Error and attack tolerance of complex network [J].Physica A, 2004, 340(1): 388-394.

[6] Sullivan J L, Novak D C, Aultman-Hall L,et al. Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: a link-based capacity-reduction approach [J]. Transportation Research Part A: Policy and Practice, 2010,44(5): 323-336.

[7] 叶青.基于复杂网络理论的轨道交通网络脆弱性分析[J].中国安全科学学报，2012,22(2):122-126. Ye Qing. Vulnerability analysis of rail transit based on complex network theory [J]. China Safety Science Journal, 2012, 22(2): 122-126.

[8] 李永树,刘刚,张帅毅.基于GIS的多粒度复杂网络模型[J] .西南交通大学学报, 2012,47(3): 406-412. Li Yongshu, Liu Gang, Zhang Shuaiyi. Multi-granularity complex network model based on GIS [J]. Journal of Southwest Jiaotong University, 2012, 47(3) : 406-412.

[9] 邓亚娟,杨云峰,马荣国.基于复杂网络理论的公路网结构特征[J].中国公路学报,2010,23(1):98-104. Deng Yajuan, Yang Yunfeng, Ma Rongguo. Highway network structure characteristics based on complex network theory [J]. China Journal of Highway and Transport, 2010, 23(1): 98-104.

[10] Velaga N R, Quddus M A, Bristow A L. Developing an enhanced weight-based topological map matching algorithm for intelligent transport systems [J]. Transportation Research Part C: Emerging Technologies, 2009, 17(6): 672-283.

[11] 杨露萍,钱大琳.道路交通网络脆弱性研究[J].交通运输系统工程与信息,2012,12(1):105-110. Yang Luping, Qian Dalin. Vulnerability analysis of road networks [J]. Journal of Transportation Systems Engineering and Information Technology, 2012,12(1): 105 -110.

[12] 张勇,杨晓光.城市路网的复杂网络特性及可靠性仿真分析[J].系统仿真学报,2008,20(2):464-513. Zhang Yong, Yang Xiaoguang. Complex network property and reliability simulation analysis of urban street networks [J]. Journal of System Simulation, 2008, 20(2):464-513.

[13] 赵月,杜文,陈爽.复杂网络理论在城市交通网络分析中的应用[J].城市交通,2009,7(1):57-64. Zhao Yue, Du Wen, Cheng Shuang. Application of complex network theory to urban transportation network analysis [J]. Urban Transport of China, 2009, 7(1): 57-64.

[14] Barabasi A L, Albert R. Emergence of scaling in random networks [J]. Science,1999, 286(5439): 509-512.

[15] 汪玲,王剑.基于异质结构的复杂交通网络拥塞分析[J].交通运输系统工程与信息,2012,12(2):119-125. Wang Ling, Wang Jian. Congestion analysis of complex traffic network based on heterogeneity [J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(2): 119-125.

Vulnerability Analysis of Urban Road Network Based on Complex Network Theory

Huang Darong1, 2, Shen Libing1, Zhao Ling1

(1. School of Information Science & Engineering, Chongqing Jiaotong University, Chongqing 400074, China;2. Research Institute of Automatic Control & Complex Systems, Duisburg-Essen University, Duisburg 47057, Germany)

Firstly, the statistic characteristics of complex network were introduced, and Xinxiang urban road network was taken as a case study, which calculated the statistical characteristics of complex network, including degree, betweenness, clustering coefficient and etc. Then, according to the topology characteristics of city road network, the model of road network vulnerability research was established by the statistic features of complex network theory. Taking the road network in Xinxiang city as an example, the vulnerability of the road network of Xinxiang city in two attack strategies which were randomly attacked and maximum degree attack were demonstrated. Finally, the vulnerability of every node in the network was calculated when they were attacked by assaulting the network rodes one by one, and the key sections of road network were found out by this algorithm. It is of important and practical significance for the network protection which takes the maintenance as the main body in post traffic times.

traffic engineering; city road network; key sections of road network; complex networks; attack strategy; vulnerability

10.3969/j.issn.1674-0696.2015.01.24

2013-10-13；

2014-03-10

国家自然科学基金项目(61004118,61304104)；重庆市高等学校优秀人才技术计划项目(2014-18)；重庆市教委自然科学基金项目(KJ120422)

黄大荣(1978—)，男，湖北建始人，教授，博士，主要从事交通可靠性工程方面的研究。E-mail：drhuangjs@gmail.com。

U491

A

1674-0696(2015)01-110-06