Navigating Ultrasmall Worlds in Ultrashort Time
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...
| Authors: | ; |
|---|---|
| Format: | Article |
| Status: | Published version |
| Publication date: | 2009 |
| Country: | España |
| Institution: | Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya) |
| Repository: | Recercat. Dipósit de la Recerca de Catalunya |
| OAI Identifier: | oai:recercat.cat:2445/140070 |
| Online Access: | https://hdl.handle.net/2445/140070 |
| Access Level: | Open access |
| Keyword: | Xarxes d'àrea extensa (Xarxes d'ordinadors) Wide area networks (Computer networks) |
| _version_ | 1878733025571766272 |
|---|---|
| author | Boguñá, Marián |
| author2 | Krioukov, Dmitri |
| author2_role | author |
| author_browse | Boguñá, Marián Krioukov, Dmitri |
| author_facet | Boguñá, Marián Krioukov, Dmitri |
| author_role | author |
| collection | Recercat. Dipósit de la Recerca de Catalunya |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | ES_4e983cde8269c57ed4882d5dfd52bb39 |
| institution | Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya) |
| instname_str | Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya) |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:recercat.cat:2445/140070 |
| publishDate | 2009 |
| publishDateSort | 2009 |
| publisher | American Physical Society |
| publisherStr | American Physical Society |
| reponame_str | Recercat. Dipósit de la Recerca de Catalunya |
| spelling | Navigating Ultrasmall Worlds in Ultrashort Time Boguñá, Marián Krioukov, Dmitri Xarxes d'àrea extensa (Xarxes d'ordinadors) Wide area networks (Computer networks) 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. American Physical Society https://hdl.handle.net/2445/140070 |
| spellingShingle | Navigating Ultrasmall Worlds in Ultrashort Time Boguñá, Marián Xarxes d'àrea extensa (Xarxes d'ordinadors) Wide area networks (Computer networks) |
| status_str | publishedVersion |
| title | Navigating Ultrasmall Worlds in Ultrashort Time |
| title_full | Navigating Ultrasmall Worlds in Ultrashort Time |
| title_fullStr | Navigating Ultrasmall Worlds in Ultrashort Time |
| title_full_unstemmed | Navigating Ultrasmall Worlds in Ultrashort Time |
| title_short | Navigating Ultrasmall Worlds in Ultrashort Time |
| title_sort | Navigating Ultrasmall Worlds in Ultrashort Time |
| topic | Xarxes d'àrea extensa (Xarxes d'ordinadors) Wide area networks (Computer networks) |
| topic_facet | Xarxes d'àrea extensa (Xarxes d'ordinadors) Wide area networks (Computer networks) |
| url | https://hdl.handle.net/2445/140070 |