Research On Hierarchical Shortest Path Algorithms For Large-Scale Networks

Computing the shortest paths in graphs is one of the most fundamental andwell-studied problems in network algorithms. Numerous real-world applications haveattracted research investigations for more than half a century, involving researchersfrom many fields including operational research, computer science, geographicinformation science, and public transportation. Finding routes in road networks is aclassical application motivating the study of the shortest path problem, and thisproblem also arises in many other domains of practical importance. For example, thetransmission of messages in a computer network is most efficient when they are sentby the shortest sequence of routers; In social networks, one would like to establishcontact with a stranger through least connections of friends and their followers.Considering that real systems are usually very large, and conventional shortest pathalgorithms failed to apply to large-scale problems due to their heavy computationalcomplexity and memory consumption; thus, there is a considerable interest in speeduptechniques, which typically invest some time into a preprocessing task in order togenerate auxiliary data that can be used to accelerate the subsequent path queries. Thisthesis investigates the problem of computing shortest paths more efficiently andaccurately based on the current research experiences and achievements, following abasic idea of hierarchical optimization for the original problem decomposition. Themain content and contributions of this thesis are summarized as follows:1. From a new research perspective of complex network theory, we integrate therecent achievements on hierarchical topology and community structure intohierarchical modeling of large-scale networks, measuring of dynamic networkpartition qualities, and also designing of subsequent path computationalgorithms, which yield promising results.2. We propose a graph partition model with the objective of minimizing thetraversing distance ratio of each subgraph, and we develop a partition algorithm for achieving this model, which provides a new way for non-planargraph partitioning and partition quality measuring of dynamic networks.3. We develop a hierarchical graph model, including the high-level graph and theabstraction graph, which are constituted respectively by extracting the bordernodes, the intercommunity edges, and the constructed community edges withineach subgraph of the partitioned network, and by mapping the subgraphs andtheir connections as nodes and edges. The model decreases the number ofnodes and edges substantially compared to the original network, therebygreatly reducing the search complexity of a hierarchical algorithm.4. We propose a fast hierarchical shorest path algorithm based on the heuristics ofsubgraph coordinates. For the source and destination nodes that located in thesame subgraph, the algorithm achieves acceleration by restricting the search toa rebuilding area; While for the source and destination nodes in differentsubgraphs, the algorithm makes use of the definition of subgraph coordinatesand subgraph distances to select the subgraphs for visit, and it can get differenttradeoffs between efficiency and accuracy via the regulation of the followingthree parameters: the number of selected subgraph pairs α, the distancecoefficient β, and the benchmark of overlapping nodes γ.5. We propose another fast hierarchical shortest path algorithm with broaderapplication, which is based on the subgraph pruning technique. The algorithmmaintains a close upper bound d (s,t)on the length of the shortest path fromthe source node s to the destination node t, which is tightened repeatedly duringthe algorithm execution. Whenever the search branch is about to leave asubgraph via the current node u, a lower estimate d(s,u,t) is calculated on thelength of a possible route from s via u to t. If this lower estimate exceeds thecurrent upper bound, then all searches from u together with those grow into theadjacent subgraph of u will be pruned, thereby eliminating unnecessarysearches and thus achieving acceleration.6. We give a theoretical analysis of the accuracy and the computationalcomplexity of the proposed subgraph coordinates based and the subgraphpruning technique based hierarchical shortest path algorithms, and we presentexperimental tests to compare and analyze the performance achievements ofthese two hierarchical algorithms to the existing algorithm under different network partition schemes. We point out the strengths and weaknesses of thetwo algorithms, and demonstrate their effectiveness from both theoretical andexperimental aspects.