面向大规模道路网的最短路径近似算法

doi:10.11947/j.AGCS.2019.20180007

测绘学报 ›› 2019, Vol. 48 ›› Issue (1): 86-94.doi: 10.11947/j.AGCS.2019.20180007

面向大规模道路网的最短路径近似算法

张志然^1,2, 刘纪平^2,3, 仇阿根², 钱新林², 张福浩²

1. 武汉大学资源与环境科学学院, 湖北武汉 430079;
2. 中国测绘科学研究院, 北京 100830;
3. 河南省科学院地理研究所, 河南郑州 450052

收稿日期:2018-01-03 修回日期:2018-09-20 出版日期:2019-01-20 发布日期:2019-01-31
通讯作者: 刘纪平 E-mail:liujp@casm.ac.cn
作者简介:张志然(1991-),女,博士生,研究方向为空间数据分析与挖掘。E-mail:zzranature@163.com
基金资助:
国家重点研发计划（2016YFC0803108）；国家基础测绘科技项目（2018KJ0104）

The shortest path approximation algorithm for large scale road network

ZHANG Zhiran^1,2, LIU Jiping^2,3, QIU Agen², QIAN Xinlin², ZHANG Fuhao²

1. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China;
2. Chinese Academy of Surveying and Mapping, Beijing 100830, China;
3. Institute of Geographical Sciences, Henan Academy of Sciences, Zhengzhou 450052, China

Received:2018-01-03 Revised:2018-09-20 Online:2019-01-20 Published:2019-01-31
Supported by:
The National Key Research and Development Program of China (No. 2016YFC0803108);The National Basic Surveying and Mapping Technological Project (No. 2018KJ0104)

摘要/Abstract

摘要：

节点重要性对大规模道路网下最短路径的计算有着重要影响。本文提出了顾及节点重要性的最短路径估计方法，该方法基于Critic方法与复杂网络理论评价节点的重要性，结合限制策略实现网络划分，通过层次结构网络的构建，实现大规模道路网数据的有效化简和最短路径的快速有效计算。试验结果表明，该方法能够使中心节点均衡地分布于网络，更好地均衡划分后子网络的规模；随着限制参数的增大，网络规模逐渐降低，查询精度最高达到1.026，相比于单一指标和无限制参数的方法，本文方法显著降低了网络的规模，在最短路径的近似计算上保持了较高的准确性，为大规模复杂网络的近似分析提供分析思路。

关键词: 大规模道路网, 最短路径, 节点重要性, 网络划分

Abstract:

Node importance has significant influence on the calculation of shortest path of large-scale road network. A shortest path estimation method based on node importance is proposed in this paper that is suitable for large-scale network. This method integrates the criteria importance though intercrieria correlation (CRITIC) method with complex network theory, with a view to evaluate nodes importance. By combining the restriction strategy to realize network division, the effective simplification of large-scale road network and shortest path estimation are realized through the construction of hierarchical network. The results show that this method can be used to distribute the center nodes evenly, and make little difference in the size of the subnetwork. As the constraint parameter increases, the numbers of nodes and edges reduced gradually, and the query accuracy reached 1.026. Compared with single index and unlimited parameters methods, this paper significantly reduces the size of the network and obtains a high accuracy on the approximate calculation of the shortest path. These will provide a new way of thinking for approximate analysis of large-scale complex networks.

Key words: large-scale road network, shortest path, node importance, network partition

中图分类号:

P208

张志然, 刘纪平, 仇阿根, 钱新林, 张福浩. 面向大规模道路网的最短路径近似算法[J]. 测绘学报, 2019, 48(1): 86-94.

ZHANG Zhiran, LIU Jiping, QIU Agen, QIAN Xinlin, ZHANG Fuhao. The shortest path approximation algorithm for large scale road network[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(1): 86-94.

参考文献

[1] BOVY P H L, STERN E. Route choice:wayfinding in transport networks[M]. Alphen, Netherlands:Kluwer Academic Publishers, 2012.
[2] 宋青. 大规模网络最短路径的分层优化算法研究[D]. 上海:上海交通大学, 2012. SONG Qing. Research on hierarchical shortest path algorithms for large-scale networks[D]. Shanghai:Shanghai Jiao Tong University, 2012.
[3] MIHALAK M, ŠRAMEK R, WIDMAYER P. Approximately counting approximately-shortest paths in directed acyclic graphs[J]. Theory of Computing Systems, 2016, 58(1):45-59.
[4] MAUE J, SANDERS P, MATIJEVIC D. Goal directed shortest path queries using precomputed cluster distances[C]//Proceedings of 2006 International Workshop on Experimental and Efficient Algorithms. Berlin:Springer, 2006:316-327.
[5] GOLDBERG A V, WERNECK R F. Computing point-to-point shortest paths from external memory[C]//Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics. Vancouver:SIAM, 2005,:26-40.
[6] IDWAN S, ETAIWI W. Computing breadth first search in large graph using hMetis partitioning[J]. European Journal of Scientific Research, 2009, 29(2):215-221.
[7] QIAO Miao. Query processing in large-scale networks[D]. Hong Kong:The Chinese University of Hong Kong, 2013.
[8] POTAMIAS M, BONCHI F, CASTILLO C, et al. Fast shortest path distance estimation in large networks[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management. Hong Kong, China:ACM, 2009:867-876.
[9] KRIEGEL H P, KRÖGER P, RENZ M, et al. Hierarchical graph embedding for efficient query processing in very large traffic networks[M]//Scientific and Statistical Database Management. Berlin:Springer, 2008:150-167.
[10] KLEINBERG J, SLIVKINS A, WEXLER T. Triangulation and embedding using small sets of beacons[C]//Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. Rome, Italy:IEEE Computer Society, 2004:444-453.
[11] FRANCIS P, JAMIN S, JIN Cheng, et al. IDMaps:a global internet host distance estimation service[J]. IEEE/ACM Transactions on Networking, 2001, 9(5):525-540.
[12] WANG Shibo, ZHAO Jinlou. Multi-attribute integrated measurement of node importance in complex networks[J]. Chaos, 2015, 25(11):113105.
[13] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法[J]. 物理学报, 2013, 62(2):54-62. YU Hui, LIU Zun, LI Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J]. Acta Physica Sinica, 2013, 62(2):54-62.
[14] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3):215-239.
[15] BRANDES U. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2):163-177.
[16] BAVELAS A. Communication patterns in task-oriented groups[J]. Journal of the Acoustical Society of America, 1950, 22(6):725-730.
[17] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684):440-442.
[18] BONACICH P. Some unique properties of eigenvector centrality[J]. Social Networks, 2007, 29(4):555-564.
[19] 刘刚, 李永树, 杨骏, 等. 对偶图节点重要度的道路网自动选取方法[J]. 测绘学报, 2014, 43(1):97-104. DOI:10.13485/j.cnki.11-2089.2014.0014. LIU Gang, LI Yongshu, YANG Jun, et al. Auto-selection method of road networks based on evaluation of node importance for dual graph[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(1):97-104. DOI:10.13485/j.cnki.11-2089.2014.0014.
[20] YANG Yunyun, XIE Gang, XIE Jun. Mining important nodes in directed weighted complex networks[J]. Discrete Dynamics in Nature and Society, 2017(5):1-7.
[21] 栾学晨, 杨必胜, 张云菲. 城市道路复杂网络结构化等级分析[J]. 武汉大学学报(信息科学版), 2012, 37(6):728-732. LUAN Xuechen, YANG Bisheng, ZHANG Yunfei. Structural hierarchy analysis of streets based on complex network theory[J]. Geomatics and Information Science of Wuhan University, 2012, 37(6):728-732.
[22] 李清泉, 曾喆, 杨必胜, 等. 城市道路网络的中介中心性分析[J]. 武汉大学学报(信息科学版), 2010, 35(1):37-41. 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.
[23] DIAKOULAKI D, MAVROTAS G, PAPAYANNAKIS L, et al. Determining objective weights in multiple criteria problems:the CRITIC method[J]. Computers & Operations Research, 1995, 22(7):763-770.
[24] 唐晋韬, 王挺, 王戟. 适合复杂网络分析的最短路径近似算法[J]. 软件学报, 2011, 22(10):2279-2290. TANG Jintao, WANG Ting, WANG Ji. Shortest path approximate algorithm for complex network analysis[J]. Journal of Software, 2011, 22(10):2279-2290.
[25] DIJKSTRA E W. A note on Two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1):269-271.
[26] 陆锋. 最短路径算法:分类体系与研究进展[J]. 测绘学报, 2001, 30(3):269-275. LU Feng. Shortest path algorithms:taxonomy and advance in research[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(3):269-275.
[27] LI Qingquan, CHEN Biyu, WANG Yafei, et al. A hybrid link-node approach for finding shortest paths in road networks with turn restrictions[J]. Transactions in GIS, 2015, 19(27):3059-3068.

面向大规模道路网的最短路径近似算法

The shortest path approximation algorithm for large scale road network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价