Journal of Geo-information Science >
A Hierarchical Random Graph Based Selection Method for Road Network Generalization
Received date: 2012-11-10
Revised date: 2012-12-01
Online published: 2012-12-25
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.
LI Mu-Zi, XU Zhu, LI Zhi-Lin, ZHANG Gong, TI Feng . A Hierarchical Random Graph Based Selection Method for Road Network Generalization[J]. Journal of Geo-information Science, 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.
/
| 〈 |
|
〉 |