Europhys. Lett., 63 (1) , pp. 8-13 (2003)
Small worlds, mazes and random walksB. 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