Shortest Path Approximation Algorithm In Very Large Graph

The shortest path algorithm is one of the classical algorithms. The shortest path algorithm used not only in computer science but also other practical problems, such as the optimization on road planning and design, the disposition of sensors and so on. It is also used in the research on discover the community in graph, compute the edge between of nodes, search the central node or the recommendation of commodity. The problems related to shortest path algorithm is increase with the rapid social development. The scale is too huge to compute by the classical algorithm of Dijkstra or Floyd. The weakness of classical algorithm is the high complexity, the huge calculated amount, the redundancy of data and scarce capacity in the processing of big data. Therefore, the approximation shortest path algorithm based on super-large scale graph is used to overcome these difficulties. There are two sorts of algorithms:the approximation shortest path algorithm based on Centers Distance of Zone (short for CDZ) and the shortest path estimation for large social graphs based on coordinate (short for Orin). CDZ is good at complex networks, and the Orin has better accuracy, but need high operation of propose process. According to the research on social network, many characteristics of huge network were discovered by researcher in the field of statistics. These characteristics are benefit for the optimization of shortest path algorithm used in super-large networks. So we raised out a new algorithm on the basis of the existing algorithms, the above is our main achievements.1) By analyzing complex network, some basic network model and characteristic statistic of complex network, we find a way to shrink the super-large graph rapidly. We find the breakthrough by analyzing the shortest path approximation algorithm on super networks and classical algorithm.2) We raised shortest path approximation algorithm based on the thumbnail network according to the self-similar characteristic on super-large graph. We lower the network size and shorten the preprocess time by constructing the thumbnail network. Our algorithms use the self-similar characteristic to shrink complex network. After preprocessing, compute the approximate value of shortest path by formula.3) On the basis of approximate value of shortest path, approximate the number of paths which go through this node by the size of landmark, and calculate the betweenness of shrink node according to the formula. We calculate out the betweenness of every node of the thumbnail network according to the formula of betweenness centrality.4) Contrastive analysis our algorithm with other algorithms by different scale of datasets, verify the performance of our algorithms.5) Use WindowBuilder Pro plug-in to realize shortest distance Oracle, the program contains preprocess, inquire of approximate shortest path and calculation of betweenness.Experimental results reveal that our algorithm is better than others, it increase the efficiency and keep the accuracy. It takes only a few milliseconds to deal with the network that has million nodes and ten million edges; it is ten times faster than CDZ and faster than Orin. Our algorithm is also better than UB and CDZ in the part of betweenness centrality with the improvement of efficiency and decrease of accuracy slightly.