基于路标的最短路径长度快速估计算法

A Landmark-Based Fast Shortest-Path Length Estimation Algorithm

针对大规模复杂网络中最短路径精确算法计算复杂的问题,提出一种基于路标的最短路径长度快速估计算法——SSPS算法。论证了SSPS算法的估计精度优于已有的Potamias算法;采用多种路标选择策略,使用多个数据集对比了SSPS算法与Potamias算法的性能。实验结果表明:SSPS算法的估计精度优于Potamias算法,且在最简单的随机路标选择策略中表现出良好的估计精度,可以较好地应用于大规模复杂网络最短路径长度的估算中。

In order to solve the problem of high computational complexity of the exact shortest-path algorithms in large-scale complex networks, this paper presents a fast shortest-path length estimation algorithm based on the concept of landmark, called as the SSPS algorithm. The paper demonstrates that the estimation precision of the SSPS algorithm is better than that of the state-of-the-art Potamias algorithm. Under a variety of landmark-selection strategies, the performance of the SSPS algorithm and the Potamias algorithm is compared using some public datasets. The experimental results have shown that the SSPS algorithm is obviously better than the Potamias algorithm in terms of estimation precision, and the SSPS algorithm with a simple random landmark-selection strategy shows good estimation accuracy. It can be applied in the fast estimation of shortest-path lengths in large-scale complex networks.