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

The shortest path algorithm is one of the classical problems in graph theory research and algorithm design.Aiming to find the shortest path between two vertices in the graph,it has been widely used in many fields in real world,such as social network,traffic geographic information system,path planning,biomedicine,bio-information network and military integrated transportation.The shortest path algorithm is not only a hot topic in the field of computer science and technology,but also has been paid close attention by researchers in other fields.With the arrival of the big data age in recent years,the data scale has been increasing,the topology of data is more and more complicated,current shortest path algorithm is unable to meet the increasing demand of data scale and inquiry speed,so it is necessary to design a faster and more effective shortest path algorithm.In this paper,we study the existing shortest path algorithm,and find that whether the accurate shortest path algorithm or the approximate shortest paths algorithm in the current main research,it is difficult to meet the increasing data size.A large scale network graph with more and more intricate structure,aiming at the characteristic of complex network with small world model and scale-free,the research direction of shortest path algorithm is usually starting from two-stage query method.The first stage is aiming to preprocess data,and establishing label index information.The second stage uses the results of preprocessing data to search the target problem online.Therefore,how to balance the relationship among the preprocessing cost,the speed of online search and the accuracy of query results will be the key problem of the two-stage query method,and the main content and direction of this paper.Aiming at the topological characteristics of complex network structure in real life,this paper presents an approximate shortest path algorithm suitable for large-scale complex network graphs,an approximate shortest path algorithm based on hub vertex of the area and Core Expressway.The algorithm first calculates the vertex' degree and equilibrium value,chooses a small number of hub vertex of the area in the graph,and uses the hub vertex of the area to segment the complex network into subgraphs,in which hub vertex of the area with the largest degree is called core vertex of area.The Core Expressway is constructed by using the hub vertex of the area for each subgraph,and the Freeway is established by the core vertex of the area.Hub vertex of the area,core vertex of the area,Core Expressway and Freeway can be drawn according to the preprocessing work,this paper proposes an OKA approximate shortest path query algorithm,and gives the corresponding query strategy.According to the above data preprocessing results and vertex in different subgraphs,using the shortest path between the hub vertex of the area,core vertex of the area,the hub vertex of area and core vertex of area are approximate to calculate the shortest path in the large-scale complex network,which can effectively reduce the search space and improve the efficiency of online query.Finally,by comparing and analyzing the experimental results with the other three approximate shortest path algorithms,it proves that the HEA-CE approximate shortest path algorithm in this paper can reduce the complexity of the algorithm in large-scale complex network analysis,improves the efficiency of online search,have high accuracy,and validates the validity of this algorithm.