基于Hosoya指标的城市道路拓扑结构重要度评估

Evaluation of the Importance of Urban Road Topological Structure Based on Hosoya Index

摘要: 为了评价城市路网中每条道路的重要性，借助于拓扑网络结构，提出了一种评价方法。该方法借助对偶拓扑网络动态变化下的节点度量指标，通过Hosoya指标度量删除的节点对拓扑网络连通性的破坏程度，来评价道路重要性，并根据Hosoya指标对节点度量指标下的重要道路集合进行集合运算得到道路重要等级。以武汉市二环与三环间4个局部路网样本为例，发现集合运算后的Hosoya指标低于单一节点度量指标下的Hosoya指标，验证了该方法的有效性，并表明多指标集成相对于单一指标能更好地表达出道路重要性。

Abstract: To evaluate the importance of each road in the urban road network, an evaluation method was proposed using a topological network structure. This method utilizes node metrics under dynamic changes in dual topology networks to evaluate the importance of roads by measuring the degree of damage to topology network connectivity caused by node deletion using the Hosoya index. Based on the Hosoya index, the important road sets under the node metric are aggregated to obtain the road importance level. Taking four local road network samples between the second and third ring roads in Wuhan as examples, it was found that the Hosoya index after set operation is lower than the Hosoya index under a single node measurement index, verifying the effectiveness of this method and indicating that multi indicator integration can better represent the importance level of roads compared to a single indicator.

1. 引言

道路网络是城市的基本骨架，是构成城市的核心要素，对路网中道路的重要性评价不仅是研究复杂路网结构与功能的基础性工作，也是城市交通规划与控制的基础 [1] 。一方面，通过评价道路重要性，对城市道路重要性进行分级，可以将不同重要等级的道路进行分级布局与管理，优化交通网络结构，提高交通容量。另一方面，城市道路网络规模庞大，加上资源和资金的限制，在交通控制的过程中对每个道路进行完全管理是不可行的，确定路网中的关键道路，对其着重管理，可以缓解交通拥堵，确保运输效率。

目前，对于路网中道路重要性的研究有以下方面：王立夫等 [2] 基于路段信息与车流量信息提出拥堵系数，将其作为道路网络路段–节点模型的边权重，运用提出的辨识方法对路网的关键路段进行辨别。Włodarczyk K等 [3] 基于合作博弈方法和可靠性理论，建立了分析道路重要性的模型，以评估道路对街道系统功能的重要性。孙秋霞等 [4] 利用交通实测数据对路段失效前后路网MFD的差异变化，提出了一种测量方法，以识别路网中的关键路段。以上关于道路重要性的研究大多从道路交通状况的角度对重要道路进行了识别，而城市道路的重要性不仅取决于其自身的属性，还取决于其在路网结构中的位置，以及与其他道路的连接关系 [5] 。随着复杂网络的不断发展，复杂网络理论在道路节点重要性方面的研究也不断深入。张喜平等 [1] 提出了基于度和介数两大因素的m阶邻居节点的路段重要性评估模型。赵妍等 [6] 利用度 + k-shell值的识别方法对路网路段重要性进行排序，但是该方法无法量化其重要性，更无法知晓其重要性量化的差距。蒋一森 [7] 从度中心性、中介中心性和结构中心性三个角度对网络中的重要节点进行了识别。胡钢等 [8] 选取五个属性指标构建复杂网络多属性决策矩阵，采用熵理论对节点属性赋权的方法对节点重要性进行排序。

基于已有的研究，考虑到一条道路的重要性也取决于该条道路失效或删除后对路网连通性的影响，本文提出了一种评价道路重要性的方法。路段是道路最基本的表达单元，从心理学上讲，人们习惯于将视觉上平滑连续的路段视为同一条道路 [5] 。因此，采用对偶法对路网做拓扑处理，把道路作为研究对象，针对道路在路网中的局部特征、全局特征、结构位置特征，选取节点度、介数、紧密中心度3个节点度量指标，得到路网中重要程度较高的道路集合，并结合能够表达每条道路连通情况的Hosoya指标，对道路集合进行集合运算得到道路重要等级，并对武汉市二环与三环间4个行政区划的4个局部路网样本进行实例分析。

2. 理论基础

拓扑性质是图形均具有的抽象结构特征，它描述了拓扑网络所具有的内在结构关系。对于城市道路网络结构分析而言，拓扑分析遵循了图论理论，将复杂的要素抽象为由节点、连边构成的点线图，并进而探讨其结构关系。基于复杂网络理论的城市路网抽象法主要有原始法和对偶法 [9] ，原始法是把交叉口转换为节点，道路转换为连边，在转换过程中不丢失地理信息；而对偶法是将路网中的道路转换为节点，交叉口转换为连边，在转换过程中丢失了路网的基本地理信息，但可以降低构建拓扑网络难度、减少工作量。其具体转换方式如图1所示。

(a) 地图 (b) 原始法 (c) 对偶法

Figure 1. Comparison between primitive method and dual method

图1. 原始法和对偶法的对比

定义图 $G=\left(N,V\right)$ ，其中N为G中节点的集合， $N=\left\{1,2,\cdots ,n\right\}$ ，n为G中节点的总数； $V=\left\{v_{ij}\right\}$ ，v_ij为节点i与节点j的连边。运用对偶法将城市路网转换为拓扑网络，选择节点度、介数、紧密中心度三个节点度量指标来表达道路的重要性。

1) 节点度。节点度k_i是指节点i与其他节点连接的节点数，能够表明该节点与邻近节点连接的程度，连接数越多说明该节点在路网局部区域越重要。

2) 节点介数。节点的度虽然在一定程度上能够说明节点的重要性，但是当两节点的度相同时，两节点的重要性很大可能会有不同。网络中节点之间的传输主要依赖于最短路径，如果某个节点被很多个最短路径经过，说明该节点在网络中很重要，其中最短路径是指节点间经由的弧最少的路径。为了量化该节点的重要性，提出了节点的介数，定义最早是由Freeman在1977年提出的。一个节点的介数最大可能

取值为星形网络中心节点的介数值， $\frac{\left(n-1\right)\left(n-2\right)}{2}$ 即，于是节点i归一化 [10] 后的介数计算公式为：

$B_i=\frac{2}{\left(n-1\right)\left(n-2\right)}{\displaystyle {\sum }_{i\ne l\ne j\in N}\frac{n_{jl}\left(i\right)}{n_{jl}}}$ (1)

其中，B_i为节点i的介数；n为拓扑网络的节点数； $n_{jl}\left(i\right)$ 表示节点j与节点l之间经过节点i的最短路径的数目；n_jl表示节点j与节点l之间所有最短路径的数目。节点介数反映了节点在整个网络的作用和影响力，是一个重要的全局特征量 [11] 。

3) 节点紧密中心度。节点的重要性也可由节点所处整体网络结构中心位置的程度来决定 [12] 。节点紧密中心度表示节点在拓扑网络结构上的中心性，可以得出拓扑网络结构最中心的点，但是该中心点的度不一定大。中心度越大，说明对应的道路与其他道路联系越紧密。它的值是其他节点到该节点最短路径长度之和的倒数，最短路径长度是指节点间最短路径的弧数。

紧密中心度需要通过最小紧密中心度来衡量不同规模的网络。极端情况下，图的某个节点可以仅通

过最短路径长度为1的路径到达其余所有节点，此时紧密中心度为 $\frac{1}{n-1}$ ，因此节点i归一化后的紧密中心度计算公式为：

$C_i=\frac{n-1}{{{\displaystyle \sum }}_{j=1}^n{d}_{ij}}$ (2)

其中，C_i为节点i的紧密中心度；d_ij为节点i到节点j的最短路径长度。

3. 研究方法

本文借助图的Hosoya拓扑指标表征道路的连通情况对于路网稳定性的贡献，以此来表达道路的重要性。

3.1. Hosoya指标

1971年，Hosoya提出了Hosoya指标 [13] ，在化学上用以描述分子结构，实现分子结构信息的数值化，定义图G的Hosoya指标为图中所有匹配数目的总和。

在图G中，如果两点在一条边的两端，则称这两点是相邻的；如果两边共用同一个节点，则称这两边是相邻的。反之，则是不相邻的。如果两边或者更多的边不共用同一节点，则这些边是相互独立的，并称这些边为边独立集。定义 $N\left(G,K\right)$ 为G中包含K条边的边独立集的数目，规定 $N\left(G,0\right)$ 为1， $N\left(G,1\right)$ 为图中边的数目。图G的Hosoya指标为所有K条边的边独立集的总和，计算式为：

$H\left(G\right)={\displaystyle {\sum }_{K=0}^{m}N\left(G,K\right)}$ (3)

其中， $m=\{\begin{array}{ll}\frac{n-1}{2},\hfill & n为奇数\hfill \\ \frac{n}{2},\hfill & n为偶数\hfill \end{array}$ (n为拓扑网络的节点数)。具体计算方法示例见图2，n = 6，m = 3， $H\left(G\right)=25$ 。

(a) 例图 (b) 例图中边独立集的数目

Figure 2. Calculation of Hosoya indexexample figure

图2. Hosoya指标例图计算

对于较复杂的网络，构造邻接矩阵 $A=\left(a_{ij}\right)$ ，编制MATLAB通用语言程序，通过邻接矩阵计算拓扑网络的Hosoya指标。邻接矩阵是表示图中节点之间的关系，表示方法如下：

$a_{ij}=\{\begin{array}{ll}a,\hfill & 节点i与节点j连边的个数\hfill \\ 0,\hfill & 节点i与节点j无连边\hfill \end{array}$

其中，a是两条道路相交形成的交叉口个数(环形路网会有多个交叉口)决定的。

3.2. 评价方法

从文献 [14] 可知，Hosoya指标越大，网络越分散，在道路网络中，越能提供更多与周围区域连通的可能性，越多的非邻接道路不会彼此受到影响。即使某一路段发生交通事故或其他紧急事件，路网中其他道路也不会因此影响通行，从而道路网络稳定性越高。

因此，借助Hosoya指标来表达道路的连通性对路网稳定性的贡献，具体步骤如下：

1) 对原始拓扑网络中的节点按照节点度由大到小依次排序，删除最大值的节点并计算删除后网络的Hosoya指标，删除节点时把与之相连的连边删除，更新网络并重新计算节点度，按照相同的步骤删除节点、记录Hosoya指标，直至删除网络中所有的节点。介数，紧密中心度如上。

2) 筛选Hosoya指标变化明显的节点，并对此类节点按照节点度、介数、紧密中心度分别记为集合K、B、C。路网规模不同，节点集合中的元素数也不同。

3) 对集合K、B、C进行不同的组合，得到集合D1、D2、D3、D4，由此得到节点重要等级，即路网的道路重要等级。组合方式如下：① $\text{D}1=\text{K}\cap \text{B}\cap \text{C}$ ；② $\text{D}2=\left(\text{K}\cap \text{B}\right)\cup \left(\text{K}\cap \text{C}\right)\cup \left(\text{B}\cap \text{C}\right)-\text{D}1$ ；③ $\text{D}3=\text{K}\cup \text{B}\cup \text{C}-\text{D}1-\text{D}2$ ；④ $\text{D}4=\text{N}-\text{D}1-\text{D}2-\text{D}3$ 。其中，D1、D2、D3分别为第一、二、三重要等级的节点集合，D4为非重要等级的节点集合，N为原始拓扑网络的节点集合。

4) 由3)得出节点重要性排序，逐级逐个删除节点，每次删除后计算拓扑网络Hosoya指标，直至删除所有节点。

5) 通过Hosoya指标对比1)与4)结果并对其进行分析，以此验证该方法的有效性。

4. 实验分析

4.1. 数据来源及预处理

城市道路网络是由一个个局部小网络组成的，研究局部小网络对城市整体路网有重要意义。我国相关的标准和规范将城市道路分为快速路、主干路、次干路和支路四级，但并未明确指出道路的分级依据，也未能建立一套定量的道路分级程序，甚至不同的标准规范对四级道路的定义都不同 [5] 。对于城市局部路网的选取借助于道路等级，快速路是连接城市的主要道路、主干路是连接城市各区的道路，在交通系统中都有着举足轻重的作用。该实验以快速路和主干路在外、次干路和支路在内形成的路网作为研究对象，以武汉市二环与三环间4个行政区划的4个局部路网样本(样本1：汉阳区的江城大道、四新南路、四新北路、芳草路围合路网；样本2：洪山区的雄楚大道、关山大道、南湖大道、民族大道围合路网；样本3：硚口区的长丰大道、古田二路、南泥湾大道、古田一路围合路网；样本4：青山区的友谊大道、工业路、冶金大道、建设十路围合路网)为例，进行实验分析。

从Open Street Map下载4个样本路网的地理矢量数据，导入Arc GIS进行预处理生成道路连边和交叉口，得到道路网(图3)，并标注道路ID于图3。

4.2. 实验结果与分析

本实验将路网样本抽象为复杂网络，由于路网样本中同一道路名称的路段平滑连续，所以将同一道路名称的路段视为同一道路。采用对偶法构建城市局部道路拓扑网络模型，把道路抽象为节点、交叉口抽象为连边。根据公式(1)、(2)并借助Networkx计算拓扑网络的节点度、介数和紧密中心度。路网样本在节点度、介数和紧密中心度动态变化下删除的节点顺序见表1。

(a) 样本1

(b) 样本2

(c) 样本3(d) 样本4

Figure 3. Map of 4 sample road networks in Wuhan city

图3. 武汉市4个样本路网图

Table 1. The order of node deletion for four samples in Wuhan under node metrics

表1. 武汉市4个样本在节点度量指标下节点删除顺序

根据表1的节点顺序，按照节点度、介数、紧密中心度依次删除节点，每次删除后计算剩余路网的Hosoya指标，直至删除所有的节点，各个样本拓扑网络Hosoya指标变化如图4 (点线1、2、3)所示。

对于此类规模的路网，根据Hosoya指标结果可知，路网中大约删除前30%的节点时，Hosoya指标发生了明显的变化，由此分别选择样本1、2、3、4在节点度量指标下的前7、4、4、5个道路作为集合K、B、C的元素。经过集合运算后得到道路重要等级(表2)，对于相同等级的节点则按节点度量指标下删除的序号和排序。样本4为规则的方格式路网，其结构的特殊性导致多个道路在路网中的重要性相同，表2括号内的道路表示与括号前的道路重要性相同。

Table 2. Road importance levels of four road network samples in Wuhan city

表2. 武汉市4个路网样本的道路重要等级

根据表2的节点重要性排序，依次删除节点，得到拓扑网络的Hosoya指标变化结果(图4点线4)，与按照单一指标删除节点得到的Hosoya指标变化作对比，结果如图4所示。

(a) 样本1 (b) 样本2 (c) 样本3 (d) 样本4

Figure 4. Consider the changes in Hosoya index when considering single and multiple indicators

图4. 考虑单一指标与多指标时Hosoya指标变化情况

由图4 (点线1、2、3)可知：① 在删除节点的初期，按照节点度删除的样本拓扑网络Hosoya指标变化最快，原因是节点度越大，该节点与其他节点的连边就越多，删除节点时就删除了更多的连边，从而Hosoya指标的结果就越小，说明该指标对路网连通性的影响较大。但是随着删除的节点数越多，节点度的大小对Hosoya指标的影响就越小。② 考虑节点在整个网络中的作用和影响力时，相比其他两个节点度量指标，在介数下删除的样本拓扑网络Hosoya指标前期的变化相对较小。③ 样本1和样本3在紧密中心度下的Hosoya指标变化与节点度下的Hosoya指标变化基本一致，但是节点的重要性排序不一致，这就说明了节点在网络结构的中心性和对周围节点影响的不同。④ 样本4在介数和紧密中心度下拓扑网络的Hosoya指标变化相同，可能的原因是路网结构为方格式，具体的原因可做进一步研究。最后随着删除的节点越来越多，继而每次删除的连边越来越少，Hosoya指标的变化越来越小，直至为0。

考虑了节点的度值、介数、紧密中心度，也就综合考虑了节点的局部特征、全局特征和结构位置特征。根据图4的对比结果可知：按照节点重要等级删除的拓扑网络Hosoya指标变化折线位于其他删除方法折线的下方，说明了该评价方法更能准确地确定道路的重要性。由该评价方法得到的道路重要等级可知：第一重要等级的道路对道路网络的连通性起着决定性作用，缺少该部分道路，整个道路网络的连通性会直接消失，对其应优先控制与保护；第二、三重要等级的道路对整个道路网连通性的影响相对次之，但是也缺一不可，也需要对其重点保护；非重要等级的道路对路网连通性的影响相对较小，不能正常通行时，对其他道路之间的通行影响相对较小。

5. 结论

1) 提出了可以反映道路局部特征、全局特征、结构位置特征的度量指标，相比单一度量指标，可以从多角度来反映道路的重要性，避免道路重要性评价的片面性。

2) 通过实例分析展示了该方法的应用过程，结果显示，与其他两个节点度量指标对比，节点度对路网连通性影响较大，较大度值节点的删除会直接影响路网连通性；该方法综合考虑多因素得出的Hosoya指标更能表达出道路重要性。

3) Hosoya拓扑指标可以通过对路网连通性贡献的角度来反映道路的重要性，除了本文提出的蓄意连续删除的方法，还可以通过删除单一道路以此来对比Hosoya指标来反映道路的重要性。