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
Pathlength scaling in graphs with incomplete navigational information
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
2011 (English)In: Physica A: Statistical Mechanics and its Applications, ISSN 0378-4371, E-ISSN 1873-2119, Vol. 390, no 21-22, 3996-4001 p.Article in journal (Refereed) Published
Abstract [en]

The graph-navigability problem concerns how one can find as short paths as possible between a pair of vertices, given an incomplete picture of a graph. We study the navigability of graphs where the vertices are tagged by a number (between 1 and the total number of vertices) in a way to aid navigation. This information is too little to ensure errorfree navigation but enough, as we will show, for the agents to do significantly better than a random walk. In our setup, given a graph, we first assign information to the vertices that agents can utilize for their navigation. To evaluate the navigation, we calculate the average distance traveled over random pairs of source and target and different graph realizations. We show that this type of embedding can be made quite efficiently; the more information is embedded, the more efficient it gets. We also investigate the embedded navigational information in a standard graph layout algorithm and find that although this information does not make algorithms as efficient as the above-mentioned schemes, it is significantly helpful.

Place, publisher, year, edition, pages
Amsterdam: North-Holland , 2011. Vol. 390, no 21-22, 3996-4001 p.
Keyword [en]
Graph routing, Geometric routing, Navigability
National Category
Physical Sciences
Identifiers
URN: urn:nbn:se:umu:diva-45960DOI: 10.1016/j.physa.2011.06.021OAI: oai:DiVA.org:umu-45960DiVA: diva2:436580
Funder
Swedish Research Council, 621-2009-3536
Available from: 2011-08-24 Created: 2011-08-24 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

fulltext(2183 kB)156 downloads
File information
File name FULLTEXT02.pdfFile size 2183 kBChecksum SHA-512
d5b5b6a50cec0fcd5d56bb81b188123dd246159a606e55d97bbce585b56342a51512157817c40af54f491f124f56c603ce5f580aa0e1ccfeafa153f796f6f0e7
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
Physica A: Statistical Mechanics and its Applications
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 156 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: 48 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