Short paths in web graphs with small query time
Short paths are found with a small query time in scale-free directed graphs using a two-phase process by which data structures comprising shortest path trees are first pre-computed for a group of central vertices called “hubs” that have short paths to most other vertices in the graph. In a query time phase, a short path between two vertices of interest in the graph is found by looking up the path to the root in each of the shortest path trees.
1. One or more computer-readable storage media storing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for computing short paths in a scale-free directed graph, the method comprising the steps of:
identifying by the one or more processors one or more hubs in the graph where the graph represents a communication network, the hubs being high-degree vertices;
pre-computing data structures for each of the one of more hubs, each of the pre-computed data structures comprising an in-tree and an out-tree, the in-tree including shortest paths directed from vertices in the graph to a given hub, the out-tree including shortest paths directed from the given hub to vertices in the graph, the pre-computing being performed prior to processing of a path query on the graph;
storing the pre-computed data structures;
when during the processing of the path query, an exact shortest path is not found, generating an upper bound on the exact shortest path;
once the upper bound is determined, performing a secondary path finding technique in the neighborhood of the short path in order to find the exact shortest path.
2. The one or more computer-readable storage media of claim 1 in which the method includes a further step of making the pre-computed data structures accessible during the processing of the path query.
3. The one or more computer-readable storage media of claim 1 in which the identifying comprises performing a PageRank algorithm on vertices and edges in the graph or analyzing the vertices' degree.
4. The one or more computer-readable storage media of claim 1 in which the graphs defined by G=(V,E) in which V is a set of vertices and E is a set of directed edges between the vertices and the storing is implemented using only O(|V|) memory.
5. The one or more computer-readable storage media of claim 1 including a further step of utilizing the pre-computed data structures to return a short path in response to the path query in approximately constant time.
6. The one or more computer-readable storage media of claim 5 in which the utilizing comprises finding a short path between two vertices specified in the path query by looking up a path to a hub in each of the pre-computed data structures.
7. The one or more computer-readable storage media of claim 1 in which the scale-free directed graph is associated with one of World Wide Web, social network, or communications network.
8. One or more computer-readable storage media storing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for executing a path query on a scale-free directed graph G=(V,E) in which V is a set of vertices and E is a set of directed edges between the vertices, the method comprising the steps of:
receiving by one or more processors a path query specifying vertices u and v that define a short path search;
accessing a set of data structures, each of the data structures representing a shortest path tree including an in-tree and an out-tree that is associated with respective hubs in the graph where the graph represents a communication network, the hubs being identified as having short paths to other vertices in the graph and having a relatively high degree compared with an average degree for other vertices in the graph;
looking up a shortest path from u to a hub in each in-tree in which u appears and generating a set of trail vertices that are located on a path from u to the hub;
looking up a shortest path from the hub to v in each out-tree in which v appears and generating a set of trail vertices that are located on a path from the hub to v;
locating an intersecting vertex x that is common between the set of trail vertices for u and the set of trail vertices for v; and
combining a path from u to x and a path from x to v to generate a short path from u to v;
generating an upper bound on an exact shortest path from u to v when the generated short path is not the exact shortest path; and
performing a secondary path finding technique in the neighborhood of the short path in order to find the exact shortest path once an upper bound is determined.
9. The one or more computer-readable media of claim 8 in which the method includes a further step of computing lengths of all short paths from u to v that are associated with all the shortest path trees in which u and v appear.
10. The one or more computer-readable media of claim 9 in which the method includes a further step of outputting a shortest path from among the computed lengths of all the short paths.
11. The one or more computer-readable media of claim 8 in which the data structures are pre-computed in advance of the step of accessing.
12. The one or more computer-readable media of claim 8 in which the hubs are each associated with shortest path trees having relatively small depth.
13. The one or more computer-readable media of claim 8 in which the short path from u to v is generated by only accessing the set of data structures but not the entire graph G.
14. A machine-implemented method for providing a web graph service for executing a path query on a scale-free directed graph G=(V,E) in which V is a set of vertices and E is a set of directed edges between the vertices, the method comprising the steps of:
pre-computing by one or more processors short path trees for each of a selected group of central vertices within a scale-free directed graph where the graph represents a communication network, each of the central vertices being a root of respective pre-computed short path trees and having a relatively high degree compared with an average degree for other vertices in the graph;
receiving a path query comprising vertices u and v between which a short path is calculable;
performing lookups on the pre-computed short path trees to identify a path from u to a root and a path from the root to v;
generating a short path from u to v using the identified paths;
generating an upper bound on an exact shortest path from u to v when the generated short path is not the exact shortest path; and
performing a secondary path finding technique in the neighborhood of the short path in order to find the exact shortest path once an upper bound is determined.
15. The machine-implemented method of claim 14 in which the generating comprises finding a common vertex of intersection x between the path from u to the root and the path from the root to v and combining a path from u to x with a path from x to v.
16. The machine-implemented method of claim 15 in which the pre-computed short path trees comprise an in-tree and an out-tree, the in-tree including shortest paths directed from vertices in the graph to a given root, the out-tree including shortest paths directed from the given root to vertices in the graph.
17. The machine-implemented method of claim 14 including a further step of iterating the generating step for each of the pre-computed short path trees in which u and v appear.
18. The machine-implemented method of claim 17 including the further steps of computing a length of each combined path resulting from the iterating step, and outputting a shortest computed path.