基于复杂网络的城市道路重要度评价及路网自动综合方法

宋海权，郭 进，刘 刚

(1.西南交通大学 信息科学与技术学院，四川 成都 610031；2.成都理工大学 地球科学学院，四川 成都 610031)



基于复杂网络的城市道路重要度评价及路网自动综合方法

宋海权1，郭 进1，刘 刚2

(1.西南交通大学 信息科学与技术学院，四川 成都 610031；2.成都理工大学 地球科学学院，四川 成都 610031)

利用复杂网络理论，构建城市复杂路网模型，基于该模型从道路的结构和功能特征角度，以连接度、介中心和接近度为度量指标定义道路重要度评价模型，并顾及路网的整体形态及路网的拓扑连通性，提出基于复杂网络理论的路网综合算法。为检验方法有效性，针对成都市道路网络进行实验分析。实验结果表明，该道路重要度评价模型较好地反映道路在整个路网结构和功能上的重要程度，复杂路网综合算法能较好地保持原始路网的整体形态结构特征。

路网综合；道路重要度；复杂网络；拓扑连通

路网综合是自动制图综合研究的重点和难点内容之一，其目的是从大比例尺地图上提取部分关键道路生成小比例尺路网结构，并保持所选路网的拓扑连通[1-3]。从网络科学的角度，路网综合又属于网络压缩研究的范畴。对于规模庞大、结构复杂的城市路网而言，路网综合的难点在于如何保持原始路网的整体形态结构特征及拓扑连通。

目前，学者们已经提出很多路网综合方法[4-8]。现有方法主要是利用传统图论从路网几何结构、层次特征等方面研究路网综合问题，然而较少顾及路网的整体形态结构和功能特征。近年来，复杂网络理论在复杂系统结构及功能分析方面的优势日趋突出[9-12]，利用复杂网络理论可以弥补传统图论在大规模网络结构分析中的不足[13]。研究认为，利用复杂网络理论可以更为合理、准确地分析道路之间的连接关系及交通动力学特性[8,13-15]。本文认为，每条道路对整个路网而言在结构和功能上都有不同程度的贡献，这种贡献可以通过相应的结构和功能评价指标进行度量。为此，本文将利用复杂网络理论，引入节点连接度、介中心和接近度等指标，考虑不同道路在结构和功能上对路网的贡献，建立道路在整个路网中的重要度评价模型，进而提出一种基于复杂网络理论的城市路网自动综合方法。

1 城市道路网络对偶拓扑模型

在城市道路网络建模方面，最常用的网络拓扑方法是直接将道路抽象为边(或弧段)、交叉口抽象为节点，进而建立具有地理空间意义的网络模型。这种建模方法虽然可以较好地描述城市路网的几何形态结构，然而难以准确反映道路之间的连接关系、结构复杂性及道路的功能特征。利用基于对偶拓扑方法的复杂网络理论可以很好地研究路网的结构和功能复杂性。该建模方法将道路按路名映射为节点、交叉口映射为边，进而建立城市道路网络的对偶拓扑模型[16]。如图1(a)为现实城市路网，且由9条道路构成；(b)为采用传统方法构建的网络拓扑结构，其中1-9为道路名或编码；(c)为基于传统路网结构建立的对偶拓扑模型。研究表明，利用复杂网络理论构建的城市复杂路网模型能够更加准确地表达道路之间的连接关系，有助于深入分析路网的结构和功能特征。图2为成都市道路网络结构，其中(a)为几何路网结构，(b)为采用对偶拓扑构建的复杂路网模型。

(a)现实城市路网

(b)传统方法构建网图1 城市道路网络拓扑模型

(c)对偶拓扑模型

(a)几何道路网络

(b)复杂路网模型

2 道路重要度评价方法

评价道路重要性对路网综合至关重要，而针对复杂路网模型，则关键在于如何准确评估节点的重要性。学者们在道路重要性评价方面提出很多方法，这些方法主要集中在两个方面：一方面，从道路等级的角度提取不同尺度下的道路；另一方面，将道路构建成路划，进而通过评价路划的重要性来提取关键道路。现有方法主要是利用图论和数学规划理论分析道路的重要性[17]，较少综合考虑道路结构和功能特性。复杂网络理论在网络结构及功能评价方面具有显著优势。研究认为，采用基于对偶拓扑的复杂网络理论及其所提供的结构化度量指标可以更为合理、准确地评估道路在整个路网中的交通特性及线路之间的连接关系。

2.1 评价指标

1)节点度。度(或连接度，Degree)是网络节点最为简单而又最为重要的概念，是节点重要性度量的重要指标之一。节点i的度定义为与该节点直接相连的其他节点的数量，一般用ki表示。研究普遍认为，节点的连接度越高，则该节点相对越重要。

2.2 道路重要度评价模型

Mi=w1ki′+w2bi′+w3ci′.

(2)

式中:Mi为节点i的重要度；w1,w2,w3分别为节点度、介中心和接近度所占的权重。式(2)表明，该评价模型同时顾及道路的结构和功能特征。在实验过程中，发现当w1,w2,w3的取值相当时(即w1=w2=w3)，评价结果较为合理、准确。如图3为利用本文方法提取的成都市路网的部分关键道路。结果显示，所提取的关键道路较为准确地反映了这些道路在整个城市路网中的重要性，这些道路在结构和交通功能上都起到非常关键的作用。

图3 关键道路提取结果

3 路网综合方法

3.1 复杂路网自动综合算法

路网综合的目的在于提取不同尺度下的重要道路构建新的路网结构。为此，本文提出基于道路重要度的城市复杂路网自动综合方法。根据道路重要度评价结果，按其重要度排序进而获得确定尺度下的道路。设原始道路网络规模为N，道路选取比例为r，则所选取路网规模为N·r。路网综合算法具体描述如下：

1)根据传统路网拓扑结构，采用基于对偶拓扑的复杂网络理论构建其复杂路网模型G={V,E}；

2)计算复杂路网模型中所有节点的连接度、介中心和接近度，基于式(3)，计算所有道路(即复杂路网模型中所有节点)的重要度；

3)将道路按重要度进行降序排序，并根据选取比例提取最为重要的N·r条道路，构建所选取的复杂路网模型Gr={Vr,Er}；

4)对所选路网进行拓扑连通性检查，并根据连通性保持算法确保网络Gr的全局连通；

5)根据所选复杂路网模型构建对应的几何网络拓扑结构，得到综合后的道路网络结构。

3.2 网络连通性保持算法

本文采用文献[6]所给出的连通性保持方法，即通过增加最小数目的节点来连通整个网络，具体算法过程如下：①获取所选网络Gr={Vr,Er}中的所有孤立节点，生成孤立节点集合Er′；②针对孤立节点i(i∈Er′)，计算距离i最近的节点j(j∈Er，j∉Er′)，获取i，j之间的最短路径，并将路径上所有节点v(v∉Er，v∈E)添加到所选网络Gr，并更新所有的节点信息和边信息；③重复步骤②，直到Gr中无孤立节点。

4 实验与讨论

为检验方法的有效性，本文以成都市市区道路网络为实验数据，针对道路在不同尺度下的重要性进行路网综合实验分析。如图4为选取比例为0.01、0.05、0.1和0.2等取值下的道路选择结果。由实验结果可知：在不同选取比例下，所选路网均较好地保持原始路网的整体形态结构，路网覆盖了原始路网的整体范围；在不同选取比例下，综合路网均能保持拓扑连通，而且较好地保持了原始路网的密度特性，随着选取比例的增大，增选道路较为合理；当选取比例较小时，所选道路为环路及主干道，随着选取比例的增加，道路的等级、层次结构得以体现。

(a)选取比例为0.01

(b)选取比例为0.05

(c)选取比例为0.1

(d)选取比例为0.2

为进一步说明本文方法的可行性，这里对所选路网与原始路网的拓扑相似性进行对比实验分析。利用文献[19-20]所给出的结构相似性度量方法，以连接度为结构度量指标，计算所选路网对原始路网的结构保持程度。为评估网络u和υ的相似性，设Vu为网络u的节点集，Vυ为网络υ的节点集。

图5 所选路网相似性分析

5 结论

路网自动综合是地图学、网络压缩等研究的重点问题。本文针对传统图论在网络结构及功能评价方面的不足，采用基于对偶拓扑的复杂网络理论构建路网的复杂网络模型，研究城市复杂路网的制图综合问题。引入连接度、介中心及接近度等结构化指标，顾及道路在整个路网中的结构及功能特征，定义道路重要度评价模型。在此基础上，考虑所选路网的拓扑连通性，通过道路重要度排序提出一种基于复杂网络的城市复杂路网自动综合算法。为检验本文方法的有效性，以成都市城区道路网络为实验数据，针对路网在不同选取比例下进行综合实验分析，结果表明：本文路网综合方法较好地顾及道路的结构和功能特征，所选路网与原始路网在结构上保持较高的相似度，较好地保持原始路网的整体形态特征及拓扑连通，路网的层次结构及密度特性也得以体现。

[1] MACKANESS W A.Analysis of urban road networks to support cartographic generalization [J].Cartography and Geographical Information Systems,1995,22(4): 306-316.

[2] JIANG B,CLARAMUNT C.A structural approach to the model generalization of an urban street network [J].GeoInformatica,2004,8(2): 157-171.

[3] ZHOU Q,LI Z.Evaluation of properties to determine the importance of individual roads for map generalization [J].Advances in Cartography and Giscience,2011,5(1): 459-475.

[4] 栾学晨,杨必胜,张云菲.城市道路复杂网络结构化等级分析[J].武汉大学学报(信息科学版),2012,37(6): 728-732.

[5] THOMSON R C,RICHARDSON D E.The good continuation principle of perceptual organization applied to the generalization of road networks [C]// Proceeding of 19th International Cartographic Conference,Ottawa: ICA,1999: 1215-1223.

[6] 徐柱,刘彩凤,张红,等.基于路划网络功能评价的道路选取方法[J].测绘学报,2012,41(5): 769-776.

[7] CHEN J,HU Y,LI Z L,et al.Selective omission of road features based on mesh density for automatic map generalization [J].International Journal of Geographical Information Science,2009,23(8): 1013-1032.

[8] LIU G,LI Y S,LI Z,et al.Cartographic generalization of urban street networks based on gravitational field theory [J].Int.J.Mod.Phys.B,2014,28(20):1450133-17.

[9] NEWMAN M E J.The structure and function of complex networks [J].SIAM Review,2003,45(2): 167-256.

[10] BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks: structure and dynamics [J].Physics Reports,2006,424(4): 175-308.

[11] 程飞,姬东鸿.基于重叠社团发现的微博话题检测方法[J].计算机工程与应用,2015,51(6): 93-98.

[12] 文宏,樊晓平,张会福,等.无标度网络上的动态局部路由策略设计[J].计算机工程与应用,2014,50(20): 10-14.

[13] 邓亚娟,杨云峰,马荣国,等.基于复杂网络理论的公路网结构特征[J].中国公路学报,2010,23(1): 98-104.

[14] 杨柳青,宗刚,柳应华.基于复杂网络的路网交通拥堵评估仿真模型[J].计算机应用研究,2014,31(3): 796-800.

[15] 李永树,刘刚,张帅毅.基于GIS的多粒度复杂网络模型[J].西南交通大学学报,2012,47(3): 406-412.

[16] LIU Gang,LI Yongshu,YANG Jun,et al.Gravitational-field routing strategy considering the distribution of traffic flow.International Journal of Geographical Information Science,2014,28(1): 39-55.

[17] 赫南,李德毅,淦文燕,等.复杂网络中重点性节点发掘综述[J].计算机科学,2007,34(12): 1-5.

[18] 李清泉,曾喆,杨必胜,等.城市道路网络的介中心性分析[J].武汉大学学报(信息科学版),2010,35(1): 37-41.

[19] LÜ L Y,MEDO M,YEUNG C H,et al.Recommender systems [J].Physics Reports,2012,519: 1-49.

[20] 乔柱.城市大比例尺地形图自动化综合的研究[J].测绘与空间地理信息，2015,38(7):172-173.

[责任编辑：张德福]

Auto generalization approach and importance evaluation of urban roads based on complex networks

SONG Haiquan1,GUO Jin1,LIU Gang2

(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,China；2.College of Earth Sciences,Chengdu University of Technology,Chengdu 610031,China)

Using the complex network theory,an urban complex road network model is constructed.On the basis of this model,from the point of the structural and functional properties of roads,the evaluation model of road importance is defined with the measures of node degree,betweenness centrality and closeness centrality.As the global morphology and topological connectivity of road networks are targetted,the generalization approach based on the complex networks theory is presented.In order to testify the efficiency of this method,experimental analysis is carried out with taking the Chengdu street networks as a case study.The results show that,the evaluation model of road importance reflects the significance of the road within the whole street network on structural and functional aspects,and the generalization approach of complex road networks retains the global morphological structural characteristic of the original road network.

generalization of road networks; road importance; complex network; topological connectivity

引用著录：宋海权，郭进，刘刚.基于复杂网络的城市道路重要度评价及路网自动综合方法[J].测绘工程，2017，26(1)：08-12.

10.19349/j.cnki.issn1006-7949.2017.01.002

2015-12-29

国家自然科学基金资助项目(41401434)

宋海权(1981-)，男，博士研究生.

U491

A

1006-7949(2017)01-0008-05