Hyperbolic Cosmograms are Go

CAIDA is the Cooperative Association for Internet Data Analysis based at UCSD, and for many years a tremendous resource in the deeply fascinating world of internet cartography. We recently attended a lecture by CAIDA’s Dmitri Krioukov whose paper, “Sustaining the Future of the Internet with Hyperbolic Mapping” has been influential well outside presumed disciplinary partitions.

The abstract captures some of what is at stake in this novel approach to conceiving internet territoriality.

The famous image from this work shows how hyperbolic geometry becomes an active geography, and supports the thesis that by seeding packets with a sense of direction that inefficiencies of Euclidean routing can be remapped. It also provides a convincing cosmogram of this particular polis and its attendant geodesic imaginary.

“We establish a connection between the scale-free topology of complex networks, and the hyperbolic geometry of hidden metric spaces underlying these networks. Given a hyperbolic space, networks topologies with scale-free degree distributions and strong clustering naturally emerge on top of the space as topological reflections of its hyperbolic geometry. Conversely, for any scale-free network with strong clustering, there is an effective hyperbolic space underlying the network. The underlying hyperbolic geometry enables greedy routing with optimal efficiency. Greedy routing does not require any global information about network topology to navigate the network. At each hop, greedy routing selects as the next hop the current hop’s neighbor closest to the destination in the underlying hyperbolic space. We show that in complex networks mapped to their hyperbolic spaces, greedy routing always succeeds reaching the destination, following the topologically shortest paths. Furthermore, we show that even without re-mapping the network or changing any node coordinates, this navigation efficiency is remarkably robust with respect to rapid network dynamics, and catastrophic levels of network damage. We map the real Internet AS-level topology to its hyperbolic space, and find that greedy routing using this map exhibits similar efficiency. These results effectively deliver a solution for Internet routing with theoretically best possible scaling properties. Not only routing table sizes and lengths of routing paths are as small as possible, but also routing communication overhead is reduced to zero.”

See also Sustaining the Future of the Internet with Hyperbolic Mapping at Internet Globalization News.

Tags: · · · · ·