PageRank by Random Walk
One random surfer, clicking forever, ranks a whole web. Build a graph and watch a surfer's visit frequencies converge to the same PageRank vector that power iteration computes.
PageRank by Random Walk
PageRank scores a page by how often a surfer who clicks random links, and occasionally jumps to a page at random, ends up there. Two methods reach the same numbers: power iteration on the Google matrix, and a single surfer counting its own visits. Edit the graph and watch both views track each other.
With probability d the surfer follows a random out-link; with probability 1 - d = 0.15 it teleports to a node picked uniformly at random. Teleportation is what makes the chain irreducible, so a unique ranking exists no matter how the links are wired. The classic web value is 0.85.
The Google matrix. Column j of M says where the surfer goes from node j: an even split across its out-links. The full operator is G = d M + (1 - d)/N, mixing those links with a uniform teleport. PageRank is the vector r that G leaves unchanged, the stationary distribution of the chain. Power iteration finds it by applying G over and over from any start.
Dangling nodes. A node with no out-links is a dangling node. A surfer landing there has nowhere to click, so its column is filled uniformly: from a dead end the walker restarts anywhere. Without that fix probability drains out of the system and the ranks no longer sum to one.
Walk equals matrix. By the ergodic theorem the long-run fraction of time the surfer spends at each node is exactly that stationary vector. So counting visits and powering up the matrix are two routes to the same ranking; the surfer is just a slow, noisy way to read off r.