Random walks on networks

Given some network, weighted or unweighted, directed or undirected, what is the probability that a random walker starting at node \(i\) reaches node \(j\) after \(t\) timesteps?

It’s an old, solved problem, but it’s still fun. Brief consideration of the problem allows us to write down the solution as

Denoting \(\Pr(j_{k} \rightarrow j_{k + 1})\) by \(P(j_{k}, j_{k + 1})\), we can rewrite this as

Note that we can think of the term outside of the product as the “entry” and “exit” condition; if \(P(i, j_1) = 0\) or \(P(j_{t - 1}, j) = 0\) for some \(j_{1}\) or \(j_{t - 1}\), that means that, e.g., node \(i\) isn’t connected to node \(j_1\) and so the probability of transferring to that node is zero. If these probabilities are zero for all nodes, e.g., \(j_1\), then that means node \(i\) is an isolated node–connected to no other nodes–and therefore we obviously can’t get to node \(j\) from \(i\).

From the above we can derive the various forms of \(\Pr(i \rightarrow j \text{ in } t \text{ timesteps }) \equiv P_{ij}(t)\) for different types of networks.

  • Undirected, unweighted, uniform probability: Here, \(P(j_{\ell}, j_{\ell + 1})\) is inversely proportional to the degree of the outgoing node:

    so that the general equation becomes

    This equation for \( P_{ji}(t) \) is

    Thus we see that \(K_i P_{ij}(t) = K_j P_{ji}(t) \), so that the system exhibits detailed balance and thus we could solve for its stationary distribution. This result was shown by Noh and Rieger in 2008; see their paper.

  • Undirected, weighted networks, weight-proportional probability: This problem is almost identical to that given above. Here the transition probabilities are given by

    Then the above equations become

    and

    so that this system also exhibits detailed balance; \(w_iP_{ij}(t) = w_jP_{ji}(t)\).

  • Here is an interesting example. Suppose a network has some “central” node \(n_0\), and define the distance from node \(j\) to this central node by

    Suppose a random walker of mass \(m = 1\) moves through the network influenced by some potential function \(V(r) = r^2 \), and that the walker passes from node \(j_{\ell}\) to node \(j_{\ell + 1}\) with probability proportional to the negative inverse of the force exerted on the walker by node \(j_{\ell + 1}\). Considering the corresponding deterministic flow on the line, we see that \(\ddot{r} = -2r\), so the deterministic system is conservative. Then \(F = -\frac{\partial V}{\partial r} = -2r\), so we have

    whereupon the general equation for \(P_{ij}(t)\) becomes

    We find that \( r(j)P_{ij}(t) = r(i)P_{ji}(t) \) which we write as

    So we find that the stationary distribution is proportional to the inverse of the distance from the origin:

    What about if \(r(i) = 0\)–that is, if we’re already at \(n_0\)? This is a systemic problem in classical physics that is due to the concept of a point mass, and cannot be resolved here. (Consider, for another example, the gravitational force…)

Distribution of first passage

Before considering another interesting case, let us discuss the distribution of first passage; that is

If we think about \(P_{ij}(t)\) carefully, we realize that we can write it as

which we can write as

We’re almost right, but we need a correction term. What happens if we’re already at \(j\) when we start? Really, we should write the above as \( P_{ij}(t) = [t = 0] [i = j] + \sum_{\tau = 0}^t F_{ij}(\tau)P_{jj}(t - \tau) \) or, using Kronecker’s delta,

Now we have to solve this functional equation for \(F_{ij}(t)\). There are a lot of ways to do this, but probably the easiest is to use some sort of frequency-space transform. Here, we’ll use the Laplace transform. (An instructive exercise would be to use the Z-transform to replicate these results.) Applying the transform to both sides of the above, denoting \( L{ \cdot } \equiv \tilde{\cdot} \), and using common identities gives

The first term on the right was easy, since the Laplace transform of the Dirac spike is the identity. The second sum might worry us momentarily, but we can rewrite it as a proper convolution:

so that the Laplace transform of the whole equation is actually just

whereupon we see that the first passage distribution in frequency space is

Now, the mean first passage time from \(i\) to \(j\), denoted \(\langle T_{ij} \rangle \), is just \( \langle T_{ij} \rangle \equiv \mathbb{E}_{F_{ij}}[t] = \sum_{t = 0}^{\infty}t F_{ij}(t) \). Let us introduce the operator \( \theta_n \equiv (-1)^n \frac{d^n}{ds^n} \). Then we see that the first moment of \(F_{ij}(t)\) is just \(\langle T_{ij} \rangle = (\theta_1 \tilde{F_{ij}})(0) \). Performing this calculation we find that

valid for \(i \neq j\). Now, we may want to examine more specialized cases of this distribution. For example, we could ask what the average time of first return is–how long, on average, will our walker spend traversing the network before returning to the node from which it started? To answer this question requires a bit of work. First, suppose that \(P_{ij}\) satisfies detailed balance. Letting \(\pi_i\) be the equilibrium probability of the system being in state \(i\) (i.e., of the walker being at node \(i\) ), we will denote the equilibrium distribution as \(P_i(\infty) = \pi_i / c_i\) where \(c_i\) is the normalization constant. (Recall that we are, for now, considering finite networks, so that all distributions are normalizable.) Since this distribution has a steady-state, let us consider the transient distribution \(Q_{ij}(t) \equiv P_{ij}(t) - P_j(\infty) \). We will denote the moments of this distribution by \(\rho_{ij}(n) = (\theta_n \tilde{Q_{ij}})(0) \). Separating into steady-state and transient parts, we then have

where the transient terms are simply the Laplace transform of the transient distribution: \( \sum_{t = 0}^{\infty} (P_{ij}(t) - P_j(\infty))e^{-st} \ \). Now, \( e^{- st} = \sum_{n=0}^{\infty}\frac{(-1)^n s^n t^n}{n!} \), so the above sum becomes

which we recognize (with joy!) as \( \sum_{n = 0}^{\infty} \rho_{ij}(n) \frac{(-1)^n s^n }{n!} \). Then the above formula becomes

Substituting this into the equation for the first passage distribution in frequency space and then calculating \( (\theta_1 \tilde{F_{ij}})(0) \) gives the general mean time of first passage as

Preferential attachment

With this result in mind, let’s consider one more type of random walk. Suppose the walker transitions from node \(j_{\ell}\) to \(j_{\ell + 1}\) with probability proportional to some function, call it \(R\), of the edge degree of \(j_{\ell + 1}\):

This is similar to many other preferential attachment processes, beginning with Yule and Simon, then de Solla Price, then Watts / Strogatz, then Barabasi / Albert, etc. The process considered here differs from those above because it does not feature injection of probability into the system; probability is conserved. Now, from the general equation for \(P_{ij}(t)\) we have that

We are interested in the time of first return. Does the function \(R\) affect the time of first return? We see that the system satisfies detailed balance. In particular, we have

so that

We will define the first return statistic of a network on which the above process operates in the following manner: let \(p(k)\) be a probability mass function with mean \(\mu \equiv \langle k \rangle\) that describes a network’s degree distribution. Then the first return statistic \(FR(\mu)\) is given by

For example, in the relatively simple case where \( R(\beta) = \beta \), we have that

Written on March 20, 2017