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

Abstract

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

CLC Number:

P208

References

[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.)