Metric Embedding, Hyperbolic Space, and Social Networks

ABSTRACT

We consider the problem of embedding an undirected graph into hyperbolic space with minimum distortion. A fundamental problem in its own right, it has also drawn a great deal of interest from applied communities interested in empirical analysis of large-scale graphs. In this paper, we establish a connection between distortion and quasi-cyclicity of graphs, and use it to derive lower and upper bounds on metric distortion. Two particularly simple and natural graphs with large quasi-cyclicity are n-node cycles and n × n square lattices, and our lower bound shows that any hyperbolic-space embedding of these graphs incurs a multiplicative distortion of at least Ω(n/log n). This is in sharp contrast to Euclidean space, where both of these graphs can be embedded with only constant multiplicative distortion. We also establish a relation between quasi-cyclicity and δ-hyperbolicity of a graph as a way to prove upper bounds on the distortion. Using this relation, we show that graphs with small quasi-cyclicity can be embedded into hyperbolic space with only constant additive distortion. Finally, we also present an efficient (linear-time) randomized algorithm for embedding a graph with small quasi-cyclicity into hyperbolic space, so that with high probability at least a (1 − ϵ) fraction of the node-pairs has only constant additive distortion. Our results also give a plausible theoretical explanation for why social networks have been observed to embed well into hyperbolic space: they tend to have small quasi-cyclicity.

References

1. P. Assouad. Plongements lipschitziens dans Rn. Bulletin de la Société Mathématique de France, 111:429--448, 1983.
2. M. Bonk and O. Schramm. Embeddings of Gromov hyperbolic spaces. Geometric & Functional Analysis, 10(2):266--306, 2000.
3. V. Chepoi, F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of Δ-hyperbolic geodesic spaces and graphs. In Proc. 24th Annual Symposium on Computational Geometry (SoCG '08), pp. 59--68, 2008.
4. J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485--497, 2004.
5. E. Ghys and P. de la Harpe (eds.). Sur les groupes Hyperboliques d'après Mikhael Gromov, volume 83 of Progress in Mathematics. Birkhäuser, Boston, 1990.
6. M. Gromov. Hyperbolic groups. Mathematical Sciences Research Institute Publications, Springer, 8:75--263, 1987.
7. W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
8. R. Kleinberg. Geographic routing using hyperbolic space. In Proc. 26th INFOCOM, pp. 1902--1909, 2007.
9. J. Kleinberg, A. Slivkins, and T. Wexler. Triangulation and embedding using small sets of beacons. Journal of the ACM, 56(6):32, 2009.
10. B. Knaster, C. Kuratowski, and S. Mazurkiewicz. Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe. Fundamenta Mathematicae, 14:132--137, 1929.
11. R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 119--132, 2006.
12. D. Krioukov, F. Papadopoulos, A. Vahdat, and M. Boguna. Curvature and temperature of complex networks. Physical Review E, 80(3):035101(R), 2009.
13. J. Matoušek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., 2002.
14. F. Papadopoulos, D. V. Krioukov, M. Boguñá, and A. Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In Proc. 29th INFOCOM, pp. 2973--2981, 2010.
15. Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete & Computational Geometry, 19(1):79--94, 1998.
16. R. Sarkar. Low distortion Delaunay embedding of trees in hyperbolic plane. In Proc. 19th International Symposium on Graph Drawing, pp. 355--366, 2012.
17. Y. Shavitt and T. Tankel. Big-bang simulation for embedding network distances in Euclidean space. ACM Trans. on Networking, 12(6):993--1006, 2004.
18. Y. Shavitt and T. Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. ACM Trans. on Networking, 16(1):25--36, 2008.
19. X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao. Orion: shortest path estimation for large social graphs. In Proc. 3rd Workshop on Online Social Networks, pp. 9--9, 2010.
20. X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao. Efficient shortest paths on massive social graphs. In Proc. 7th International Conference on Collaborative Computing, pp. 77--86, 2011.

• Theory of computation