Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2008-09-17
Phys. Rev. Lett. 102, 058701 (2009)
Physics
Condensed Matter
Disordered Systems and Neural Networks
4 pages, 2 figures
Scientific paper
10.1103/PhysRevLett.102.058701
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.
Boguñá Marián
Krioukov Dmitri
No associations
LandOfFree
Navigating ultrasmall worlds in ultrashort time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Navigating ultrasmall worlds in ultrashort time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Navigating ultrasmall worlds in ultrashort time will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-279984