PageRank
A node's importance is the long-run chance a random surfer following links lands on it — the dominant eigenvector of the link matrix.
PageRank
How do you rank the importance of a page in a web of millions, using nothing but the links between them? PageRank, the algorithm that launched Google, gives a beautifully circular answer: a page is important if important pages link to it. Importance is defined in terms of itself — and the way out of that circle is one of the loveliest applications of Linear Algebra to a real-world Graph.
The random surfer
Picture someone browsing at random. They sit on a page, pick one of its outgoing links uniformly at random, click it, and repeat — forever. A page's PageRank is the fraction of time this random surfer spends on it. Pages with many incoming links get visited often; a link from a frequently-visited page is worth more than a link from an obscure one, because the surfer arrives there more often to begin with. Importance flows along edges and pools where the structure concentrates it.
One fix keeps the wandering well-behaved. A surfer can get stuck on a page with no outgoing links, or trapped in a small cluster. So with a small probability d \approx 0.15 — the damping — the surfer teleports to a random page instead of following a link. This keeps every page reachable and the long-run fractions unique.
It is an eigenvector
Stack the ranks into a vector \mathbf{r} and the link structure into a matrix M (with the teleport term folded in). The fixed-point equation becomes simply
That is the definition of an eigenvector with eigenvalue 1. PageRank is nothing but the dominant eigenvector of the web's link matrix — exactly the Eigenvalues and Eigenvectors story from the linear-algebra section, made enormous. And you compute it the simplest way imaginable: start with any guess, multiply by M over and over, and watch it converge. This power iteration is the random surfer's wandering written as repeated Matrix Multiplication.
Watch the rank settle
Each node below starts with an equal share of rank. Every step, a node pushes its rank evenly out along its edges (with a dash of teleport mixed back in). A node's size tracks its current rank. Watch the mass slosh around and then settle — the well-connected nodes swell, the peripheral ones shrink, and after a dozen iterations the picture stops changing. That frozen distribution is the dominant eigenvector.
Beyond the web
PageRank long ago escaped search engines. It scores influence in social networks, importance of species in food webs, key papers in citation graphs, and central roads in transport maps — anywhere "important things point to important things" makes sense. It is one face of a larger family of Centrality measures, distinguished by its recursive, eigenvector-based definition of importance.