Issue
EPL
Volume 87, Number 5, September 2009
Article Number 58004
Number of page(s) 6
Section Interdisciplinary Physics and Related Areas of Science and Technology
DOI http://dx.doi.org/10.1209/0295-5075/87/58004
Published online 24 September 2009
EPL, 87 (2009) 58004
DOI: 10.1209/0295-5075/87/58004

Learning paths in complex networks

D. O. Cajueiro1, 2 and R. F. S. Andrade3, 2

1   Department of Economics, Universidade de Brasília - Campus Darcy Ribeiro, Prédio da FACE, Asa Norte, 70910-900 Brasília, Brazil
2   National Institute of Science and Technology for Complex Systems
3   Instituto de Física, Universidade Federal da Bahia - 40210-340 Salvador, Brazil

danielcajueiro@gmail.com
randrade@ufba.br

received 24 May 2009; accepted in final form 1 September 2009; published September 2009
published online 24 September 2009

Abstract
This letter addresses the issue of learning shortest paths in complex networks, which is of utmost importance in real-life navigation. The approach has been partially motivated by recent progress in characterizing navigation problems in networks, having as extreme situations the completely ignorant (random) walker and the rich directed walker, which can pay for information that will guide to the target node along the shortest path. A learning framework based on a first-visit Monte Carlo algorithm is implemented, together with four independent measures that characterize the learning process. The methodology is applied to a number of network classes, as well as to networks constructed from actual data. The results indicate that the navigation difficulty and learning velocity are strongly related to the network topology.

PACS
89.75.Hc - Networks and genealogical trees.
02.70.Uu - Applications of Monte Carlo methods.
89.75.Fb - Structures and organization in complex systems.

© EPLA 2009