Random walk and Pair-Annihilation Processes on Scale-Free Networks

The scale-free (SF) networks that have been studied so far contained quenched disorder generated by random dilution which does not vary with the time. In practice, if a SF network is to represent, for example, the worldwide web, then the links between its various nodes may temporarily be lost, and re-established again later on. This gives rise to SF networks with annealed disorder. Even if the disorder is quenched, it may be more realistic to generate it by a dynamical proces...

We study a random walk problem on the hierarchical network which is a scale-free network grown deterministically. The random walk problem is mapped onto a dynamical Ising spin chain system in one dimension with a nonlocal spin update rule, which allows an analytic approach. We show analytically that the characteristic relaxation time scale grows algebraically with the total number of nodes $N$ as $T \sim N^z$. From a scaling argument, we also show the power-law decay of the a...

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

Random networks with complex topology are common in Nature, describing systems as diverse as the world wide web or social and business networks. Recently, it has been demonstrated that most large networks for which topological information is available display scale-free features. Here we study the scaling properties of the recently introduced scale-free model, that can account for the observed power-law distribution of the connectivities. We develop a mean-field method to pre...

We study a zero range process on scale-free networks in order to investigate how network structure influences particle dynamics. The zero range process is defined with the particle jumping rate function $p(n)=n^\delta$. We show analytically that a complete condensation occurs when $\delta \leq \delta_c \equiv 1/(\gamma-1)$ where $\gamma$ is the degree distribution exponent of the underlying networks. In the complete condensation, those nodes whose degree is higher than a thre...

The concept of scale-free networks has been widely applied across natural and physical sciences. Many claims are made about the properties of these networks, even though the concept of scale-free is often vaguely defined. We present tools and procedures to analyse the statistical properties of networks defined by arbitrary degree distributions and other constraints. Doing so reveals the highly likely properties, and some unrecognised richness, of scale-free networks, and cast...

It is known that the heterogeneity of scale-free networks helps enhancing the efficiency of trapping processes performed on them. In this paper, we show that transport efficiency is much lower in a fractal scale-free network than in non-fractal networks. To this end, we examine a simple random walk with a fixed trap at a given position on a fractal scale-free network. We calculate analytically the mean first-passage time (MFPT) as a measure of the efficiency for the trapping ...

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

Random walks are one of the best investigated dynamical processes on graphs. A particularly fascinating phenomenon is the scaling relationship of fluctuations $\sigma $ with the average flux $\langle f \rangle $. Here we analyze how network topology and nodes with finite capacity lead to deviations from a simple scaling law $\sigma \sim \langle f \rangle ^\alpha$. Sources of randomness are the random walk itself (internal noise) and the fluctuation of the number of walkers (e...

Loops are subgraphs responsible for the multiplicity of paths going from one to another generic node in a given network. In this paper we present an analytic approach for the evaluation of the average number of loops in random scale-free networks valid at fixed number of nodes N and for any length L of the loops. We bring evidence that the most frequent loop size in a scale-free network of N nodes is of the order of N like in random regular graphs while small loops are more f...