Efficient Navigation in Scale-Free Newtorks Embedded in Hyperbolic Metric Spaces

Efficient Navigation in Scale-Free Newtorks Embedded in Hyperbolic Metric Spaces, Dmitri Krioukov, Fragkiskos Papadopoulos, Marian Boguna, Amin Vahdat, Arxiv:0805.1266v1, May 2008.

Some related version was submitted to a SIGMETRICS workshop.

This paper shows that you can create some random topologies using some simple rules in hyperbolic graphs such that these graphs exhibit similar properties than Internet AS topologies (clustering properties, triangles, node degrees).

Within the hyperbolic space with the associated distance, the paper observes that greedy routing work pretty near optimal (where optimal is shortest path) for these topologies. It thus conjectures that, if one could map the Internet AS topology to a hidden hyperbolic topology, one could use this topology to do routing relatively efficiently.

This is very cute, and indeed if you could identify an underlying hidden metric space under the graph topology, that'd be great. A few thoughts quickly come to mind though: first, shortest path is not what's happening in between ASes anyway, so there's another step to take right there. Another thought is that, hyperbolic topology have an inherent scalability issue: because you can cram more points within the space (it's "larger" in some sense), then you have to use more bits to describe each point. An example: in Euclidean geometry, I can put n points equally spaced and use log(n) bits to describe each position. In hyperbolic geometry, I would need n bits to describe each position, since they would be at 1/k^n for them to be equidistant. So I can put infinitely many of them on (0,1], but with O(n) bits for each position. So greedy routing does simplify to some extent, but since O(n) bits gives me shortest path routing in Euclidean space, there's no benefit from that perspective.

Another question is this: some properties are similar in the AS-topology, and in the hyperbolic generated graph. But to what extent the graphs are truly isomorphic? Li, Alderson, Tanaka, Doyle, Willinger have this paper where they confront analysis based on this kind of high level similarities, which could lead to drastically different conclusions. So proceed with caution, it's a treacherous path. But if it leads somewhere, it could have dramatic impact.