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

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