Hyperbolic Embeddings for Near-Optimal Greedy Routing

摘要

Greedy routing computes paths between nodes in a network by successively moving to the neighbor closestto the target with respect to coordinates given by an embedding into some metric space. Its advantage is thatonly local information is used for routing decisions. We present different algorithms for generating graphembeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddingsguarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths ofthe resulting greedy paths.We evaluate our algorithm on multiple generated and real-world networks. For networks that are generallyassumed to have a hidden underlying hyperbolic geometry, such as the Internet graph [3], we achievenear-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortestpaths). In the case of the Internet graph, they are only 6% longer when using our best algorithm, whichgreatly improves upon the previous best known embedding, whose creation required substantial manualintervention.In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of thecoordinates of the resulting embeddings and observe how it impacts the success rate when coordinates arenot represented with very high precision. Since numerical difficulties are a major issue when performingcomputations in the hyperbolic plane, we consider variations of our algorithm that improve the success ratewhen using coordinates with lower precision.