﻿ ﻿ 对偶图节点重要度的道路网自动选取方法
 文章快速检索 高级检索

Auto-selection Method of Road Networks Based on Evaluation of Node Importance for Dual Graph
LIU Gang,LI Yongshu,YANG JunZHANG Xiping
Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 610031, China
First author: LIU Gang (1986—), male, PhD candidate, majors in complex network theory, GIS theory and application.

E-mail：liuganggis@sina.com

Abstract: The dual graph is constructed based on the generalized topological road network by using dual topology method. By introducing the concept of m-order neighbors and taking into account the factors of the node’s degree, betweenness centrality and distance within the dual graph, the importance contributions of the node-self and first to m-order neighbors and defining the evaluation model for node importance is considered. Based on this, a road selection process based on the evaluation of node importance for dual graph is proposed. In order to verify the efficiency of this process, the degree distribution is introduced to evaluate the level of maintaining the global structure and topological characteristics of road network, and real urban road network is used for experiments. The results show that this road selection process can maintain the global structure and topological characteristics of the original road network, keep the selected road network well connected, and also this method is stable and reliable.

Key words: map generalization     road selection     importance contribution     betweenness centrality     degree of node

1 引 言

2 网络拓扑图的建立及拓扑结构特征指标

2.1 道路网络的对偶拓扑表达

 图 1 交通网络拓扑结构 Fig. 1 Transportation network topology structure

2.2 网络拓扑结构特征指标

2.2.1 节点度

2.2.2节点介中心

2.2.3 节点距离

3 对偶图节点重要度评价方法

3.1 m阶邻居节点

 图 2 邻居节点示意图 Fig. 2 Sketch map of neighbors

3.2 节点重要度评估策略

3.3 道路网对偶图节点重要度评价

4 基于节点重要度评价的道路网自动选取方法

4.1 道路网自动选取方法

Ns=NS(9)

(1) 构建路网的对偶图G=V，L，建立其节点与原始广义路网拓扑中道路间映射关系。

(2) 获取对偶图中任意节点i的1到m阶邻居节点集：π(1)(i)、π(2)(i)、…、π(m)(i)。

(3)计算节点i的1到m阶邻居节点集的度值k(0)i、k(1)i、k(2)i、…、k(m)i和介中心值b(0)i、b(1)i、b(2)i、…、b(m)i，然后作归一化处理得到k′(0)i、k′(1)i、k′(2)i、…、k′(m)i和b′(0)i、b′(1)i、b′(2)i、…、b′(m)i

(4) 根据公式(8)，计算每个节点的重要度Ii

(5) 针对所有节点，按重要度从大到小进行排序，得到一组新的节点序列v1、v2、v3、…、vN

(6) 根据预定选取比例S，从上述节点序列中提取最前面紧邻的NS个节点及这些节点之间的所有连边，构建选取比例S下的对偶图Gs=Vs,Ls

(7) 对Gs=Vs,Ls进行连通性检查，按4.3中的连通性保持算法确保Gs全域的连通性。

(8) 基于对偶图Gs=Vs,Ls，根据节点与道路间的映射关系从原始广义路网拓扑中提取Gs网络中所有节点相应的道路，进而构建选取比例S下的道路网络。

4.2 连通性保持算法

(1)提取对偶图Gs=Vs,Ls中的所有孤立节点，形成孤立节点集V′s。

(2)针对任意节点i(i∈V′s)，计算距离i最近的某节点j(j∈Vs且jV′s)，获取i与j之间的最短路径，将路径上所有节点v(vVs)添加到Gs，更新Vs、Ls，并从V′s中移除i。

(3)重复步骤(2)，直到对偶图Gs=Vs,Ls中无孤立节点。

5 试验与讨论

 图 3 成都市城区广义路网结构 Fig. 3 Generalized road network of Chengdu city

①在各选取比例下，即便选取比例非常小，所选路网保持拓扑连通，较好地覆盖了原始路网的整体范围；
②在各选取比例下，所选路网保持了原始路网的整体结构；
③在各选取比例下，路网密度特征得以保持，原始路网中相对密集(或稀疏)的区域在所选路网中仍得以体现；
④随着选取比例的增大，所增选的道路较为合理，有效地顾及了原始路网的密度和整体结构，道路层次性得以体现。由此可知，本文道路选取方法较好地顾及了道路的拓扑和位置信息，能较好地满足道路网自动综合的基本要求。

 图 4 不同选取比例下道路选取结果 Fig. 4 Roads selection results at various selection ratios

 图 5 道路重要度指标I与m的关系 Fig. 5 The relation of I and m

 图 6原始道路网络的度分布 Fig. 6 The degree distribution of original road network

6 结 论

 [1] MACKANESS W A. Analysis of Urban Road Networks to Support Cartographic Generalization[J]. Cartography and Geographic 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] HU Yungang, CHEN Jun, LI Zhilin, et al. Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 351-357. (胡云岗, 陈军, 李志林, 等. 基于网眼密度的道路选取方法[J]. 测绘学报, 2007, 36(3): 351-357.). [4] CHEN Bo, WU Fang, QIANG Haizhong. A Study on Road Networks’ Auto-selection Algorithms[J]. Journal of Image and Graphics, 2008, 13(2): 2388-2393. (陈波, 武芳, 钱海忠. 道路网自动选取方法研究[J]. 中国图象图形学报, 2008, 13(2): 2388-2393.). [5] CHAUDHRY O, MACKANESS M. Rural and Urban Road Network Generalization: Deriving 1: 250, 000 from OS Master Map[C]//Proceedings of International Cartographic Conference. Coruna:[s. n.], 2005. [6] TOUYA G. A Road Network Selection Process Based on Data Enrichment and Structure Detection[J] .Transactions in GIS,2010, 14( 5): 595 - 614. [7] THOMSON R C, RICHARDSON D E. The Good Continuation Principle of Perceptual Organization Applied to the Generalization of Road Networks[C]//Proceedings of 19th International Cartographic Conference. Ottawa: ICA, 1999: 1215-1223. [8] XU Zhu, LIU Caifeng, ZHANG Hong, et al. Road Selection Based on Evaluation of Stroke Network Functionality[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 769-776. (徐柱, 刘彩凤, 张红, 等. 基于路划网络功能评价的道路选取方法[J]. 测绘学报, 2012, 41(5): 769-776.). [9] WANNING P, MULLER J C. A Dynamic Decision Tree Structure Supporting Urban Road Network Automated[J]. The Cartographic Journal, 1996, 33(1): 5-10. [10] 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. [11] 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. [12] DENG Hongyan, WU Fang, WANG Huilian, et al. A Generalization of Road Networks Based on Topological Similarity[J]. Journal of Geomatics Science and Technology, 2008, 25(3): 183-187. (邓红艳, 武芳, 王辉连, 等. 基于拓扑相似性的道路网综合模型[J]. 测绘科学技术学报, 2008, 25(3): 183-187.). [13] 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. (邓亚娟, 杨云峰, 马荣国. 基于复杂网络理论的公路网结构特征[J]. 中国公路学报, 2010, 23(1): 98-104.). [14] BARTHLEMY M. Spatial Networks[J]. Physics Reports, 2011(499): 1-101. [15] LI Qingquan, ZENG Zhe, YANG Bisheng, et al. Betweenness Centrality Analysis for Urban Road Networks[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 37-41. (李清泉, 曾喆, 杨必胜, 等. 城市道路网络的中介中心性分析[J], 武汉大学学报:信息科学版, 2010, 35(1): 37-41.). [16] WEST D B. Introduction to Graph Theory[M]. Upper Saddle River:Prentice Hall, 2001. [17] WASHIO T, MOTODA H. State of the Art of Graph-based Data Mining[J]. SIGKDD Explore News, 2003, 5(1):59-68. [18] HE Nan, LI Deyi, GAN Wenyan, et al. Mining Vital Nodes in Complex Networks[J]. Computer Science, 2007, 34(12): 1-5. (赫南, 李德毅, 淦文燕, 等. 复杂网络中重要性节点发掘综述[J]. 计算机科学, 2007, 34(12): 1-5.) .. [19] CRUCITTI P, LATORA V, PORTA S. Centrality in Networks of Urban Streets[J]. Chaos, 2006, 16(1): 15113-15122. [20] LIU Gang, LI Yongshu. Routing Strategy for Complex Networks Based on Gravitation Field Theory[J]. Acta Physica Sinica, 2012, 61(24): 248901. (刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究[J]. .物理学报, 2012, 61(24): 248901.) . [21] WANG Lin, DAI Guanzhong. On Degree Distribution of Complex Network[J]. Journal of Northwestern Polytechnical University, 2006, 24(4): 405-409. (王林, 戴冠中. 复杂网络的度分布研究[J]. . 西北工业大学学报, 2006, 24(4): 405-409.) .
http://dx.doi.org/10.13485/j.cnki.11-2089.2014.
0014

0

#### 文章信息

LIU Gang, LI Yongshu, YANG Jun,et al.

Auto-selection Method of Road Networks Based on Evaluation of Node Importance for Dual Graph

Acta Geodaeticaet Cartographica Sinica,2014,43(1):97-104.
http://dx.doi.org/10.13485/j.cnki.11-2089.2014.0014