Skip to main content
SearchLoginLogin or Signup

Random walks on networks: dynamical properties

Published onSep 01, 2019
Random walks on networks: dynamical properties


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


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 Cx01(t)C_{x_0}^1(t) for starting site x0x_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 Cx0n(t)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 ρx01(t)\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 x0x_0 .

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

Γx0x(t)=10tρx0x(t)dt\Gamma_{x_0x}(t) = 1-\int_{0}^{t}\rho_{x_0x}(t')dt' ,

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

Here we stress out that the coverage area depends on an initial point x0x_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 Γx0xn(t)\Gamma_{x_0x}^n(t) , that site x has not been visited by any of n independent random walkers is just the product:

Γx0xn(t)=(Γx0x(t))n\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 Γx0xn(t)\Gamma_{x_0x}^n(t) as:

Cx0n(t)=xV(G)(1(Γx0x(t))n),C_{x_0}^n(t) =\sum_{x\in V(G)} (1- (\Gamma_{x_0x}(t))^n), %\\ \nonumber = \sum_{x\in V(G)} (1-(1-\int_{0}^{t}\rho_{x_0x}(t')dt')^n),

where ρx01(t)\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 Cx01(t)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 xhx_h with ψ~(s)=1/(1+sατα),α(0,1)\tilde{\psi}(s)=1/(1+s^\alpha\tau^\alpha),\alpha\in(0,1) increases Cx01C_{x_0}^1, where the limiting behavior of function Cx0n=Cx0n(t)C_{x_0}^n =C_{x_0}^n(t\rightarrow\infty) .

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

No comments here
Why not start the discussion?