Kinetic-growth self-avoiding walks on small-world networks

Abstract

Kinetically-grown self-avoiding walks have been studied on Watts-Strogatz small-world networks, rewired from a two-dimensional square lattice. The maximum length L of this kind of walks is limited in regular lattices by an attrition effect, which gives finite values for its mean value < L >. For random networks, this mean attrition length < L > scales as a power of the network size, and diverges in the thermodynamic limit (large system size N). For small-world networks, we find a behavior that interpolates between those corresponding to regular lattices and randon networks, for rewiring probability p ranging from 0 to 1. For p < 1, the mean self-intersection and attrition length of kinetically-grown walks are finite. For p = 1, < L > grows with system size as N^{1/2}, diverging in the thermodynamic limit. In this limit and close to p = 1, the mean attrition length diverges as (1-p)^{-4}. Results of approximate probabilistic calculations agree well with those derived from numerical simulations.

10 pages, 7 figures

References in corpus (23)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Efficient Behavior of Small-World Networks
• The diameter of the world wide web
• Network robustness and fragility: Percolation on random graphs
• Scaling and percolation in the small-world network model
• Search in Power-Law Networks
• Identity and Search in Social Networks
• Epidemics and percolation in small-world networks
• Optimal network topologies for local search with congestion
• Fast Response and Temporal Coding on Coherent Oscillations in Small-World Networks
• Small world effect in an epidemiological model
• Mean-field solution of the small-world network model
• Path finding strategies in scale-free networks
• Ising model in small-world networks
• Small-World Networks: Links with long-tailed distributions
• Random spread on the family of small-world networks
• Self-avoiding walks on scale-free networks
• Adaptive Random Walks on the Class of Web Graph
• Scaling of random spreading in small world networks
• Self-avoiding walks and connective constants in small-world networks
• Kinetic growth walks on complex networks

Cited by in corpus (8)

• Antiferromagnetic Ising model in small-world networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• Zero-temperature Glauber dynamics on small-world networks
• Self-avoiding walks and connective constants in clustered scale-free networks
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
• Efficient network exploration by means of resetting self-avoiding random walkers