Research On Shortest Path Approximation Algorithm For Large-scale Complex Networks

The method of the shortest path calculation between any two points of a complex network is not only applied to many practical application scenarios such as information and communication,transportation and disaster warning,but also the basis for the calculation of the characteristic quantity of a complex network.Thus,the shortest path problem has gained the attention of scholars in many fields.The network scale has far exceeded the applicability of the shortest path classical algorithm and the approximation algorithm has become a feasible alternative solution with the arriving of the big data era.However,the efficiency gains of existing approximation algorithms are all at the expense of a large amount of preprocessing or search accuracy,which cannot simultaneously meet the requirements of high accuracy and low latency for shortest path computation in large-scale networks.Therefore,designing more efficient approximation algorithms for shortest path while guaranteeing high accuracy of the results is an important goal of current research.This thesis researches and analyzes the pain points of existing approximation algorithms and proposes a shortest path approximation algorithm based on deterministic coverage network to break the barrier of shortest path computation at the level of deterministic network,which provides a new solution idea for this direction.The main work of this thesis is as follows.(1)The existing approximation algorithms rely on high-complexity classical algorithms for exact path search among high-level network nodes,which leads to low computational efficiency in the preprocessing stage.The algorithm in this thesis abstracts the overlay network with deterministic topology based on the iterative rules of the deterministic network model over the non-deterministic actual complex network,and uses the advantage that the deterministic network can derive the shortest path resolution solution directly from the determined position relationship between nodes to achieve the shortest distance between any two points of the complex network estimated with linear time complexity to solve this problem,which improves the computational efficiency of the preprocessing stage.(2)The hierarchical class approximation algorithm divides the underlying real network into regions based on high-level nodes,so that nodes in different regions access each other through high-level paths to improve the efficiency of shortest path search.The algorithm in this thesis is based on the node centrality index to filter the set of marker nodes with high influence on the coverage network,and adjusts the scale of the set according to the topological characteristics of the actual network,so that the area divided based on the marker nodes is more consistent with the topological structure characteristics of the real network and improves the accuracy of the algorithm.(3)The path search process is optimized using a combination of shortest path algorithm acceleration techniques,and a target-guided search method based on marked node distances is designed to accelerate the approximate solution process by compressing the search space.This thesis takes real network datasets with different sizes and types to experiments and analyzes the described algorithms,and selects the representative shortest path approximation algorithm CDZ based on the distance of region centroid and KS based on k-shell for comparison experiments.The experimental results verify that the algorithm proposed in this thesis can effectively reduce the complexity of the preprocessing stage,improve the search efficiency,and ensure that the approximate results have high accuracy in the approximate search of the shortest path in large-scale complex networks.