Kinetic growth walks on complex networks

Abstract

Kinetically grown self-avoiding walks on various types of generalized random networks have been studied. Networks with short- and long-tailed degree distributions $P(k)$ were considered ($k$, degree or connectivity), including scale-free networks with $P(k)\sim k^{-\gamma }$. The long-range behaviour of self-avoiding walks on random networks is found to be determined by finite-size effects. The mean self-intersection length of non-reversal random walks, $<l>$, scales as a power of the system size $N$: $<l>\sim N^{\beta }$, with an exponent $\beta =0.5$ for short-tailed degree distributions and $\beta <0.5$ for scale-free networks with $\gamma <3$. The mean attrition length of kinetic growth walks, $<L>$, scales as $<L>\sim N^{\alpha }$, with an exponent $\alpha$ which depends on the lowest degree in the network. Results of approximate probabilistic calculations are supported by those derived from simulations of various kinds of networks. The efficiency of kinetic growth walks to explore networks is largely reduced by inhomogeneity in the degree distribution, as happens for scale-free networks.

10 pages, 8 figures

References in corpus (3)

• Self-avoiding walks on scale-free networks
• Return times of random walk on generalized random graphs
• Random Walks on Complex Networks

Cited by in corpus (10)

• 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
• 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
• Self-avoiding walks and connective constants in clustered scale-free networks
• Non-Markovian random walks characterize network robustness to nonlocal cascades
• Analytical results for the distribution of first hitting times of random walks on random regular graphs
• 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