Self-avoiding walks on scale-free networks

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, ...

It was discovered a few years ago that many networks in the real world exhibit self-similarity. A lot of researches on the structures and processes on real and artificial fractal complex networks have been done, drawing an analogy to critical phenomena. However, the non-Markovian dynamics on fractal networks has not been understood well yet. We here study the self-avoiding walk on complex fractal networks through the mapping of the self-avoiding walk to the n-vector model by ...

Random walks on discrete lattices are fundamental models that form the basis for our understanding of transport and diffusion processes. For a single random walker on complex networks, many properties such as the mean first passage time and cover time are known. However, many recent applications such as search engines and recommender systems involve multiple random walkers on complex networks. In this work, based on numerical simulations, we show that the fraction of nodes of...

We investigate the dynamic scaling properties of stochastic particle systems on a non-deterministic scale-free network. It has been known that the dynamic scaling behavior depends on the degree distribution exponent of the underlying scale-free network. Our study shows that it also depends on the global structure of the underlying network. In random walks on the tree structure scale-free network, we find that the relaxation time follows a power-law scaling $\tau\sim N$ with t...

In this study we have carried out computer simulations of random walks on Watts-Strogatz-type small world networks and measured the mean number of visited sites and the return probabilities. These quantities were found to obey scaling behavior with intuitively reasoned exponents as long as the probability $p$ of having a long range bond was sufficiently low.

We study diffusion (random walks) on recursive scale-free graphs, and contrast the results to similar studies in other analytically soluble media. This allows us to identify ways in which diffusion in scale-free graphs is special. Most notably, scale-free architecture results in a faster transit time between existing nodes, when the network grows in size; and walks emanating from the most connected nodes are recurrent, despite the network's infinite dimension. We also find th...

We study a simple model in which the growth of a network is determined by the location of one or more random walkers. Depending on walker speed, the model generates a spectrum of structures situated between well-known limiting cases. We demonstrate that the average degree observed by a walker is related to the global variance. Modulating the extent to which the location of node attachment is determined by the walker as opposed to random selection is akin to scaling the speed ...

We study an intermittent random walk on a random network of scale-free degree distribution. The walk is a combination of simple random walks of duration $t_w$ and random long-range jumps. While the time the walker needs to cover all the nodes increases with $t_w$, the corresponding time for the edges displays a non monotonic behavior with a minimum for some nontrivial value of $t_w$. This is a heterogeneity-induced effect that is not observed in homogeneous small-world networ...

We study the mean length $\ell(k)$ of the shortest paths between a vertex of degree $k$ and other vertices in growing networks, where correlations are essential. In a number of deterministic scale-free networks we observe a power-law correction to a logarithmic dependence, $\ell(k) = A\ln [N/k^{(\gamma-1)/2}] - C k^{\gamma-1}/N + ...$ in a wide range of network sizes. Here $N$ is the number of vertices in the network, $\gamma$ is the degree distribution exponent, and the coef...

In this work we investigate the dynamics of random walk processes on scale-free networks in a short to moderate time scale. We perform extensive simulations for the calculation of the mean squared displacement, the network coverage and the survival probability on a network with a concentration $c$ of static traps. We show that the random walkers remain close to their origin, but cover a large part of the network at the same time. This behavior is markedly different than usual...