Research On Approximating To The Shortest Path Based On Quotient Space Theory

With the speedup of the humans progress growing faster and faster, the scale of the networks around us is bigger and bigger. Finding the shortest path, one of the most classic problems, has been facing challenges. One of the challenges is that the complexity is too high to search the shortest path of a pair of nodes in a large-scale network. This dissertation proposed a hierarchical-solving algorithm based on the hierarchical granularity of the Quotient Space Theory. In the process of jumping among the different granular spaces, task to find the shortest path could be completed.After the in-depth analysis of the humans ways of thinking, Professor Zhang Ling and Academician Zhang Bo proposed the Quotient Space Model Theory, in which a triples (X,f,T) stands for the problem to be resolved. With the conversion among the different granularities, the original problem can been transformed into a new one expressed as the triples ([X],[f],[T]). While jumping from one level to another, the complex problems could be simplified and resolved. Then construct the final solution of the problem under the original granular space. This thought for problems solving is just based on the humans’ways of thinking:when observing and analyzing problems, we often construct several granular spaces which are very different from each other, and do well to and fro.To solving the shortest path problem in a large-scale network, our hierarchical solving algorithm, which was combined with quotient space theory, divided the large-scale network into lots of sub-networks. Map these sub-networks onto a new network, in which each sub-network was replaced by a new node. With the progress of mapping, the scale of the new network was much smaller than the original one. The two networks were in different levels. The progress of granularity coarsening and refining implemented the jumping from one network to the other. Based on the two basis theories of quotient space, our hierarchical solving algorithm reduced the high complexity to find the shortest path in large-scale networks for the classic algorithms.Main works of this dissertation were as follows: Firstly, search for the community partition methods for different networks. There were weighted networks and unweighted networks. With the standards of the modularity function given by Newman etc, a large-scale network could be divided into several smaller networks. The standards has gotten board recognition and been used to evaluate a new proposed algorithm to be good or not.Secondly, in the basis of community partition, construct hierarchical networks in different granular spaces. Each of the sub-networks was replaced by a new node. That was to say the nodes in the same community were mapped to the same new node in the new network. According to the connection of the original network, connect the new nodes by keeping original connectivity relations. The new network was a higher level one.Thirdly, resolve the final approximate shortest path in the networks under different granular spaces. After the new network had been constructed, we should turn to do the same work in the higher level network. Getting the final solution should return to the original network. Solving the original problem was in the process of jumping from one granular space to another.This dissertation tested and verified our algorithm using several networks generated by computer. Then we applied our algorithm to three traffic networks of the states of the USA. It was hard to find the shortest path using the classic algorithms. In our experiments, we succeeded in doing that. However, the process of forming the new high level network had made some of the overall information lost. So, the solution given by our algorithm might not be the optimal one, but a optimum one. For practical application, this solution could meet the needs. Therefore, with shorter time but lower accuracy, the final solution could also be used in lots of applications.