Deterministic walks in random networks: an application to thesaurus graphs

KINOUCHI, OSAME; MARTINEZ, ALEXANDRE S.; LIMA, GILSON F.; LOURENCO, G. M.; RISAU GUSMAN, SEBASTIAN

PHYSICA A - STATISTICAL AND THEORETICAL PHYSICS

Elsevier

Lugar: Amsterdam; Año: 2002 vol. 3153 p. 665 - 676

0378-4371

In a landscape composed of N randomly distributed sites in Euclidean space, a walker ("tourist") goes to the nearest one that has not been visited in the last $\tau$ steps. This procedure leads to trajectories composed of a transient part and a final cyclic attractor of period $p$. The tourist walk presents a simple scaling with respect to $\tau$ and can be performed in a wide range of networks that can be viewed as ordinal neighborhood graphs. As an example, we show that graphs defined by thesaurus dictionaries share some of the statistical properties of low-dimensional (d=2) Euclidean graphs and are easily distinguished from random link networks which correspond to the $d \rightarrow \infty$ limit. This approach furnishes complementary information to the usual clustering coefficient and mean minimum separation length.