Self-avoiding walks and connective constants in small-world networks

Abstract

Long-distance characteristics of small-world networks have been studied by means of self-avoiding walks (SAW's). We consider networks generated by rewiring links in one- and two-dimensional regular lattices. The number of SAW's $u_n$ was obtained from numerical simulations as a function of the number of steps $n$ on the considered networks. The so-called connective constant, $\mu ={\lim }_{n\to \infty }{u}_n/u_{n-1}$, which characterizes the long-distance behavior of the walks, increases continuously with disorder strength (or rewiring probability, $p$). For small $p$, one has a linear relation $\mu ={\mu }_0+ap$, ${\mu }_0$ and $a$ being constants dependent on the underlying lattice. Close to $p=1$ one finds the behavior expected for random graphs. An analytical approach is given to account for the results derived from numerical simulations. Both methods yield results agreeing with each other for small $p$, and differ for $p$ close to 1, because of the different connectivity distributions resulting in both cases.

7 pages, 5 figures

References in corpus (20)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Efficient Behavior of Small-World Networks
• The diameter of the world wide web
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Scaling and percolation in the small-world network model
• Epidemics and percolation in small-world networks
• Fast Response and Temporal Coding on Coherent Oscillations in Small-World Networks
• Small world effect in an epidemiological model
• Small-world networks: Evidence for a crossover picture
• Ising model in small-world networks
• Percolation and epidemics in a two-dimensional small world
• XY model in small-world networks
• Small-World Networks: Links with long-tailed distributions
• Erratum: Small-world networks: Evidence for a crossover picture
• Relaxation Properties of Small-World Networks
• Random spread on the family of small-world networks
• First-order transition in small-world networks
• Scaling of random spreading in small world networks

Cited by in corpus (20)

• Knowledge Acquisition: A Complex Networks Approach
• Self-avoiding walks on scale-free networks
• Evolving small-world networks with geographical attachment preference
• Configurational entropy of hydrogen-disordered ice polymorphs
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• Antiferromagnetic Ising model in small-world networks
• Kinetic growth walks on complex networks
• A scale-free network hidden in the collapsing polymer
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Kinetic-growth self-avoiding walks on small-world networks
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Analytical results for the distribution of first hitting times of random walks on random regular graphs
• 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
• Self-Avoiding Walk on Fractal Complex Networks: Exactly Solvable Cases
• Efficient network exploration by means of resetting self-avoiding random walkers
• Universal scaling in real dimension
• Structural characterization of ice polymorphs from self-avoiding walks