留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

运用复杂网络方法分析城市道路网的鲁棒性

田晶 方华强 刘佳佳 赵风 任畅

田晶, 方华强, 刘佳佳, 赵风, 任畅. 运用复杂网络方法分析城市道路网的鲁棒性[J]. 武汉大学学报 ( 信息科学版), 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
引用本文: 田晶, 方华强, 刘佳佳, 赵风, 任畅. 运用复杂网络方法分析城市道路网的鲁棒性[J]. 武汉大学学报 ( 信息科学版), 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
TIAN Jing, FANG Huaqiang, LIU Jiajia, ZHAO Feng, REN Chang. Robustness Analysis of Urban Street Networks Using Complex Network Method[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
Citation: TIAN Jing, FANG Huaqiang, LIU Jiajia, ZHAO Feng, REN Chang. Robustness Analysis of Urban Street Networks Using Complex Network Method[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334

运用复杂网络方法分析城市道路网的鲁棒性

doi: 10.13203/j.whugis20150334
基金项目: 

国家自然科学基金 41701439

详细信息
    作者简介:

    田晶, 博士, 讲师, 主要研究方向为地图自动综合和空间数据挖掘。tianjing_sres@whu.edu.cn

    通讯作者: 任畅, 博士生。imrc@whu.edu.cn
  • 中图分类号: P208

Robustness Analysis of Urban Street Networks Using Complex Network Method

Funds: 

National Natural Science Foundation of China 41701439

More Information
    Author Bio:

    TIAN Jing, PhD, lecturer, specializes in automated map generalization and spatial data mining. E-mail: tianjing_sres@whu.edu.cn

    Corresponding author: REN Chang, PhD candidate. E-mail: imrc@whu.edu.cn
图(4) / 表(2)
计量
  • 文章访问数:  1021
  • HTML全文浏览量:  185
  • PDF下载量:  210
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-06-30
  • 刊出日期:  2019-05-05

运用复杂网络方法分析城市道路网的鲁棒性

doi: 10.13203/j.whugis20150334
    基金项目:

    国家自然科学基金 41701439

    作者简介:

    田晶, 博士, 讲师, 主要研究方向为地图自动综合和空间数据挖掘。tianjing_sres@whu.edu.cn

    通讯作者: 任畅, 博士生。imrc@whu.edu.cn
  • 中图分类号: P208

摘要: 道路网的鲁棒性分析有助于预防或者降低恐怖袭击、自然灾害以及交通拥堵造成的损失。从开放街道地图上获得世界范围内的50个城市道路网,沿用复杂网络鲁棒性分析方法,运用连续删除模型和级联模型对以道路链相交关系表示的城市道路网进行了鲁棒性分析,同时对路网的鲁棒性与其拓扑模式间的关系进行了探讨。研究发现,对于路网的鲁棒性,运用连续删除模型和级联模型所得到的鲁棒性结果存在差异。其中,连续删除模型的道路网鲁棒性普遍较差;而级联模型的鲁棒性,不同路网之间的差别较大;对于同一模型下的度策略和介数策略,介数策略的破坏性大于度策略。对于路网鲁棒性与其拓扑模式的关系,在连续删除模型下,路网鲁棒性与度相关性呈现显著正相关,无标度与非无标度的路网鲁棒性有差异;在级联模型下,路网鲁棒性与度相关性不相关,无标度与非无标度的路网鲁棒性差异不显著。

English Abstract

田晶, 方华强, 刘佳佳, 赵风, 任畅. 运用复杂网络方法分析城市道路网的鲁棒性[J]. 武汉大学学报 ( 信息科学版), 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
引用本文: 田晶, 方华强, 刘佳佳, 赵风, 任畅. 运用复杂网络方法分析城市道路网的鲁棒性[J]. 武汉大学学报 ( 信息科学版), 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
TIAN Jing, FANG Huaqiang, LIU Jiajia, ZHAO Feng, REN Chang. Robustness Analysis of Urban Street Networks Using Complex Network Method[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
Citation: TIAN Jing, FANG Huaqiang, LIU Jiajia, ZHAO Feng, REN Chang. Robustness Analysis of Urban Street Networks Using Complex Network Method[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
  • 复杂网络的鲁棒性分析是研究当网络受到蓄意攻击或出现随机故障时,网络中节点间的连接程度受到的破坏以及通信传输行为受到的影响[1],其研究主要集中在静态鲁棒性和动态鲁棒性两个方面[2]。静态鲁棒性是研究删除一部分节点或边对网络连通性的影响;动态鲁棒性则是研究复杂网络上的雪崩效应与级联效应,即删除一个节点对其他节点负载的影响。蓄意攻击表现为删除网络中重要的节点或边,而随机故障表现为随机删除网络中的节点或边[1-2]。与复杂网络的其他应用领域相似,道路网可自然地建模为网络。根据网络表达的不同,道路网拓扑模式分析的模型主要有原图法和对偶法[3-5]两种。原图法是指图的节点对应于道路交叉点和端点,图的边对应于路段;对偶法是指图的节点对应于道路或道路链(stroke),图的边对应于道路或stroke间是否具有相交关系,近年来还出现了基于社区结构的新视角[6]。基于stroke的对偶法超脱了原有网络的几何表示,更关注于其拓扑组织,有助于揭示隐含结构,仍然是目前应用最广泛的一种路网表达形式[3]

    道路网鲁棒性涉及在受到破坏和出现故障时保持路网功能的能力,道路网的鲁棒性分析有助于预防或者降低恐怖袭击、自然灾害以及交通拥堵造成的损失[6]。不同研究领域的学者作了很多有益的研究,提出了若干衡量道路重要性和鲁棒性的指标[7-10]。道路网鲁棒性分析的一种常用方式是沿用复杂网络领域的分析方法。文献[11]对欧洲41个自组织城市路网和文献[6]在3个粒度上对世界范围内6个城市的鲁棒性分析均是采用复杂网络鲁棒性分析的方法; 文献[12]采用平均最短路径随节点删除的变化对长沙77条街道组成的路网对偶图的网络弹性进行了分析; 文献[13]则运用随机故障和蓄意攻击的3种不同策略对武汉城市圈的城乡公路网进行了稳定性研究。然而,已有的运用复杂网络分析路网鲁棒性的样本研究数据不全面(即对整个城市进行分析的样本数量较小[6, 13],样本数量较大的研究针对的仅仅是城市的某一个部分[11]),分析模型单一(一般使用连续删除模型及其不同策略),并未考虑其他鲁棒性分析模型(如级联模型[14])。大样本城市道路网的鲁棒性以及受不同鲁棒性模型、不同攻击策略的影响是本文关注的第1个问题。研究显示,无标度网络表现出对随机故障的健壮性和蓄意攻击的脆弱性[1-2, 14],同配网络表现出对蓄意攻击的健壮性[11, 15],路网的鲁棒性与这两种拓扑模式的关系是本文关注的第2个问题。

    自发地理信息(volunteered geographic information, VGI)的发展为大规模的地理分析提供了丰富的数据,开放街道地图(OpenStreetMap, OSM)是其典型的成功案例[16]。尽管OSM数据质量存在一定问题[17-20],但有学者认为它可与国家测绘系统或商业公司提供的数据相媲美[16],而且已有很多成功应用[6, 16, 21]。本文从OSM上获得大样本的城市道路网数据,沿用复杂网络鲁棒性分析方法,对以stroke相交关系表示的城市道路网进行了不同攻击模型下的鲁棒性分析,同时对道路网的鲁棒性与其拓扑模式间的关系进行了探讨。

    • 本文选取世界范围内的50个城市的道路网数据(来源于http://metro.teczno.com),这些城市的选取既考虑了OSM道路数据的完整性,又结合了大洲分布、历史起源和城市规模。

      在道路网拓扑分析中常采用道路同名法和每对最大适合、自身最大适合和自身适合等策略生成stroke[22],在道路网综合研究中还考虑了道路等级的生成方法[23]。由于道路名和等级信息经常缺失,自身最大适合以及自身适合策略产生的stroke集不确定[22],故本文选用最大适合策略生成stroke,连接角度阈值由经验值设为60°[24],随后根据其相交关系形成对偶图。该对偶图是基于stroke的拓扑表达,图的节点对应于stroke,图的边对应于stroke的相交关系。

    • 本文主要关注道路网在受到蓄意攻击时的静态鲁棒性和动态鲁棒性。介数和度分别描述了网络中节点重要性的不同方面[2]。节点的介数B(r)是网络中任意两个节点间最短路径经过该节点的平均比例,在路网中度量了该stroke处于其他路段之间的程度,其表达式为:

      $$B(r) = \frac{1}{{(n - 1)(n - 2)}}{\sum\limits_{p, q \in [1, n\} p \ne q:q \ne r}}\frac{{{m_{pq}}(r)}}{{{m_{pq}}}} $$ (1)

      式中,mpq表示节点pq间最短路径的数量;mpq(r)表示节点pq间最短路径中经过节点r的数量;n为节点总数。节点的度D(r)是该节点具有的连接数,在路网中表示与该stroke相交的其他路段的数量,其表达式为:

      $$D(r) = \sum\limits_{p = 1}^n I (r, p) $$ (2)

      式中,I(r, p)表示节点rp之间是否有边相连,有则为1,否则为0。

      本文在静态分析中采用连续删除模型,对节点进行排序后逐点删除,评价其对网络功能的破坏,每次删除节点后重新计算节点的度和介数。删除顺序有介数和度两种策略,分别以介数或度降序排列。若介数最大的节点有多个,则选择度高的节点进行删除;若度最高的节点存在多个,则选择介数大的节点进行删除。本文在动态分析中采用文献[14]提出的级联模型,此类模型[25]的原理为:首先有针对性地删除一个重要节点,然后对其他节点的载荷进行重分配。重分配导致部分节点载荷高于负载能力而失效,其载荷被分配到其他节点,产生级联崩溃。设节点r的载荷Lr为经过该节点的最短路径的数量,负载能力Cr为该节点能承受的最大载荷,则:

      $${C_r} = \left( {1 + \alpha } \right){L_r} $$ (3)

      式中,r=1, 2…nα为容差参量,一般小于0.5。删除起始节点或节点失效后更新剩余节点的载荷,若Lr > Cr,那么节点r失效。重复此过程, 直到最后剩余的所有节点的载荷均小于等于其负载能力。级联模型中,介数策略和度策略分别指以介数最高和度最高的节点作为级联起始节点的删除方式,存在多个最大值情况的处理方式与连续删除模型类似。

      常用评价网络功能的指标有平均路径长度、全局效率、最大连通分支相对大小、孤立分支平均大小等[1, 25-26]。由于平均路径长度在描述非连通图上存在缺陷[26],而全局效率对于不同的图不具备可比性(不同道路网初始的全局效率不同),所以本文选择最大连通分支相对大小和孤立分支平均大小作为网络功能的评价指标。最大连通分支相对大小S是指最大的连通分支所包含的节点数与原图中的节点数的比值。该指标考虑了网络中边的连接情况,可以度量网络中节点间的连接程度受到的破坏情况。假定初始道路网是连通图,那么该值为1。孤立分支平均大小<s> 是指除去极大连通分支外的孤立分支的平均节点规模。假定初始路网为连通图,那么该值定义为0;如果所有节点之间彼此均不连通,那么该值为1;其余情况该值均大于1;该值达到峰值代表路网崩溃达到临界点[1]。在连续删除模型下,参照文献[11]的实际做法,定义S=0.5时的删除节点比例fS、孤立分支平均大小达到峰值时的删除节点比例f<s>为描述网络鲁棒性的指标,显然fSf<s>越大,网络鲁棒性越强。由于级联模型中级联效应会自动停止,所以在容差α条件下级联效应停止时,网络最大连通分支的相对大小Sα可作为评价网络鲁棒性的指标,其中α值为0.1、0.2、0.3、0.4、0.5。 <s> 在连续删除过程中达到峰值时的删除比例可以衡量网络鲁棒性,而级联模型每次崩溃删除的节点为多个,不能获得<s>达到峰值的状态,所以级联模型未采用<s>。

      综上,本文采用的鲁棒性分析模型为连续删除模型和级联模型,每种模型均采用基于度和基于介数两种策略。连续删除模型中,度量鲁棒性的指标为最大连通分支相对大小S=0.5时的fSf<s>,级联模型中度量鲁棒性的指标为级联停止时网络的Sα值。

    • 无标度特性指网络的度分布服从幂律分布,一般幂指数的绝对值为2~3,偶尔会超出该范围[27]。如果一组数据的概率密度分布满足p(x)∝x-β的形式,则该组数据遵循幂律分布,其中β为幂指数的绝对值。本文采用文献[28]提出的幂律分布判断方法,对网络中所有节点的度进行计算得到系数βp值。其中β由最大似然法得到;p值则是基于Kolmogorov-Smirnov检验的拟合优度检验结果得出,p值越大,模型越优,p值大于0.05时,接受原假设, 即数据分布符合幂律分布模型[21]

      现实世界中的一些网络呈现出度高的节点倾向于与度高的节点相连的现象,表现为度相关性的同配;另外一些网络呈现出度高的节点倾向于与度低的节点相连,表现为度相关性的异配。当然,还有一些既不呈现同配也不呈现异配的网络[15]。本文选择Litvak-Hofstad同配性系数描述网络的度相关性。用随机变量JK表示总边数为M的无向图中某边连接的两个节点的度。对于边ijiki是边i的两端节点的度,令tijtik表示边i的两端节点度排序后的序,由于边的两端节点是无序的,故以1/2的概率随机记录可能的出现顺序,Litvak-Hofstad同配性系数ρ的计算公式为:

      $$\begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\rho = \\ \frac{{\sum\limits_{i = 1}^M {\left[ {t_i^j - (M + 1)/2} \right]} \left[ {t_i^k - (M + 1)/2} \right]}}{{\sqrt {\sum\limits_{i = 1}^M {{{\left[ {t_i^j - (M + 1)/2} \right]}^2}} \sum\limits_{i = 1}^M {{{\left[ {t_i^k - (M + 1)/2} \right]}^2}} } }} \end{array} $$ (4)

      式中,ρ > 0时,代表网络同配;ρ < 0时,代表网络异配;ρ=0,则表示网络不相关。

    • 图 1显示了连续删除模型下的路网鲁棒性,横坐标表示删除节点的比例f,纵坐标表示极大连通分量相对大小S和孤立分支平均大小 <s> 。介数策略下,fS的范围为0.000 7~0.030 3,f< s >范围为0.000 1~0.033 9;度策略下,fS的范围为0.004~0.117 2,f< s >范围为0.000 2~0.161 1。

      图  1  连续删除模型下的路网鲁棒性

      Figure 1.  Street Network Robustness Under Consecutive Attack Model

      图 1的曲线变化趋势可以明显看出,度策略下S的下降趋势较介数策略慢,而 < s > 达到峰值时删除节点的比例f<s>也比介数策略大。从曲线的变化速率可以看出,度攻击策略的破坏性弱于介数策略。比较度策略和介数策略的fS,其中所有路网的度策略fS均大于介数策略;比较度策略和介数策略的f<s>,其中88%的城市路网度策略的f<s>大于介数策略。对介数策略和度策略下的鲁棒性指标fS进行单因素方差分析,结果p值小于0.01,箱图如图 2(a)所示;对两种策略下的鲁棒性指标f<s>进行单因素方差分析,结果p值小于0.01,箱图如图 2(b)所示,进一步验证了度攻击策略的破坏性弱于介数策略的结论。

      图  2  两种策略鲁棒性比较

      Figure 2.  Comparison of Robustness Under Two Strategies

      在连续删除模型下,路网表现出较为脆弱的特性。这可以归因于大多数路网都呈现出异质性的特征。度分布具有很强的异质性,导致遭遇度攻击策略时,少数高度节点失效后,整个路网迅速崩溃;而介数的异质性更为明显,高介数和低介数的两极分化现象较度分布更为严重,这导致遭遇介数攻击策略时,极少数的高介数节点失效后,路网面临迅速崩溃。

    • 图 3(a)图 3(b)分别显示了以城市库里蒂巴为例的基于介数和基于度的级联模型及其对应的S,横坐标代表不同容差值α,纵坐标表示S值。总体而言,S值随着容差增大而增大,但部分城市会出现随着容差增大而S值减小的情况,如图 3(a)所示,当容差从0.2增大到0.3时,库里蒂巴的S值反而下降。这种小范围的下降是由于负载动态更新引起的。虽然容差增大,但触发级联效应的顺序不同、单次级联失效的节点个数不同均会产生这种现象。

      图  3  级联模型下的路网鲁棒性

      Figure 3.  Street Network Robustness Under CascadeAttack Model

      比较同一城市的介数策略与度策略,发现同一容差值度策略下的S通常大于介数策略下的S。以容差0.1为例,介数策略下,50个城市S的平均值为0.166,小于度策略下的平均值0.249,其他容差情况类似。对介数策略和度策略下的鲁棒性指标Sα进行单因素方差分析,发现不同容差下的p值均小于显著性水平0.01,故可认为级联模型下的介数策略和度策略的鲁棒性具有显著差异。同时,有26个城市介数策略和度策略的鲁棒性排名差异较大(排名相差大于10),可能是由于负载与介数有直接关联而与度没有直接关联,所以最大度节点与最大介数节点的不一致造成了介数策略和度策略路网鲁棒性的不同。

    • 由于连续删除模型和级联模型的鲁棒性衡量指标的实际意义不同,无法直接比较数值大小,所以将各自指标的数值转换成排名进行比较。

      图 4为介数策略和度策略下连续删除模型和级联模型的鲁棒性排名散点图,纵坐标表示级联删除模型容差为0.1时的鲁棒性排名(其他容差值的情况类似),横坐标分别为fSf<s>的排名。从图 4中可以看出,连续删除模型与级联模型下,城市路网鲁棒性的相关性较弱,这表明道路网的鲁棒性具有模型敏感性。

      图  4  连续删除模型和级联模型下的路网鲁棒性排名

      Figure 4.  Rank Changes of Street Network Robustness Under Consecutive and Cascade Attack Models

    • 计算Litvak-Hofstad同配性系数与路网鲁棒性之间的相关系数,结果见表 1。总体而言,在连续删除模型下,同配路网的鲁棒性强于异配网络,表 1表明Litvak-Hofstad同配性系数与网络的鲁棒性正相关。在级联模型下,未发现上述规律,可能是由于两种模型的机制不同。在连续删除模型中,每次删除最重要的道路,假定道路网呈现同配,则高度道路网构成核,正如文献[15]所提,互相连接的高度节点构成核会增强网络的鲁棒性。然而,运用级联模型时,对于同配网络,假如高度节点与高负载节点具有一致性,删除高度节点,其流量将会重新分配到核中的其他节点,导致其他节点出现流量超过载荷,进而引发整个核的迅速崩溃,使同配网络的鲁棒性弱于异配网络;假如高度节点与高负载节点不一致,删除高度节点对高负载节点可能没有影响,故在运用级联模型时呈现出与连续删除模型不同的现象。

      表 1  Litvak-Hofstad同配性系数与鲁棒性指标的相关系数

      Table 1.  Correlation Coefficients Between Litvak-Hofstad Assortativity Coefficients and Robustness Indexes

      模型 策略 参数 容差α 相关系数
      连续删除 介数 fS 0.497***
      f<s> 0.412***
      fS 0.670***
      f<s> 0.608***
      级联 介数 Sα 0.1 -0.241
      0.2 -0.289**
      0.3 -0.280**
      0.4 -0.064
      0.5 0.072
      0.1 0.011
      0.2 -0.092
      Sα 0.3 -0.168
      0.4 -0.041
      0.5 0.053
      注:—表示模型没有该参数,**表示显著性水平0.05,***表示显著性水平0.01

      对于路网的度分布,50个路网中有31个呈现无标度特性,与文献[29]提到的普遍性有一定差异。根据是否呈现无标度特性将路网分成两组,运用单因素方差分析检验两组路网鲁棒性的差异,结果如表 2所示。由表 2可知,在连续删除模型下,无论选用何种策略,两组路网的鲁棒性在90%水平下差异显著;而在级联删除模型下,两组路网的鲁棒性差异不显著,表明度分布对级联模型下的路网鲁棒性没有影响。这与前人研究结论有差异[1-2, 14],可能是因为本文实验中道路网的规模差异较大,而前人研究的模拟数据通常是节点数相同或相近的网络。

      表 2  无标度特性对路网鲁棒性影响的单因素方差分析p

      Table 2.  p-Values for One-Way Analysis of Variance Testing Influence of Scale-Free Property onStreet Network Robustness

      模型 策略 参数 容差α p
      连续删除 介数 fS 0.019 7**
      f<s> 0.006 9**
      fS 0.040 7**
      f<s> 0.094 3*
      级联 介数 Sα 0.1 0.246
      0.2 0.892
      0.3 0.867
      0.4 0.874
      0.5 0.667
      0.1 0.854
      0.2 0.999
      Sα 0.3 0.155
      0.4 0.340
      0.5 0.302
      注:—表示模型没有该参数,*表示显著性水平0.1,**表示显著性水平0.05
    • 本文延用复杂网络鲁棒性分析方法,在相对异质的数据样本上(50个世界范围内的城市),对以stroke相交关系表示的城市道路网进行了连续删除模型和级联模型下的鲁棒性分析。研究发现,运用连续删除模型和级联模型所得到的路网鲁棒性结果存在差异,表明路网的鲁棒性分析具有模型敏感性。对于同一模型下的度策略和介数策略,介数策略的破坏性均大于度策略,表明相对于度高的节点,介数高的节点在路网中承担更为核心的作用;对于路网鲁棒性与其拓扑模式的关系,在连续删除模型下,路网鲁棒性与度相关性呈现显著正相关,无标度与非无标度的路网鲁棒性有差异;而在级联模型下则无此规律,路网鲁棒性与度相关性不相关,无标度与非无标度的路网鲁棒性差异不显著。

      下一步将进行更为全面的分析与比较,并将道路网的鲁棒性分析结果应用在预防恐怖袭击、自然灾害以及交通拥堵等方面。

参考文献 (29)

目录

    /

    返回文章
    返回