Abstract: The processing efficiency of classical shortest path algorithms for complex networks is not suitable for large-scale complex networks, moreover, the existing approximation algorithms are limited in generality and accuracy of calculation for increasing scale of complex networks. [K]-shell shortest path approximation algorithm for complex networks is proposed to solve the above problem. The [k]-shell value of nodes is used to divide the network and guide the search path, the [k]-shell sub-net is processed by super-node aggregation to reduce the size of nodes and edges in the path search, and the computational efficiency and accuracy of the algorithm are improved by using the bi-directional search tree in the path search process. Experimental results show that the algorithm has better generality and higher computational efficiency and accuracy in real and simulated large-scale complex networks.

Key words: complex network, shortest path, [k]-shell, super-node aggregation, bi-directional search tree

摘要： 复杂网络最短路径经典算法的处理效率较低，不适用于大规模复杂网络，而现有近似算法通用性有限，且计算准确率不理想，不能满足规模日益扩大的复杂网络中的最短路径计算需求。针对于此，提出基于[k]-shell的复杂网络最短路径近似算法。算法利用节点的[k]-shell值进行网络划分并引导搜索路径，利用超点聚合处理[k]-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明，算法通用性较好，在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率。

关键词: 复杂网络, 最短路径, [k]-shell, 超点聚合, 双向搜索树