基于层次随机图的道路选取方法

doi:10.3724/SP.J.1047.2012.00719

地球信息科学学报 ›› 2012, Vol. 14 ›› Issue (6): 719-727.doi: 10.3724/SP.J.1047.2012.00719

• 地球信息科学理论与方法 • 上一篇下一篇

基于层次随机图的道路选取方法

李木梓, 徐柱, 李志林, 张红, 遆鹏

西南交通大学地球科学与环境工程学院, 成都 610031

收稿日期:2012-11-10 修回日期:2012-12-01 出版日期:2012-12-25 发布日期:2012-12-25
通讯作者: 徐柱(1972-),男,博士,教授,博士生导师,研究方向为时空数据分析与挖掘、空间数据综合、空间数据共享等。E-mail:xuzhucn@gmail.com E-mail:xuzhucn@gmail.com
作者简介:李木梓(1985-),女,博士,研究方向为空间数据库、空间数据综合。E-mail:green.sunny@163.com
基金资助:
国土资源公益性行业科研专项经费(201111013);国家自然科学基金项目(40971209);中央高校基本科研业务费专项(SWJTU11CX059,SWJTU11CX063,SWJTU10ZT02)资助。

A Hierarchical Random Graph Based Selection Method for Road Network Generalization

LI Muzi, XU Zhu, LI Zhilin, ZHANG Hong, TI Peng

Department of Remote Sensing and Geographic Information Engineering, Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 610031, China

Received:2012-11-10 Revised:2012-12-01 Online:2012-12-25 Published:2012-12-25

摘要/Abstract

摘要：

道路选取是道路网自动综合的关键问题之一,这方面已有多年研究,虽已取得很大进展,但尚不能自动完成一定比例尺下道路网的选取。本文提出一种基于层次随机图的道路选取方法,通过构建道路网的层次聚类结构以辅助道路选取。层次随机图是一种复杂网络模型,表现为一个二叉树,它不仅可以将复杂的道路网进行层次聚类,而且在可视化的同时提供了不同粒度的聚类信息。在构建道路网的层次随机图的基础上,本文采用累计权重数来衡量每条道路在整体层次结构中的重要性,并据此进行道路选择。我们将该方法应用到不同模式的实际道路网中进行道路选取试验,包括方格形、方格放射状、环形放射状、自由式路网等,以对应的谷歌地图作为参考进行道路选取符合数量、符合长度的定量评价和观察对比定性评价。试验表明本方法的选取结果与谷歌地图符合度很高。此外,与典型的基于路划长度和基于度中心度(degree centrality)的选取方法相比,本文方法更优。最后给出了本文方法优缺点的讨论和进一步研究的展望。

关键词: 道路网, 制图综合, 层次随机图, 复杂网络, 道路网络

Abstract:

Generalization of road network is one of the focuses in map generalization. Road network generalization can be considered as the combination of two processes. One is selective omission, and the other is the simplification of selected roads. Selective omission is the key process, in which it is hard to maintain the overall and key local structures of original networks. Many solutions have been proposed for road selective omission. But previous solutions cannot maintain these structures in the process of selective omission. It will solve the problem if we can build the hierarchical structure of road networks and make selection based on the structure. This paper presents a novel method for selective omission. The method first builds the hierarchical structure of road networks. It is based on Hierarchical Random Graph (HRG) which transforms a graph into a dendrogram, which is widely used in complex networks. HRG goes beyond simple clustering and provides clustering information at all levels of granularity for visualization. But HRG is over detailed for multi-scale representation as its dendrogram usually contains tens or even more layers. So, after building HRG of road networks, we propose a measure named Accumulated Probability Number (APN) to simply HRG hierarchy. APN reflects the importance of each road in the whole network. It should be noted that we use road ‘strokes' as vertices and the connections between them as edges when transforming a road network into a graph. The proposed approach is validated with case studies of road network generalization. Different patterns of road networks are considered including grid, ring-star-hybrid, grid-star-hybrid, irregular patterns. The corresponding Google Map is used as the reference for evaluation of road selection. The results of APN-based selection match well with the reference.

Key words: road networks, map generalization, complex networks, hierarchical random graph, road networks

李木梓, 徐柱, 李志林, 张红, 遆鹏. 基于层次随机图的道路选取方法[J]. 地球信息科学学报, 2012, 14(6): 719-727.DOI:10.3724/SP.J.1047.2012.00719

LI Mu-Zi, XU Zhu, LI Zhi-Lin, ZHANG Gong, TI Feng. A Hierarchical Random Graph Based Selection Method for Road Network Generalization[J]. , 2012, 14(6): 719-727.DOI:10.3724/SP.J.1047.2012.00719

参考文献

[1] Li Z. Algorithmic foundation of multi-scale spatial representation[M]. CRC Press (Taylor & Francis Group), Bacon Raton. 2006: 280.

[2] Mackaness W, Mackechnie G. Automating the detection and simplification of junctions in road networks[J]. GeoInformatica, 1999, 3(2):185-200.

[3] Li Z, Choi Y. Topographic map generalization: Association of road elimination with thematic attributes[J], The Cartographic Journal, 2002, 39(2):153-166.

[4] Thomson R, Richardson D. The ‘good continuation' principle of perceptual organisation applied to the generalisation of road networks [C].//Keller C P (ed.), 19th International Cartographic Conference, ICA, Ottawa, 1999: 1215-1223.

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

[6] Zhou Q, Li Z. A comparative study of various strategies to concatenate road segments into strokes for map generalization[J]. International Journal of Geographical Information Science, 2012, 26(4): 691-715.

[7] Hillier B. Space is the machine: A configurational theory of architecture[M]. Cambridge, UK: Cambridge University Press, 1996.

[8] Hillier B, Hanson J The social logic of space[M]. Cambridge, UK: Cambridge University Press, 1984.

[9] 周亮, 陆锋, 张恒才.基于动态中介中心性的城市道路网实时分层方法 [J] 地球信息科学学报, 2012, 14 (3): 292-298.

[10] Thomson R, Brooks R. Exploiting perceptual grouping for map analysis, understanding and generalization: The case of road and river networks [C]. Graphics Recognition: Algorithms and Applications (GREC 2002),2002: 148-157.

[11] Li Z, Zhou Q. Integration of linear and areal hierarchies for continuous multi-scale representation of road networks[J]. International Journal of Geographical Information Science, 2012, iFirst(1): 1-26.

[12] Jiang B, Lars H. Selection of streets from a network using self-organizing maps[J]. Transactions in GIS, 2004, 8(3): 335-350.

[13] José L, Francisco J. Generalization-oriented road line classification by means of an artificial neural network[J]. GeoInformatica,2008, 12 (3): 289-312.

[14] Deng H, Wu F, Zhai R, Liu W. A generalization model of road networks based on genetic algorithm[J]. Geometrics and Information Science of Wuhan University, 2006, 31(2):164-167.

[15] Morisset B, Ruas A. Simulation and agent modelling for road selection in generalization [C].//proceedings of the ICA 18th International Cartographic Conference, 1997: 1376-1380.

[16] Topfer F, Pillewizer W. The principles of selection[J]. Cartographic Journal, 1966, 3(1): 10-16.

[17] 徐柱,蒙艳姿,李志林,等.基于有向属性关系图的典型道路交叉口结构识别方法[J].测绘学报,2011,40(1):125-131.

[18] Yang B, Luan X, Li Q. An adaptive method for identifying the spatial patterns in road networks[J]. Computers, Environment and Urban Systems, 2010(34):40-48.

[19] Clauset A, Moore C, Newman M. Hierarchical structure and the prediction of missing links in networks. Nature, 2008(453): 98-101.

[20] Wu H. Automatic create tree structure of contours and its applications[J]. Developments in Surveying and Mapping,1996(1): 2-7.

[21] Wu H. The automated construction of tree structure of river network. Geometrics and Information Science of Wuhan University, 1995, supplementary issue.

[22] Rusak Mazur E, Caster H. Horton ordering scheme and the generalisation of river networks[J]. Cartographic Journal, 1990, 27(2):104-112.

[23] Newman M. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2011, 8(1): 25-31.

[24] Wang X, Jiao L, Wu J. Extracting hierarchical organization of complex networks by dynamics towards synchronization[J]. Physica A, 2009(388: 2975-2986.

[25] Corominas-Murtra B, Go i J, Rodríguez-Caso C, Solé R. Measuring the hierarchy of feedforward networks[J]. Chaos, 2011, 21(1):1-12.

[26] Zhang J, Zhang K,Xu X,Tse C and Small M. Seeding the Kernels in Graphs: toward Multi-resolution Community Analysis. New Journal of Physics 11(2009):113003.

[27] Ioannis P, Klapaftis S. Word sense induction & disambiguation using hierarchical random graphs [C]. Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, 2010: 745-755.

[28] Song Q, Wang X. Efficient routing on large road networks using hierarchical communities[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(1):132-140.

[29] Fountain F, Lapata M. Taxonomy induction using hierarchical random graphs [C]. 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Montre'al, Canada, June 3-8, 2012: 466-476,

[30] Jiang B. A topological pattern of urban street networks: Universality and peculiarity[J]. Physica A, 2007(384): 647-655.

[31] Zhang Q. Modeling structure and patterns in road network generalization [C].//Proceeding of 7th ICA workshop on generalisation and multiple representation, Leicester, 2004.

[32] Heinzle F, Anders K, Sester M. Graph based approaches for recognition of patterns and implicit information in road networks [C].//Proceeding of XXII International Cartographic Conference, La Coruna, Spain, 2005.

[33] Heinzle F, Anders K, Sester M. Pattern recognition in road networks on the example of circular road detection[M].//Raubal M, et al. (Eds.). GIScience. Springer, 2006: 153-167).

[34] Mones E, Vicsek L, Vicsek T. Hierarchy measure for complex networks[J]. PLoS ONE, 2012, 7(3): e33799.

基于层次随机图的道路选取方法

A Hierarchical Random Graph Based Selection Method for Road Network Generalization

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	王晓凡, 方志祥, 仲浩宇, 邹欣妍. 传染病防控下的市民慢性病药品现场购药需求的周期优化[J]. 地球信息科学学报, 2021, 23(2): 307-317.
[2]	赵韶雅, 杨星斗, 戴特奇, 张超. 基于刷卡数据的公共汽车客流网络复杂性日内变化研究[J]. 地球信息科学学报, 2020, 22(6): 1254-1267.
[3]	郑诗晨, 盛业华, 吕海洋. 基于粒子滤波的行车轨迹路网匹配方法[J]. 地球信息科学学报, 2020, 22(11): 2109-2117.
[4]	黄梦娜,马廷. 中国道路网引起的景观破碎格局及其对保护区的影响[J]. 地球信息科学学报, 2019, 21(8): 1183-1195.
[5]	秦昆, 罗萍, 姚博睿. GDELT数据网络化挖掘与国际关系分析[J]. 地球信息科学学报, 2019, 21(1): 14-24.
[6]	杨忍, 牟乃夏, 彭澎, 刘希亮, 张恒才, 陆锋. “海上丝绸之路”沿线重要港口竞争力评价[J]. 地球信息科学学报, 2018, 20(5): 623-631.
[7]	方志祥, 余红楚, 黄守倩. 海洋运输网络研究进展与趋势探讨[J]. 地球信息科学学报, 2018, 20(5): 554-563.
[8]	张宏, 王礼茂, 宋涛, 刘大庆, 文娜. 面向全空间的管道天然气贸易关联关系挖掘[J]. 地球信息科学学报, 2017, 19(9): 1253-1260.
[9]	王双, 陈毓芬, 袁烨城, 李伟, 王成舜. 科学合作地域倾向性研究——以中国雾霾研究为例[J]. 地球信息科学学报, 2017, 19(2): 248-255.
[10]	周艳, 李妍羲, 江荣贵, 耿二辉. 交通拥堵与预警信息交互传播动力学分析[J]. 地球信息科学学报, 2017, 19(10): 1279-1286.
[11]	谢坤, 邓敏, 张云菲. 城市道路网的多尺度连续变换方法[J]. 地球信息科学学报, 2016, 18(9): 1160-1166.
[12]	钟翔, 高勇, 邬伦. 基于链接分析的网页文本核心地名提取方法[J]. 地球信息科学学报, 2016, 18(4): 435-442.
[13]	刘康, 段滢滢, 张恒才. 基于路网拓扑层次性表达的驾车路径规划方法[J]. 地球信息科学学报, 2015, 17(9): 1039-1046.
[14]	杜世宏, 雒立群, 赵文智, 郭舟. 多尺度空间关系研究进展[J]. 地球信息科学学报, 2015, 17(2): 135-146.
[15]	陆锋, 刘康, 陈洁. 大数据时代的人类移动性研究[J]. 地球信息科学学报, 2014, 16(5): 665-672.