Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:umu:diva-45960DOI: 10.1016/j.physa.2011.06.021OAI: diva2:436580
Swedish Research Council, 621-2009-3536
Available from: 2011-08-24 Created: 2011-08-24 Last updated: 2013-09-06Bibliographically approved

Open Access in DiVA

fulltext(2183 kB)125 downloads
File information
File name FULLTEXT02.pdfFile size 2183 kBChecksum SHA-512
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: 125 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

Altmetric score

Total: 32 hits
ReferencesLink to record
Permanent link

Direct link