Routing in the Internet and Navigability of Scale-Free Networks

The Internet has become an integral part of the ubiquitous
information infrastructure of the modern society. But its global
scale comes with a price: to route information packets from a given
source to a given destination, routers maintain and constantly
update an almost full view of the global network topology. This
maintenance involves immense computation and information processing
overhead, and has recently been widely recognized as one of the
biggest scalability problems in the Internet.

In this talk we focus on the question if routing (or targeted
information propagation) can be efficient in the Internet and
networks alike without any global knowledge of the network topology.
In other words we are interested if the Internet and other complex
networks are navigable -- we say that a network is navigable if some
simple routing strategies based only on local information available
to a node are efficient. Such local information can be nodes'
coordinates in some hidden metric spaces, and then nodes can route
"greedily" by forwarding information to their neighbors closest to
the destination in the hidden space. We show that if these spaces
are hyperbolic, then networks built upon them naturally acquire
scale-free node degree distributions and strong clustering. The
topology of these networks are thus surprisingly similar to the
topologies of real networks, including the Internet. Moreover, their
navigability properties are essentially best possible: almost all
greedy routes reach their destinations and follow the shortest paths
in the network.