Carregant...
Fitxers
Tipus de document
ArticleVersió
Versió publicadaData de publicació
Tots els drets reservats
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/140070
Navigating Ultrasmall Worlds in Ultrashort Time
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
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.
Matèries (anglès)
Citació
Citació
BOGUÑÁ, Marián, KRIOUKOV, Dmitri. Navigating Ultrasmall Worlds in Ultrashort Time. _Physical Review Letters_. 2009. Vol. 102, núm. 5, pàgs. 058701. [consulta: 21 de gener de 2026]. ISSN: 0031-9007. [Disponible a: https://hdl.handle.net/2445/140070]