Random Walks on Graphs

A drunk wanderer stepping to random neighbours: where it spends its time reveals importance, and how long trips take reveals distance.

A walk on a three-node line with transition arrows spends half its time at the middle node and returns there in one two-step round trip

Why Does This Exist?

Graphs have no coordinates, so "important" and "close" need operational definitions. A random walk supplies both: importance is where a wanderer spends its time, closeness is how quickly it arrives. That idea powers PageRank (a walk with teleportation), DeepWalk and node2vec (walks as sentences), diffusion distances, and cover-time bounds for exploration. The chain theory underneath is in Markov chains and long-run behaviour in stationary distributions; the graph encoding is in graph fundamentals.

The one idea you need first

From node $i$ with degree $d_i$ , step to each neighbour with probability $1/d_i$ . That is $P = D^{-1}A$ . On a connected undirected graph the walk settles to $\pi_i = d_i / 2|E|$ : time share equals degree share.

Think of It Like This

A tourist who only follows signposts

A tourist in a town with no map stands at each junction and picks an outgoing road uniformly at random. Busy junctions with many roads get visited often, not because they are signposted as important but because many routes lead through them. The fraction of evenings spent at each square converges to its share of road ends.

Two landmarks feel close when the tourist stumbles from one to the other quickly on average, even if the map distance is long through dead ends. And a town split by one bridge feels far apart: crossings are rare, which is exactly what partitioning exploits.

Where the analogy stops: real analyses add teleportation (bored tourist taxis home) to fix dead ends and disconnection, and they study exact hitting times rather than vibes.

How It Actually Works

Transition matrix $P = D^{-1}A$ : row $i$ spreads $1/d_i$ over neighbours. A distribution $\pi$ is stationary when $\pi P = \pi$ . For connected undirected graphs, $\pi_i = d_i/2|E|$ works: check flow balance, since $d_i \times (1/d_i) = 1$ unit crosses each edge each way.

Hitting and commute. Hitting time $H_{ij}$ is expected steps from $i$ to first reach $j$ ; commute $C_{ij} = H_{ij} + H_{ji}$ grows with effective resistance. Short commute means well-connected, even across many hops.

PageRank. Real webs dangle and disconnect, so the walk teleports with probability $1 - d$ (usually $0.15$ ) to a uniform node: $P' = dP + (1-d)\mathbf{1}v^\top$ . That guarantees a unique stationary vector, which is the ranking.

Worked example

Line $1 - 2 - 3$ . Degrees $1, 2, 1$ , total $2|E| = 4$ . Stationary: $\pi = (0.25, 0.50, 0.25)$ .

P = \begin{bmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \end{bmatrix}

Verify: $(\pi P)_2 = 0.25(1) + 0.50(0) + 0.25(1) = 0.50$ . Checks.

Two-step return to the middle: from 2, go left then back ( $0.5 \times 1 = 0.5$ ) or right then back ( $0.5 \times 1 = 0.5$ ), total $1.0$ . From an end, two-step return is impossible ( $0$ ): ends must go middle-end-middle in three. The middle's double degree doubles its time share and guarantees immediate return.

Watch Out For

Dangling nodes and disconnected pieces eat the walk

A node with no out-edges traps all mass that arrives; a disconnected component never shares mass with the rest. Plain stationary analysis then reports rankings that depend on where the walk started, and power iteration converges to different vectors per start.

Symptom: rank scores sum correctly but shift with initialization, or one component hogs everything. Fix: add teleportation (PageRank), remove or repair dangling nodes first, and run a connected-components pass before interpreting any walk statistic.

Bipartite periodicity fools convergence tests

On a bipartite graph the walk alternates sides every step, so the distribution oscillates forever and never settles pointwise: even steps favour one side, odd steps the other. Averaging converges but snapshots do not.

Symptom: iterates flip-flop while the residual refuses to shrink, on an exactly periodic structure. Fix: use a lazy walk (stay put with probability $0.5$ ) or teleportation to break periodicity, and test Cesaro averages rather than last iterates.

The Quick Version

Step to a uniform random neighbour: $P = D^{-1}A$ .
Long-run time share is degree share: $\pi_i = d_i/2|E|$ on connected undirected graphs.
On the 3-line the split is 25, 50, 25 percent with certain two-step return to the middle.
Hitting and commute times measure closeness through the walk, not the map.
PageRank adds teleportation to survive dangling nodes and disconnection.
Break periodicity with laziness or teleportation before trusting convergence.