Random walks on networks: dynamical properties

Abstract

This work is dedicated to random walks on networks and analytical calculations of properties of stochastic properties on networks, in particular, for the coverage area of random walks on networks. This work has been done as follow-up of research papers [GrebTupikina, TupikinaGreb].

Results

Coverage area for a random walk on a network can be expressed through FPT(t), this is one of our results, which we describe in Analytical results section. At the same time, coverage time can be estimated from FPT(t) plot. [see Appendix and post on network nodes].

In order to characterize the spreading of the infections (in SI and SIR) process and to study the effect of heterogeneous node (with different spreading properties of this node) we estimate the average number of distinct sites visited till time t, denoted as $C_{x_0}^1(t)$ for starting site $x_0$.

It is one of the key-quantities, which characterize spreading processes on graphs, is the average number of distinct visited sites by n random walks by the time t [Larralde1992].

We also note that no explicit analytical descriptions of $C_{x_0}^n(t)$ , have been achieved so far for a general case of a network, [ErdosDvor].

Here we derive the average number of visited nodes from FPT for RW. Here we study the effect of heterogeneous node on {the average number of distinct sites visited till time t.

Let $\rho _{x_0}^1(t)$ be the probability density that site x has been visited for the first time at time t, starting at site $x_0$ .

Then probability that site x has not been visited by one random walker till time t is

$\Gamma_{x_0x}(t) = 1-\int_{0}^{t}\rho_{x_0x}(t')dt'$ ,

where $\rho _{x_0}^1(t)$ is the probability density, which can be expressed using framework from [GrebTupikina]. Therefore we can estimate $C_{x_0}^1(t)$ using expressions of other quantities.

Here we stress out that the coverage area depends on an initial point $x_0$, which was not the focus of the studies in [Starnini].

For some network types (static regular) the initial node does not play a big role, but for some, like irregular temporal networks, the random process on a network is sensitive to an initial condition.

The probability $\Gamma_{x_0x}^n(t)$ , that site x has not been visited by any of n independent random walkers is just the product:

$\Gamma_{x_0x}^n(t) = (\Gamma_{x_0x}(t))^n$ ,

Then the averaged number of distinct visited sites by n independent RWs on a graph G is expressed as a sum over all nodes of the graph V(G) and through the probability $\Gamma_{x_0x}^n(t)$ as:

$C_{x_0}^n(t) =\sum_{x\in V(G)} (1- (\Gamma_{x_0x}(t))^n),$

where $\rho _{x_0}^1(t)$ can be expressed using the framework from [GrebTupikina]. From Equation above we can discover how heterogeneities affect the number of distinct visited sites.

Using $C_{x_0}^1(t)$ one can define a measure, which characterizes the role of heterogeneities on the speed of spreading. In particular, we see that for the regular loopless graphs, the heterogeneous node $x_h$ with $\tilde{\psi}(s)=1/(1+s^\alpha\tau^\alpha),\alpha\in(0,1)$ increases $C_{x_0}^1$, where the limiting behavior of function $C_{x_0}^n =C_{x_0}^n(t\rightarrow\infty)$ .

$C_{x_0}^1$ plays an important role for both, estimation of the global measures for epidemiological processes on graphs (like speed, spread area) and for estimation of the local properties, like node importance in the epidemics spreading process.