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

摘要

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