12.6 Random walks and PageRank

Suppose an object moves around a graph, choosing its next edge at random according to a rule at its current node. We may not know where it will be after one or two moves, but we can ask a precise question: what is the probability that it is at a particular node? A random walk is this repeated random movement. The next-step chances depend on the current node, so instead of predicting one path, we track a probability for every possible current node and update those probabilities after each move. This can model movement between locations, changes between states, or visits through a network.

This is intermediate to advanced Stage 1 material. Review conditional probability and sink components first. Transition matrices explain the compact update below, but you can follow the two-node example without them. MIT OpenCourseWare's Centrality and Web Search lecture develops this interpretation further.

A basic idea: add the chances of arriving at a node

Take two nodes, $A$ and $B$. From $A$, the walker must move to $B$. From $B$, it moves to $A$ with probability $1/2$ or stays at $B$ with probability $1/2$. Suppose it starts equally likely at either node: $p_0(A)=p_0(B)=0.5$. This pair of starting probabilities is a distribution; its entries add to $1$.

After one move, the walker can reach $A$ only by starting at $B$ and choosing $B\to A$. Multiply the chances: $p_1(A)=0.5(1/2)=0.25$. It can reach $B$ in two different ways: start at $A$ and move there, or start at $B$ and stay. Add those separate chances: $p_1(B)=0.5(1)+0.5(1/2)=0.75$. The new distribution is $(0.25,0.75)$, still totalling $1$.

For the second move, repeat from the new distribution: $p_2(A)=0.75(1/2)=0.375$ and $p_2(B)=0.25(1)+0.75(1/2)=0.625$. We have found the probability of being at either node after two steps without having to guess which single path the walker took. For example, the $0.375$ chance of ending at $A$ also comes from adding the two possible two-step paths to $A$: $0.5(1)(1/2)=0.25$ and $0.5(1/2)(1/2)=0.125$.

A quick tour of random walks

For every possible move from node $i$ to node $j$, let $P_{ij}$ be its probability. A move that is not allowed has probability $0$; the probabilities of all moves leaving one node add to $1$. If a node has no outgoing edge, the model must supply a rule, such as staying there with probability $1$. Let $p_t(i)$ be the probability that the walker is at node $i$ after $t$ moves. To find the probability at a particular node $j$ after one more move, add the probability arriving from every possible previous node:

$$p_{t+1}(j)=\sum_i p_t(i)P_{ij}.$$

Each term multiplies the chance of being at $i$ by the chance of moving from $i$ to $j$. Adding the terms combines alternative routes to $j$. A single walker takes one route; $p_t$ describes our uncertainty over all routes it could have taken.

For a compact calculation, use a row-vector convention: $p_t=(p_t(A),p_t(B),\ldots)$ and $p_{t+1}=p_tP$. Each row of the transition matrix $P$ lists the outgoing probabilities from one node and must sum to $1$. For our two-node walk,

$$P=\begin{pmatrix}0&1\\[2pt]1/2&1/2\end{pmatrix},\qquad p_0=(0.5,0.5),\qquad p_1=p_0P=(0.25,0.75),\qquad p_2=p_1P=(0.375,0.625).$$

When repeated updates settle, a stationary distribution $p_*$ satisfies $p_*=p_*P$: one more move does not change the probabilities. In this walk, $A$ receives half of $B$'s probability, so a stable pair must satisfy $p_*(A)=p_*(B)/2$ and $p_*(A)+p_*(B)=1$. Solving gives $(1/3,2/3)$. Not every graph's walk settles from every start. A closed group can trap a walker, and a strict back-and-forth cycle can make probabilities alternate.

PageRank: a use of the random walk

Now make the nodes web pages and the directed edges links. A visitor following a random outgoing link performs a random walk; a page visited more often in the long run gets a larger walk-based score. An ordinary link walk has problems: a page with no outgoing link has nowhere to send its probability, and a sink group can trap the visitor. PageRank keeps the walk but sometimes makes a random jump, called teleportation.

First give each page with no outgoing links a fallback outgoing distribution, often the same distribution $u$ used for jumps, so every row of $P$ still sums to $1$. Let $d$ be the chance of following a link and $u$ the jump distribution. One PageRank update is

$$p_{t+1}=d\,p_tP+(1-d)u,\qquad 0<d<1.$$

The first part follows links; the second part redistributes a small amount of probability through jumps. The entries remain nonnegative and add to $1$. If $u$ gives every page a positive chance, a visitor can eventually get out of any sink and reach any page. Repeating the update approaches a stable PageRank distribution in this finite model.

For the two-node example, let $d=0.8$ and $u=(0.5,0.5)$. The link-only move from $(0.5,0.5)$ gives $(0.25,0.75)$; adding jumps gives $0.8(0.25,0.75)+0.2(0.5,0.5)=(0.30,0.70)$. Another update gives $(0.38,0.62)$. The stable PageRank score solves $p=d\,pP+(1-d)u$ and is $(5/14,9/14)$, approximately $(0.357,0.643)$. It describes this chosen link-and-jump model, not an intrinsic quality of a page.

The animation separates following a link from adding teleportation. Use Next to see the probability move and the total remain $1$.

Previous

Replay Next

Application 1: a non-web random walk

A two-state model says a dry day is followed by a dry day with chance $0.8$, and a wet day is followed by a dry day with chance $0.4$. Starting from a certainly dry day, what is the distribution after two steps?

1. Write the rows in dry, wet order. $P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}$; each row sums to $1$.
2. Take one step. $p_0=(1,0)$ gives $p_1=(0.8,0.2)$.
3. Take another. $p_2=(0.8,0.2)P=(0.8\cdot0.8+0.2\cdot0.4,\ 0.8\cdot0.2+0.2\cdot0.6)=(0.72,0.28)$.

This is an ordinary random walk with no teleportation. It uses the same multiply-and-add rule as the two-node example.

Application 2: rank two pages

Use the two-page graph above with $d=0.8$, uniform jumps, and $p_0=(0.5,0.5)$. What is the distribution after two PageRank updates?

1. Follow links from the start. $p_0P=(0.25,0.75)$.
2. Mix in jumps. $p_1=0.8(0.25,0.75)+0.2(0.5,0.5)=(0.30,0.70)$.
3. Repeat. $p_1P=(0.35,0.65)$, so $p_2=0.8(0.35,0.65)+0.2(0.5,0.5)=(0.38,0.62)$.

Page $B$ has the larger score after two rounds; both entries still add to $1$.