4
$\begingroup$

Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)

I don't know what is a good definition of a ``good" embedding is! May be my rough intuition is that there should be minimum distortion of the shortest path metric on the graph. I am open to knowing if there are other definitions which are also considered in literature.

Two related MO discussions (for which I don't see hyperbolic counterparts) ,

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Have a look at the following for a start:

  1. Quantifying tree like structure in complex networks
  2. On the Hyperbolicity of Small-World and Tree-Like Random Graphs
  3. Geographic Routing Using Hyperbolic Space
  4. This webpage on "Embedding Networks in Hyperbolic Space"
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks! Let me see them. What would be a good reason for say complexity theorists to try embedding a graph into a hyperbolic space? $\endgroup$
    – Student
    Commented Aug 26, 2015 at 1:45
  • $\begingroup$ Many of these references talk of the ``$\delta$-Gromov hyperbolic" space. Can you explain why is that related to the usual $\mathbb{H}_n$? $\endgroup$
    – Student
    Commented Aug 26, 2015 at 20:48
  • 1
    $\begingroup$ Every CAT(k) space with $k < 0$ is $\delta$-hyperbolic... $\endgroup$
    – Suvrit
    Commented Aug 26, 2015 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .