Europhys. Lett.
Volume 63, Number 1, July 2003
Page(s) 8 - 13
Section General
Published online 01 June 2003
DOI: 10.1209/epl/i2003-00470-4
Europhys. Lett., 63 (1) , pp. 8-13 (2003)

Small worlds, mazes and random walks

B. Luque1 and O. Miramontes2

1  Departamento Matemática Aplicada y Estadística Escuela Superior de Ingenieros Aeronáuticos, Universidad Politécnica de Madrid Plaza Cardenal Cisneros 3, Madrid 28040, Spain
2  Departamento de Sistemas Complejos, Instituto de Física Universidad Nacional Autónoma de México, Cd Universitaria México 01000 DF, México

(Received 23 December 2002; accepted in final form 2 May 2003)

A parametrized family of random walks whose trajectories are easily identified as graphs is presented. This construction shows small-world-like behavior but, interestingly, a power law emerges between the minimal distance L and the number of nodes N of the graph instead of the typical logarithmic scaling. We explain this peculiar finding in the light of the well-known scaling relationships in Random Walk Theory. Our model establishes a link between Complex Networks and Self-Avoiding Random Walks, a useful theoretical framework in polymer science.

05.40.Fb - Random walks and Levy flights.
02.50.-r - Probability theory, stochastic processes, and statistics.
02.70.Uu - Applications of Monte Carlo methods.

© EDP Sciences 2003