Metric embedding, hyperbolic space, and social networks

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

30 Citations (Scopus)
31 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 O(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 d-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 - &epsis;) 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
Title of host publication30th Annual Symposium on Computational Geometry (SOCG'14), Kyoto, Japan, June 8-11, 2014
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages501-510
ISBN (Print)978-1-4503-2594-3
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event30th Annual Symposium on Computational Geometry (SoCG 2014) - Kyoto, Japan
Duration: 8 Jun 201411 Jun 2014
Conference number: 30

Conference

Conference30th Annual Symposium on Computational Geometry (SoCG 2014)
Abbreviated titleSoCG '14
Country/TerritoryJapan
CityKyoto
Period8/06/1411/06/14

Fingerprint

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

Cite this