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, weightproportional 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 frequencyspace transform. Here, we’ll use the Laplace transform. (An instructive exercise would be to use the Ztransform 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 steadystate, 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 steadystate 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