December 23, 2004
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.
Similar papers 1
April 22, 2005
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 pow...
January 23, 2019
Various types of walks on complex networks have been used in recent years to model search and navigation in several kinds of systems, with particular emphasis on random walks. This gives valuable information on network properties, but self-avoiding walks (SAWs) may be more suitable than unrestricted random walks to study long-distance characteristics of complex systems. Here we study SAWs in clustered scale-free networks, characterized by a degree distribution of the form $P(...
November 15, 2004
We show how scale-free degree distributions can emerge naturally from growing networks by using random walks for selecting vertices for attachment. This result holds for several variants of the walk algorithm and for a wide range of parameters. The growth mechanism is based on using local graph information only, so this is a process of self-organisation. The standard mean-field equations are an excellent approximation for network growth using these rules. We discuss the effec...
January 4, 2007
Dynamical scalings for the end-to-end distance $R_{ee}$ and the number of distinct visited nodes $N_v$ of random walks (RWs) on finite scale-free networks (SFNs) are studied numerically. $\left< R_{ee} \right>$ shows the dynamical scaling behavior $\left<R_{ee}({\bar \ell},t)\right>= \bar{\ell}^\alpha (\gamma, N) g(t/\bar{\ell}^z)$, where $\bar{\ell}$ is the average minimum distance between all possible pairs of nodes in the network, $N$ is the number of nodes, $\gamma$ is th...
April 14, 2008
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 fi...
September 14, 2008
Various real-life networks exhibit degree correlations and heterogeneous structure, with the latter being characterized by power-law degree distribution $P(k)\sim k^{-\gamma}$, where the degree exponent $\gamma$ describes the extent of heterogeneity. In this paper, we study analytically the average path length (APL) of and random walks (RWs) on a family of deterministic networks, recursive scale-free trees (RSFTs), with negative degree correlations and various $\gamma \in (2,...
June 8, 2000
A model for growing networks is introduced, having as a main ingredient that new nodes are attached to the network through one existing node and then explore the network through the links of the visited nodes. From exact calculations of two limiting cases and numerical simulations the phase diagram of the model is obtained. In the stationary limit, large network sizes, a phase transition from a network with finite average connectivity to a network with a power law distributio...
May 16, 2009
We study the random walk problem on a class of deterministic Scale-Free networks displaying a degree sequence for hubs scaling as a power law with an exponent $\gamma=\log 3/\log2$. We find exact results concerning different first-passage phenomena and, in particular, we calculate the probability of first return to the main hub. These results allow to derive the exact analytic expression for the mean time to first reach the main hub, whose leading behavior is given by $\tau \...
June 13, 2003
Using both numerical simulations and scaling arguments, we study the behavior of a random walker on a one-dimensional small-world network. For the properties we study, we find that the random walk obeys a characteristic scaling form. These properties include the average number of distinct sites visited by the random walker, the mean-square displacement of the walker, and the distribution of first-return times. The scaling form has three characteristic time regimes. At short t...
March 21, 2016
We present an analytical and numerical study of the paths of self avoiding walks (SAWs) on random networks. Since these walks do not retrace their paths, they effectively delete the nodes they visit, together with their links, thus pruning the network. The walkers hop between neighboring nodes, until they reach a dead-end node from which they cannot proceed. Focusing on Erd\H{o}s-R\'enyi networks we show that the pruned networks maintain a Poisson degree distribution, $p_t(k)...