Many graph processing algorithms require determination of shortest-path distances between arbitrary numbers of node pairs. Since computation of exact distances between all node-pairs of a large graph, e.g., 10M nodes and up, is prohibitively expensive both in computational time and storage space, distance approximation is often used in place of exact computation. A distance oracle is a data structure that answers inter-point distance queries more efficiently than in standard O(n 2 ) in time or storage space for an n node graph, e.g., in O(nlogn). In this paper, we present a novel and scalable distance oracle that leverages the hyperbolic core of real-world large graphs for fast and scalable distance approximation via spanning trees. We show empirically that the proposed oracle significantly outperforms prior oracles on a random set of test cases drawn from public domain graph libraries. There are two sets of prior work against which we benchmark our approach. The first set, which often outperforms all other oracles, employs embedding of the graph into low dimensional Euclidean spaces with carefully constructed hyperbolic distances, but provides no guarantees on the distance estimation error. The second set leverages Gromov-type tree contraction of the graph with the additive error guaranteed not to exceed 2δ logn, where δ is the hyperbolic constant of the graph. We show that our proposed oracle 1) is significantly faster than those oracles that use hyperbolic embedding (first set) with similar approximation error and, perhaps surprisingly, 2) exhibits substantially lower average estimation error compared to Gromovlike tree contractions (second set). We substantiate our claims through numerical computations on a collection of a dozen real world networks and synthetic test cases from multiple domains, ranging in size from 10s of thousand to 10s of millions of nodes.
Distance oracles have been investigated both from theoretical and practical perspectives. As described earlier, our focus is on distance oracles that provide accurate distance estimates on large real-world graphs rapidly (a few microseconds) while having scalable preprocessing and near-linear storage requirement. This category includes a number of recent practical heuristics @cite_12 @cite_24 @cite_14 @cite_43 @cite_5 @cite_6 ) that aim to estimate distance by embedding the graph in geometric spaces, like Euclidean or Hyperbolic, or by extracting different kinds of approximating trees from the real graph. Other heuristics, such as, @cite_43 @cite_8 or the landmark based approaches with diverse seeding strategies @cite_31 use variants of breadth first search (BFS) trees. We also remark that the sketch-based distance oracle by @cite_26 , that engineers a distance oracle with provable multiplicative guarantees, is similar in nature to other approaches cited above. On the other side, there are some theoretical approaches @cite_27 @cite_37 @cite_18 @cite_17 that prove worst-case bounds on accuracy for specific graph classes such as those with power-law degree distribution or those with small graph hyperbolicity @cite_0 @cite_10 @cite_40 . These techniques have not been evaluated on large real-world graphs. We evaluate some of these techniques for benchmarking of our oracle's performance.
@cite_37 @cite_14 @cite_26 @cite_18 @cite_8 @cite_6 @cite_24 @cite_43 @cite_27 @cite_0 @cite_40 @cite_5 @cite_31 @cite_10 @cite_12 @cite_17
2142420687 2159394589 1512819151 2140271346 2152306920 2029803751 2141663929 2151954369 2172107427 1587282847 2283762717 1965650021
We introduce a novel measure called e-four-pointscondition (e-4PC), which assigns a value e ∈ [0,1] to every metric space quantifying how close the metric is to a tree metric. Data-sets taken from real Internet measurements indicate remarkable closeness of Internet latencies to tree metrics based on this condition. We study embeddings of e-4PC metric spaces into trees and prove tight upper and lower bounds. Specifically, we show that there are constants c1 and c2 such that, (1) every metric (X,d) which satisfies the e-4PC can be embedded into a tree with distortion (1+e)c1log|X|, and (2) for every e ∈: [0,1] and any number of nodes, there is a metric space (X,d) satisfying the e-4PC that does not embed into a tree with distortion less than (1+e)c2log|X|. In addition, we prove a lower bound on approximate distance labelings of e-4PC metrics, and give tight bounds for tree embeddings with additive error guarantees. We study the fundamental problem of computing distances between nodes in large graphs such as the web graph and social networks. Our objective is to be able to answer distance queries between pairs of nodes in real time. Since the standard shortest path algorithms are expensive, our approach moves the time-consuming shortest-path computation offline, and at query time only looks up precomputed values and performs simple and fast computations on these precomputed values. More specifically, during the offline phase we compute and store a small "sketch" for each node in the graph, and at query-time we look up the sketches of the source and destination nodes and perform a simple computation using these two sketches to estimate the distance. The emergence of real life graphs with billions of nodes poses significant challenges for managing and querying these graphs. One of the fundamental queries submitted to graphs is the shortest distance query. Online BFS (breadth-first search) and offline pre-computing pairwise shortest distances are prohibitive in time or space complexity for billion-node graphs. In this paper, we study the feasibility of building distance oracles for billion-node graphs. A distance oracle provides approximate answers to shortest distance queries by using a pre-computed data structure for the graph. Sketch-based distance oracles are good candidates because they assign each vertex a sketch of bounded size, which means they have linear space complexity. However, state-of-the-art sketch-based distance oracles lack efficiency or accuracy when dealing with big graphs. In this paper, we address the scalability and accuracy issues by focusing on optimizing the three key factors that affect the performance of distance oracles: landmark selection, distributed BFS, and answer generation. We conduct extensive experiments on both real networks and synthetic networks to show that we can build distance oracles of affordable cost and efficiently answer shortest distance queries even for billion-node graphs. Computing the shortest path between a pair of vertices in a graph is a fundamental primitive in graph algorithmics. Classical exact methods for this problem do not scale up to contemporary, rapidly evolving social networks with hundreds of millions of users and billions of connections. A number of approximate methods have been proposed, including several landmark-based methods that have been shown to scale up to very large graphs with acceptable accuracy. This paper presents two improvements to existing landmark-based shortest path estimation methods. The first improvement relates to the use of shortest-path trees (SPTs). Together with appropriate short-cutting heuristics, the use of SPTs allows to achieve higher accuracy with acceptable time and memory overhead. Furthermore, SPTs can be maintained incrementally under edge insertions and deletions, which allows for a fully-dynamic algorithm. The second improvement is a new landmark selection strategy that seeks to maximize the coverage of all shortest paths by the selected landmarks. The improved method is evaluated on the DBLP, Orkut, Twitter and Skype social networks. Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick [2001] to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by [2000]. Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme. Let n denote the number of nodes in the network. We provide a labeled routing scheme that, after a stretch--5 handshaking step (similar to DNS lookup in TCP IP), routes messages along stretch--3 paths. We prove that, instead of routing tables with O(n1 2) bits (O suppresses factors logarithmic in n) as in the general scheme by Thorup and Zwick, expected sizes of O(nγ log n) bits are sufficient, and that all the routing tables can be constructed at once in expected time O(n1+γ log n), with γ = τ-22 τ-3 + e, where τ∈(2,3) is the power-law exponent and e 0 (which implies e With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick [2001, 2005] for stretch-3 and we obtain a new upper bound of expected O(n1+γ) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5--approximate distance queries in time at most O(n1 4+e) (similar to γ, the exponent actually depends on τ and lies between e and 1 4 + e). Let G= (V, E) be a connected graph endowed with the standard graph-metric dGand in which longest induced simple cycle has length? (G). We prove that there exists a tree T= (V,F ) such that| dG(u, v) ?dT(u, v)| ? ??(G)2? +?for all vertices u, v?V, where?= 1 if ?(G) ?= 4, 5 and ?= 2 otherwise. The case ?(G) = 3 (i.e., G is a chordal graph) has been considered in Brandstadt, Chepoi, and Dragan, (1999) J.Algorithms 30. The proof contains an efficient algorithm for determining such a treeT . δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points u,v,w,x, the two larger of the distance sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most 2δ. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted δ-hyperbolic graphs. Using the Layering Partition technique, we show that every n-vertex δ-hyperbolic graph with δ≥1 2 has an additive O(δlog n)-spanner with at most O(δn) edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of δ-hyperbolic graphs with an additive error O(δlog n). The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of n-vertex δ-hyperbolic graphs with δ≥1 2 admits a routing labeling scheme with O(δlog 2 n) bit labels, O(δlog n) additive stretch and O(log 2(4δ)) time routing protocol, and a distance labeling scheme with O(log 2 n) bit labels, O(δlog n) additive error and constant time distance decoder. Shortest paths and shortest path distances are important primary queries for users to query in a large graph. In this paper, we propose a new approach to answer shortest path and shortest path distance queries efficiently with an error bound. The error bound is controlled by a user-specified parameter, and the online query efficiency is achieved with prepossessing offline. In the offline preprocessing, we take a reference node embedding approach which computes the single-source shortest paths from each reference node to all the other nodes. To guarantee the user-specified error bound, we design a novel coverage-based reference node selection strategy, and show that selecting the optimal set of reference nodes is NP-hard. We propose a greedy selection algorithm which exploits the submodular property of the formulated objective function, and use a graph partitioning-based heuristic to further reduce the offline computational complexity of reference node embedding. In the online query answering, we use the precomputed distances to provide a lower bound and an upper bound of the true shortest path distance based on the triangle inequality. In addition, we propose a linear algorithm which computes the approximate shortest path between two nodes within the error bound. We perform extensive experimental evaluation on a large-scale road network and a social network and demonstrate the effectiveness and efficiency of our proposed methods. In this paper we study approximate landmark-based methods for point-to-point distance estimation in very large networks. These methods involve selecting a subset of nodes as landmarks and computing offline the distances from each node in the graph to those landmarks. At runtime, when the distance between a pair of nodes is needed, it can be estimated quickly by combining the precomputed distances. We prove that selecting the optimal set of landmarks is an NP-hard problem, and thus heuristic solutions need to be employed. We therefore explore theoretical insights to devise a variety of simple methods that scale well in very large networks. The efficiency of the suggested techniques is tested experimentally using five real-world graphs having millions of edges. While theoretical bounds support the claim that random landmarks work well in practice, our extensive experimentation shows that smart landmark selection can yield dramatically more accurate results: for a given target accuracy, our methods require as much as 250 times less space than selecting landmarks at random. In addition, we demonstrate that at a very small accuracy loss our techniques are several orders of magnitude faster than the state-of-the-art exact methods. Finally, we study an application of our methods to the task of social search in large graphs. A graph G is δ-hyperbolic if for any four vertices u,v,x,y of G the two larger of the three distance sums dG(u,v) + dG(x,y), dG(u,x) + dG(v,y), dG(u,y) + dG(v,x) differ by at most δ, and the smallest δ ≥ 0 for which G is δ-hyperbolic is called the hyperbolicity of G. In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of G can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of O(log2n) bits for bounded hyperbolicity graphs with n vertices such that distances can be approximated within an additive error of O(log n). The label length is optimal for every additive error up to ne. We also show a lower bound of Ω(log log n) on the approximation factor, namely every s-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires s = Ω(log log n). Through measurements, researchers continue to produce large social graphs that capture relationships, transactions, and social interactions between users. Efficient analysis of these graphs requires algorithms that scale well with graph size. We examine node distance computation, a critical primitive in graph problems such as computing node separation, centrality computation, mutual friend detection, and community detection. For large million-node social graphs, computing even a single shortest path using traditional breadth-first-search can take several seconds. In this paper, we propose a novel node distance estimation mechanism that effectively maps nodes in high dimensional graphs to positions in low-dimension Euclidean coordinate spaces, thus allowing constant time node distance computation. We describe Orion, a pro totype graph coordinate system, and explore critical decisions in its design. Finally, we evaluate the accuracy of Orion's node distance estimates, and show that it can produce accurate results in applications such as node separation, node centrality, and ranked social search. δ-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition: for any four points u,v,w,x, the two larger of the sums d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w) differ by at most 2δ. Given a finite set S of points of a δ-hyperbolic space, we present simple and fast methods for approximating the diameter of S with an additive error 2δ and computing an approximate radius and center of a smallest enclosing ball for S with an additive error 3δ. These algorithms run in linear time for classical hyperbolic spaces and for δ-hyperbolic graphs and networks. Furthermore, we show that for δ-hyperbolic graphs G=(V,E) with uniformly bounded degrees of vertices, the exact center of S can be computed in linear time O(|E|). We also provide a simple construction of distance approximating trees of δ-hyperbolic graphs G on n vertices with an additive error O(δlog2 n). This construction has an additive error comparable with that given by Gromov for n-point δ-hyperbolic spaces, but can be implemented in O(|E|) time (instead of O(n2)). Finally, we establish that several geometrical classes of graphs have bounded hyperbolicity.