对偶图节点重要度的道路网自动选取方法

测绘学报 ›› 2014, Vol. 43 ›› Issue (1): 97-104.

对偶图节点重要度的道路网自动选取方法

刘刚¹,李永树¹,杨骏张喜平¹

收稿日期:2013-01-21 修回日期:2013-12-03 出版日期:2014-01-20 发布日期:2014-01-20
通讯作者: 刘刚 E-mail:liuganggis@sina.com
基金资助:
高等学校博士学科点专项科研基金;2013年西南交通大学博士研究生创新基金;2013年西南交通大学优秀博士学位论文培育项目;中央高校基本科研业务费专项资金;自然科学基金项目;中国博士后科学基金面上项目;中央高校基本科研业务费科技创新项目;重庆市教委科学技术研究项目(自然科学类)

Auto-selection Method of Road Networks Based on Evaluation of Node Importance for Complex Traffic Network

Received:2013-01-21 Revised:2013-12-03 Online:2014-01-20 Published:2014-01-20

摘要/Abstract

摘要：

采用对偶拓扑方法构建基于广义路网拓扑的复杂交通网络，通过引入m阶邻居节点概念，考虑复杂交通网络中节点度、介中心及节点间距离等因素，顾及节点自身及1到m阶邻居节点的重要度贡献，定义了节点重要度评价模型，进而提出一种基于m阶邻居节点重要度贡献的道路网自动选取方法，并基于网络最小规模原则保持选取道路的连通性。为检验方法的有效性，引入度分布评价所选取道路对路网整体结构及拓扑特性的保持程度，并采用实际城市路网进行试验，结果表明本文方法选取的路网能较好地保持了原始路网的整体结构、拓扑特性及道路连通性，且算法稳定、可靠。

关键词: 地图综合, 道路选取, 重要度贡献, 介中心, 度

Abstract:

The complex traffic network 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 on the complex traffic network, we consider the importance contributions of the node-self and first to m-order neighbors and define the evaluation model for node importance. Based on this, a road selection process based on the importance contribution of m-order neighbors is proposed, and the selection set is guaranteed to be connected through adopting the minimization principle to network size. 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 of selection. The results show that this road selection process can maintain the global structure of the original road network, maintain the topological characteristics and 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

中图分类号:

P208

刘刚李永树杨骏张喜平. 对偶图节点重要度的道路网自动选取方法[J]. 测绘学报, 2014, 43(1): 97-104.

参考文献

[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] JIANG B, HARRIE L. Selection of Street s from a Network Using Self-organizing Maps [J]. Transactions in GIS, 2004, 8(3): 335-350.
[4] HU Yungang, CHEN Jun, LI Zhilin, ZHAO Renliang. 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.)
[5] 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.)
[6] 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.
[7] ROBERT C, THOMSON, RUPERT B. Exploiting Perceptual Grouping for Map Analysis, Understanding and Generalization: The Case of Road and River Networks [J]. Lecture Notes in Computer Science, 2002(2390): 148-157.
[8] TOUYA G. A Road Network Selection Process Based on Data Enrichment and Structure Detection[ J ] .Transactions in GIS,2010, 14( 5): 595 - 614.
[9] 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.
[10] XU Z, LIU C F, ZHANG H, HUANG Z C, LI Z L. 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.)
[11] WANNING P, MULLER J C. A Dynamic Decision Tree Structure Supporting Urban Road Network Automated [J]. The Cartographic Journal, 1996, 33(1): 5-10.
[12] CHEN J, HU Y, LI Z L, ZHAO R L, MENG L Q. 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.
[13] 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.
[14] 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.)
[15] 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.)
[16] Marc Barthélemy. Spatial Networks [J]. Physics Reports, 2011(499): 1-101.
[17] LI Yongshu, LIU Gang, ZHANG Shuaiyi. Multi-granularity Complex Network Model Based on GIS [J]. Journal of Southwest Jiaotong University, 2012, 47(3): 406-412. (李永树, 刘刚, 张帅毅. 基于GIS的多粒度复杂网络模型[J]. 西南交通大学学报, 2012, 47(3): 406-412.)
[18] LI Qingquan, ZENG Zhe, YANG Bisheng, LI Bijun. 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.)
[19] West D B. Introduction to Graph Theory [M]. Prentice Hall ,Upper Saddle River, 2001.
[20] Washio T, Motoda H. State of the art of graph-based data mining [J]. SIGKDD Explore News, 2003, 5(1):59-68.
[21] HE Nan, LI Deyi, GAN Wenyan, ZHU Xi. Mining Vital Nodes in Complex Networks [J]. Computer Science, 2007, 34(12): 1-5. (赫南, 李德毅, 淦文燕, 朱熙. 复杂网络中重要性节点发掘综述[J]. 计算机科学, 2007, 34(12): 1-5.)
[22] Crucitti P, Latora V, Porta S. Centrality in Networks of Urban Streets [J]. Chaos, 2006, 16(1): 15113-15122.
[23] 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.)
[24] 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.)