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 as a walk with teleportation, DeepWalk and node2vec as walks turned into 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. A town split by one bridge feels far apart because crossings are rare, which is exactly what partitioning exploits.

Where it stops: real analyses add teleportation, the bored tourist taking a taxi home, to fix dead ends and disconnection. They study exact hitting times rather than vibes.

How It Actually Works

The transition matrix is $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, because flow balances: $d_i \times (1/d_i) = 1$ unit crosses each edge each way.

Hitting and commute. Hitting time $H_{ij}$ is the 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

Take the line $1 - 2 - 3$ . Degrees are $1$ , $2$ , $1$ with total $2|E| = 4$ . Stationarity predicts $\pi = (0.25, 0.50, 0.25)$ .

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

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

Two step return to the middle: go left then back with $0.5 \times 1 = 0.5$ , or right then back with $0.5 \times 1 = 0.5$ , for total $1.0$ . Every two step trip from the middle returns. From an end, two step return is impossible at $0$ : ends need middle end middle in three steps. The middle owns double degree, double time share, and certain 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: scores sum correctly but shift with initialization, or one component hogs everything. Fix: add teleportation as PageRank does, 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. Averages converge but snapshots do not.

Symptom: iterates flip flop while the residual refuses to shrink on an exactly periodic structure. Fix: use a lazy walk that stays put with probability $0.5$ or add 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.