Self-avoiding walks on scale-free networks

Abstract

Several kinds of walks on complex networks are currently used to analyze search and navigation in different systems. Many analytical and computational results are known for random walks on such networks. Self-avoiding walks (SAWs) are expected to be more suitable than unrestricted random walks to explore various kinds of real-life networks. Here we study long-range properties of random SAWs on scale-free networks, characterized by a degree distribution $P(k)\sim k^{-\gamma }$. In the limit of large networks (system size $N\to \infty$), the average number $s_n$ of SAWs starting from a generic site increases as ${\mu }^n$, with $\mu =<k^2>/<k>-1$. For finite $N$, $s_n$ is reduced due to the presence of loops in the network, which causes the emergence of attrition of the paths. For kinetic growth walks, the average maximum length, $<L>$, increases as a power of the system size: $<L>\sim N^{\alpha }$, with an exponent $\alpha$ increasing as the parameter $\gamma$ is raised. We discuss the dependence of $\alpha$ on the minimum allowed degree in the network. A similar power-law dependence is found for the mean self-intersection length of non-reversal random walks. Simulation results support our approximate analytical calculations.

9 pages, 7 figures

References in corpus (3)

• Efficient Immunization Strategies for Computer Networks and Populations
• Ising model in scale-free networks: A Monte Carlo simulation
• Random Walks on Complex Networks

Cited by in corpus (20)

• Cycles and clustering in bipartite networks
• Knowledge Acquisition: A Complex Networks Approach
• The Web of Connections between Tourism Companies in Elba: Structure and Dynamics
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• Biased diffusion on Japanese inter-firm trading network: Estimation of sales from network structure
• Kinetic growth walks on complex networks
• Self Avoiding Paths Routing Algorithm in Scale-Free Networks
• Diffusive capture processes for information search
• 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
• 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 Crowd Exploration of Large Networks: The Case of Causal Attribution
• Self-Avoiding Walk on Fractal Complex Networks: Exactly Solvable Cases
• Universal scaling in real dimension
• Intermittent exploration on a scale-free network
• Structural characterization of ice polymorphs from self-avoiding walks
• A decaying factor accounts for contained activity in neuronal networks with no need of hierarchical or modular organization
• Upper bounds for the connective constant of weighted self-avoiding walks