Markov Chains, Random Walks, and PageRank
A graph has so far been a static object: who is connected to whom. A random walk turns it into a process — a token that moves from vertex to vertex — and that process has a limiting behaviour which is, remarkably, computable. Three useful things come out of this single idea:
the stationary distribution of the walk, which ranks vertices by how often the walk visits them;
PageRank, which is that ranking with one modification that makes it well defined on the web;
Markov chain Monte Carlo, a way to sample from a distribution we can evaluate but not normalise — the machinery behind the E-step of EM and behind Bayesian computation.
Only matrix–vector multiplication is needed, plus the eigenvalue idea from the spectral clustering page: the same spectrum answers both “how does this graph split?” and “how fast does a walk explore it?”.
1. The walk and its transition matrix¶
Let be an undirected graph with adjacency matrix and degrees . From vertex we pick one of its neighbours uniformly and step there. The whole rule is a row-stochastic matrix,
With a row vector holding the probability of being at each vertex after steps,
So a random walk is repeated multiplication by a fixed matrix — the same operation as in the matrix product page, and the same “power iteration” that computes dominant eigenvectors in the SVD chapter.
Worked example: a path of three vertices. For the degrees are and
Then , , , and so on forever: the walk never settles. It is forced to alternate between the two sides. This is periodicity, and it is why the plain walk is not yet a ranking method.
2. Stationary distribution¶
A distribution is stationary when : started in , the law of the walk never changes. For an undirected graph the stationary distribution is proportional to the degrees,
and the check is one line:
The walk therefore spends time at a vertex in proportion to its degree. Existence and uniqueness come from Perron–Frobenius: has eigenvalue 1 with a non-negative eigenvector, and if the graph is connected and aperiodic (for instance has one self-loop) every other eigenvalue satisfies .
3. How fast the walk mixes¶
Order the eigenvalues . Then
so the spectral gap is the mixing rate: a large gap means fast exploration. Here the page meets the spectral clustering one. For the random-walk Laplacian we have
i.e. the eigenvalue that decides whether a graph falls apart into clusters also decides how quickly a walk forgets where it started. Two questions, one spectrum.
4. PageRank: the walk that cannot get stuck¶
Ranking web pages by fails for two reasons: a page with no out-links traps the walk, and a bipartite or periodic structure prevents convergence. PageRank repairs both with a single device, a teleport — with probability , jump to a uniformly random page:
The stationary distribution of the damped chain solves
a linear system, equivalently an eigenproblem for with eigenvalue 1. The chain is now aperiodic and irreducible, exists and is unique, and power iteration converges at rate .
Worked example. For the three-vertex path with , the equations give
against for the undamped walk. The ordering is unchanged; teleport pulls every value a little toward . Page and Brin used . Concentrating the teleport on a seed set instead of the uniform distribution gives personalised PageRank, which is how neighbourhood-based recommenders and citation impact measures use the same iteration.
5. MCMC: sampling from what you can only evaluate¶
Suppose we want to sample from where is known but its normalising constant is not — a Bayesian posterior, a Boltzmann distribution, the conditional law inside an E-step. Direct sampling is out of reach, but a Markov chain whose stationary distribution is is enough: run it long and keep the states.
Metropolis–Hastings. At state propose and accept with probability
otherwise stay where you are. Only the ratio of appears, never its normalising constant — that is the entire trick. The chain satisfies detailed balance,
which implies is stationary. Gibbs sampling is the special case “resample one coordinate from its full conditional”, for which the acceptance probability is exactly 1; it is the standard tool for latent-variable models.
Three practical facts worth stating once: discard a burn-in; consecutive samples are correlated, so the effective sample size is smaller than the iteration count; and a chain can look healthy in a trace plot while mixing badly — hence several chains and a comparison of their answers.
6. Where this leads¶
Hidden Markov models are a Markov chain on hidden states plus an emission model. The forward recursion is the walk of §1 with a reweighting by the likelihood at every step, which is why its cost is rather than the of enumerating state sequences.
Spectral clustering uses the same spectrum as §3 for a different question (where to cut).
EM needs expectations that Gibbs and Metropolis–Hastings can supply when the E-step cannot be computed in closed form.
Exercises¶
For the three-vertex path compute and , and explain the alternation using the eigenvalues of (they are ).
Show that a bipartite graph gives for and hence period 2, and that adding a single self-loop removes the period without changing the stationary distribution.
Implement PageRank by power iteration on a random directed graph. Plot and check that it falls by a factor per iteration.
Write Metropolis–Hastings for on the line, and compare the normalised histogram with the exact density.
Sources¶
T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, 2nd ed., §14.10 (PageRank) and §8.6 (MCMC).
M. J. Zaki, W. Meira Jr., Data Mining and Machine Learning, ch. 5 (Markov chains and random walks on graphs).
A. Blum, J. Hopcroft, R. Kannan, Foundations of Data Science, ch. 5–6 (random walks, Markov chains, mixing).