Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exploring maps with greedy navigators
Umeå University, Faculty of Science and Technology, Department of Physics. (IceLab)
Umeå University, Faculty of Science and Technology, Department of Physics. (IceLab)ORCID iD: 0000-0003-2156-1096
2012 (English)In: Physical Review Letters, ISSN 0031-9007, E-ISSN 1079-7114, Vol. 108, no 12, 8701- p.Article in journal (Refereed) Published
Abstract [en]

During the last decade of network research focusing on structural and dynamical properties of networks, the role of network users has been more or less underestimated from the bird’s-eye view of global perspective. In this era of global positioning system equipped smartphones, however, a user’s ability to access local geometric information and find efficient pathways on networks plays a crucial role, rather than the globally optimal pathways. We present a simple greedy spatial navigation strategy as a probe to explore spatial networks. These greedy navigators use directional information in every move they take, without being trapped in a dead end based on their memory about previous routes. We suggest that the centralities measures have to be modified to incorporate the navigators’ behavior, and present the intriguing effect of navigators’ greediness where removing some edges may actually enhance the routing efficiency, which is reminiscent of Braess’s paradox. In addition, using samples of road structures in large cities around the world, it is shown that the navigability measure we define reflects unique structural properties, which are not easy to predict from other topological characteristics. In this respect, we believe that our routing scheme significantly moves the routing problem on networks one step closer to reality, incorporating the inevitable incompleteness of navigators’ information.

Place, publisher, year, edition, pages
2012. Vol. 108, no 12, 8701- p.
National Category
Other Physics Topics
Identifiers
URN: urn:nbn:se:umu:diva-53354DOI: 10.1103/PhysRevLett.108.128701OAI: oai:DiVA.org:umu-53354DiVA: diva2:511664
Available from: 2012-03-22 Created: 2012-03-22 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

fulltext(2705 kB)157 downloads
File information
File name FULLTEXT03.pdfFile size 2705 kBChecksum SHA-512
3bfa374b40b4af3d90f32a047b14c45d63b89fdccc131adc612a1e84d1230b0639499e2bfcfeec47196be825c97bd3604bae494f217787c5012275fab46bf6da
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lee, Sang HoonHolme, Petter
By organisation
Department of Physics
In the same journal
Physical Review Letters
Other Physics Topics

Search outside of DiVA

GoogleGoogle Scholar
Total: 157 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 71 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf