Metric embedding, hyperbolic space, and social networks

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
71 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalComputational Geometry
Volume59
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

  • Delta-hyperbolicity
  • Hyperbolic space
  • Metric embedding
  • Quasi-cyclicity
  • Social networks

Fingerprint

Dive into the research topics of 'Metric embedding, hyperbolic space, and social networks'. Together they form a unique fingerprint.

Cite this