  Random scale-free networks are ultrasmall worlds. The average length of the
shortest paths in networks of size N scales as lnlnN. Here we show that these
ultrasmall worlds can be navigated in ultrashort time. Greedy routing on
scale-free networks embedded in metric spaces finds paths with the average
length scaling also as lnlnN. Greedy routing uses only local information to
navigate a network. Nevertheless, it finds asymptotically the shortest paths, a
direct computation of which requires global topology knowledge. Our findings
imply that the peculiar structure of complex networks ensures that the lack of
global topological awareness has asymptotically no impact on the length of
communication paths. These results have important consequences for
communication systems such as the Internet, where maintaining knowledge of
current topology is a major scalability bottleneck.

Disordered Systems and Neural Networks;Networking and Internet Architecture;Physics and Society