Please use this identifier to cite or link to this item:
Title: Navigating Ultrasmall Worlds in Ultrashort Time
Author: Boguñá, Marián
Krioukov, Dmitri
Keywords: Xarxes d'àrea extensa (Xarxes d'ordinadors)
Wide area networks (Computer networks)
Issue Date: 3-Feb-2009
Publisher: American Physical Society
Abstract: Random scale-free networks are ultrasmall worlds. The average length of the shortest paths in networks of size N scales as ln  ln  N . 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 ln  ln  N . 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.
Note: Reproducció del document publicat a:
It is part of: Physical Review Letters, 2009, vol. 102, num. 5, p. 058701
Related resource:
ISSN: 0031-9007
Appears in Collections:Articles publicats en revistes (Física de la Matèria Condensada)

Files in This Item:
File Description SizeFormat 
567157.pdf261.26 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.