The shortest path approximation algorithm for large scale road network

doi:10.11947/j.AGCS.2019.20180007

Acta Geodaetica et Cartographica Sinica ›› 2019, Vol. 48 ›› Issue (1): 86-94.doi: 10.11947/j.AGCS.2019.20180007

• Cartography and Geoinformation • Previous Articles Next Articles

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

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

CLC Number:

P208

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments