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) ,

$\endgroup$
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"
$\endgroup$
  • $\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$ – Anirbit Aug 26 '15 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$ – Anirbit Aug 26 '15 at 20:48
  • $\begingroup$ Every CAT(k) space with $k < 0$ is $\delta$-hyperbolic... $\endgroup$ – Suvrit Aug 26 '15 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.