Deterministic walks in random networks: An application to thesaurus graphs

DOI10.1016/S0378-4371(02)00972-XMaRDI QIDQ1848192zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 19 November 2002

Published in Physica A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0110217

zbMATH Keywords

final cyclic attractorrandomly distributed Euclidean-space sitestrajectories

Mathematics Subject Classification ID

Processes in random environments (60K37)

Abstract: 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 au steps. This procedure leads to trajectories composed of a transient part and a final cyclic attractor of period p. The tourist walk presents universal aspects with respect to au and can be done 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 graphs. This approach furnishes complementary information to the usual clustering coefficient and mean minimum separation length.

Recommendations

• Random walks and diffusions on graphs and databases. An introduction.
• Random walks on graphs: ideas, techniques and results
• scientific article; zbMATH DE number 1107737
• Random walks and diffusion on networks
• The average number of distinct sites visited by a random walker on random graphs

Cites work

• Collective dynamics of `small-world' networks
• Exploring complex networks
• Further travels with my ant
• Reflexive Nearest Neighbours
• Relaxation, closing probabilities and transition from oscillatory to chaotic attractors in asymmetric neural networks
• The stochastic traveling salesman problem: finite size scaling and the cavity prediction

Cited in

(5)

• Complex networks: structure and dynamics
• Texture analysis and classification using deterministic tourist walk
• Complex network classification using partially self-avoiding deterministic walks
• Topological structure of dictionary graphs
• Accessibility in complex networks

This page was built for publication: Deterministic walks in random networks: An application to thesaurus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1848192)