公路交通网络的区块划分

朱 霞，宋伟东

（辽宁工程技术大学 测绘与地理科学学院，辽宁 阜新 123000）

0 引言

公路交通网络是服务经济、服务社会、服务公众的重要基础设施，是综合交通运输体系的骨干，如何评价交通网络规划的合理性、公路网络结构设计的合理性、交通网络维护和养护情况等是亟待解决的理论问题和现实问题.目前国内外有很多对网络结构分析的研究内容.

近年来，许多研究利用各种模型的分析理论对交通网络进行了探索.网络研究人员引入了大量的中心度指标，这些指标根据一定的标准赋予网络中顶点的重要性[1].这些指标已被证明在分析和理解社交网络[2-3]、引文网络[4]、计算机网络[5-6]、城市网络[7-9]等网络所扮演的角色方面具有重要价值.SUN D[10]等基于复杂网络和图论，对城市轨道交通系统的网络和站点脆弱性进行了分析.AGRYZKOV 等[11]人提出一种适应PageRank 算法（APA）来建立城市网络节点排名，从城市网络的主要特征获得的数据计算每个节点的重要性. CHOPRA S S[12]等人提出一个全面的多管架构，分析网络拓扑结构、空间组织和客流信息，以了解伦敦地铁系统的弹性. WAGNER M 等[13]提出了一种使用功能主成分分析来创建高质量的在线流量预测方法. YANG Y[14-16]等将社区检测的概念引入到城市交通状态关联网络中，提出了一种识别交通状态空间关联模式的新视角. ZHOU Y[17]等通过统一的指标和模型定量分析大型复杂地铁网络的脆弱性和恢复性，提出了一个评估大型复杂地铁网络弹性的总体框架. TANG F[18]等从两个角度定义链接的临界性，提出一种新的城市交通网络关键节点识别方法.

因此，从一个新的角度来解释大规模网络中交通状态空间分布的复杂性.提出一种同时考虑结构相似性和属性相似性的区块划分准则.利用原始节点映射方法应用于公路交通网络分析中，构建公路交通网络的数学模型.调整PageRank 算法，添加公路交通网络地理空间结构影响因子计算公路交通网络关键性节点排序结果，定义为公路交通网络关键性节点分析方法（简称FWLPA）.利用关键性节点分析方法的排序结果值和最短路径距离值绘制决策图，来选择区块划分的初始聚类中心点的位置和个数.最后以沈阳市公路交通网络为实验数据，通过公路交通网络区块划分方法识别出网络结构相似度和属性相似度模块，并分析出区块划分的适宜性评价.

1 公路交通网络构建

公路交通网络（RTN）是由道路节点与节点和节点之间的连边构成的，可以通过一组数学实体来定义，其中N为道路节点，E为道路节点与节点之间的连边

2 公路交通网络区块划分

地理空间角度交通网络区块结构划分概念（Regional Patch Detection）：在不同层次划分公路交通网络的范围内，区块是一个公路交通网络的子集，包含一定的节点和节点与节点之间的路段，区块内的节点与节点之间关系紧密，具有较强的拓扑结构相似性和地物设施属性相似性；而区块与区块之间的关系比较稀疏，区块与区块之间的相似性可以类似但距离较远，区块与区块之间的差异较大但距离较近的分布特征.

公路交通网络由国道、省道、县道、乡道和村道五个等级路网构成，深入分析公路交通网络的特性模块聚集情况，分析相同属性路网的分布情况.通过初始聚类中心的选取，然后基于K-Means 聚类方法识别出公路交通网络的特性区域.

2.1 聚类中心选取

为聚类算法的设计提供一种新的思路.聚类算法的核心思想在于对聚类中心（Cluster Centers）的刻画上，认为聚类中心同时具有以下属性：

（1）聚类中心是被低影响邻居包围的重要节点；

（2）初始聚类中心均匀的分布在物理网络中，并且中心点之间的“距离”相对更大.

对于每个节点i，计算两个值：FWLPA 计算值iρ和从较高中心度节点出发的最短路径长度iδ.FWLPA 的计算值iρ是向量*1x的第i个分量，它评估节点i的重要性.利用以上结果绘制一个二维决策图，其中横轴表示节点的FWLPA 值，纵轴表示最短路径长度.所以，可以在决策图中选择分布在图右上方的K个节点选作为初始聚类中心.然后利用聚类算法K-Means 将交通网络中的节点划分为不同的区块群体.由此将ρ值和δ值综合考虑的量来确定聚类中心的个数为

2.2 区块划分方法

在获得K个初始聚类中心后，应用K-means 算法将关联较强的节点(或路段)分配到同一个模块中.区块划分方法需要两个步骤进行迭代.

步骤1节点分配

假设C是一组质心，每个质心定义一个簇.最初K个初始簇中心构成了中心的初始集合，每个节点都被分配到最近的质心为

如果一个节点与两个簇心之间的距离相等，则将该节点分配给簇索引数较小的簇.

步骤2质心迭代更新

设分配给第k个集群的节点集为Zk.每个簇的质心通过分配给该质心簇的所有节点的均值来更新

该算法在第一步和第二步之间迭代，直到满足条件停止，即没有节点改变集群，距离之和最小化，或者达到最大迭代次数.

3 区块划分的适宜性分析

基于公路交通网络关键性分析（FWLPA）结果和最短路径长度两个指标对公路交通网络进行区块划分.通过标准欧氏距离计算节点相似性，然后利用K-Means 算法对网络模块进行检测.运用模块评价指数（Q-modularity）方法[19-20]来评价公路交通网络的适宜性.Q-modularity 的值一般在[-0.5，1]内.对于特定的模块结构，每个模块的边数存在差异.实际的边连接越高，节点越倾向于集中在某些模块上，即网络的模块化结构越明显.具体计算公式为

式中，A是由网络G计算得到的邻接矩阵，如果有一条从i到j的边，则Aij= 1，否则Aij= 0；m为连接边的总数；2m为节点度的总数；Aij/2m为两个节点之间连接的实际概率；k i和kj分别是节点i和j的度；如果保持网络的度分布，但随机连接边，之后任意一对节点连接的概率为式（6）～式（7）中表示实际节点连接概率高于期望值的程度，是一个具有两个变量的函数，如果节点属于同一个模块，则值为1，否则为0，只考虑模块内的连接.应用该模型对公路交通网络区块划分的适用性进行评价，如果实际公路交通网络的道路连接边数大于随机网络中的边数，其值为正，并且值越大说明区块划分的效果越快，越适宜.

4 实验

沈阳市全面积为12 856 km2，包括国道（G）、省道（S）、县道（X）和乡道（X）4 个等级的公路交通网络，有7 条国道，实际里程为746 km；有15 条省道，实际里程为1 055 km；有80 条县道，实际里程为1 337 km，有440 条乡道，实际里程为3 303 km，详细数据见表1.图1 为沈阳市公路交通网络图.

表1 沈阳市公路交通网络数据Tab.1 Shenyang road traffic network data

采用聚类算法识别公路交通网络模块必须考虑道路节点的属性，具有共同边缘和共同属性的道路节点构成的模块结构，见图2，沈阳市公路交通网络道路节点的分布情况，运用二维决策图理论，分析沈阳市公路交通网络模块个数和模块初始中心节点位置，其中表示节点i的综合值.

图1 沈阳市公路交通网络Fig.1 Shenyang road traffic network

参考γ值越大，越有可能是模块初始中心点.因此，只需对进行降序排列，然后从前往后截取若干个数据点作为初始模块中心点.图2 中，图2（a）为出沈阳市公路交通网络道路节点的分布情况，图2（b）为出沈阳市公路交通网络二维决策值结果，图2（c）为橙色方块圈出的点就是沈阳市公路交通网络区块划分的个数以及模块初始中心点的位置，图2（d）为圈出的结果点的个数.

图2 沈阳市公路交通网络区块划分初始中心点决策Fig.2 Shenyang road traffic network regional patch detection initial center points decision graph

由上述决策图结果可知，先计算出所需区块结构的数量，沈阳市公路交通网络的区块结构数量为十块.见图3，淡黄橘色区域为标签1 区块结构；黄色区域为标签2 区块结构等10 个标签区块.

图3 沈阳市公路交通网络区块划分分布Fig.3 Shenyang road traffic network regional patch detection

如图3，蓝色边框绘制出了沈阳市公路交通网络的区块结构，将整个沈阳市分为10 个区块结构，跨越了原有的行政区划界限的限制，从公路交通网络结构的特征深层次的分析出全新的公路交通网络结构状态.从图中可以明确的看出10 个模块的中心点位，从地理空间结构的角度去理解，提高这10个模块结构的连通性能以及便利程度就能很大程度地提高沈阳市的公路交通状况.评价沈阳市的模块指数值为0.062 6，区块划分结果值较小，适宜性一般.在实际中，当这类网络的值一般在0.3 到0.7之间时，聚类效果非常好.较高的值是罕见的.将网络中的每条边作为对矩阵A各元素贡献的独立度量，可以计算出Q的期望误差.网络模块划分结果一般，说明沈阳市公路交通网络的分布特征较弱.

5 结论

结合公路交通网络的建设和结构分析方法，从区块划分的新视角分析了公路交通网络的地理空间结构功能，并对模块进行了自适应分析.

（1）在RTN 中，公路交通网络系统的模块划分结果取决于地物设施的属性、路段之间的距离以及路网的平面分布.

（2）一个节点的关键度量不仅取决于它与其他节点的连接，还取决于它的地理空间特性.运用交通网络区块划分算法识别聚类性强的路段集.

（3）将该模型和分析方法应用于沈阳市公路交通网络中.结果表明：该方法在检测模块和模块结构分析方面表现良好，在识别公路交通网络的地理空间依赖模式方面具有很大的潜力，为交通运营和管理分析提供理论依据；根据模块的分布趋势对公路交通网络系统进行研究，为今后交通网络的维护和改造提供了理论依据.