Research On Shortest Path Approximation Algorithm For Multidimensional Networks Based On K-shell

With the development of society and the deepening of research,the study of complex networks has gradually shifted from single-dimensional network to multidimensional network,the edges between multidimensional network nodes contain the weights of multiple dimensions.The shortest path calculation of multidimensional network needs to consider the weights of multiple dimensions comprehensively.The specific cost of the path can be obtained by calculating the given scoring function.The calculation methods of the shortest path in one-dimensional networks are based on the sub-path properties of Dijkstra algorithm,however,the sub-path property is not applicable if the scoring function of multidimensional network is a non-linear function,therefore,the shortest path algorithm for one-dimensional networks is not suitable for multidimensional networks.At present,the research on the shortest path of multidimensional network is still less,and the applicability of existing methods is poor,the computational efficiency and accuracy can not meet the needs of the shortest path calculation in large-scale multidimensional networks.Based on the existing research,this paper proposes a shortest path approximation algorithm for multidimensional networks based on k-shell.The algorithm divides the network into high-level and low-level areas according to the k-shell value of nodes,bidirectional search tree is used in the search process,the k-shell value of the node is used to control the search direction and the switch between two search trees.The shortest path between the pairs of nodes is searched alternately from the lower level to the higher level,alternately searching the shortest path between pairs of nodes from the lower level to the higher level,the search process ends when the search queue is empty or reaches the high-level area,and selects a path with the least cost under the scoring function as the approximate shortest path.The algorithm searches in the direction of high k-shell value neighbor nodes of current nodes.Considering the influence of k-shell value of nodes andk-shell value of neighbor nodes on nodes,the node back-off value is proposed to measure the importance of nodes in the shortest path search process.The accuracy of the algorithm is improved by appropriate back-off search through node back-off value,and by adjusting the back-off threshold,the algorithm can meet the needs of different computational efficiency and accuracy,so that the algorithm can be applied to different types of networks.In the shortest path search process,a fast method to calculate the initial search threshold is given,and based on the bidirectional search process,a bidirectional pruning strategy suitable for this algorithm is given,which can more quickly and accurately prune sub-paths that can not appear on the shortest path and improve the calculation efficiency of the algorithm.This paper validates that retrogressive search based on node back off value can effectively improve the accuracy of the algorithm in the shortest path search process on the same network firstly,then,this paper verifies the applicability of the proposed algorithm to different types of complex networks,finally,the algorithm is compared with other similar algorithms,the results show that the proposed algorithm has high computational efficiency and accuracy in the shortest path calculation of multidimensional networks.