PageRank

PageRank is the algorithm that made Google possible, and it is the clearest example of how modern AI ranks information. Learning it unlocks the study of graph theory at a deeper level, including how search engines, recommendation systems, and even large language models decide which results or facts are most important. You will be able to understand concepts like centrality, random walks, and power iteration, which appear later in graph neural networks and knowledge graphs. Concretely, this page prepares you to: (1) explain how a search engine orders billions of pages, (2) follow discussions about ranking and recommendation systems, and (3) recognize the same underlying mathematics in AI systems that find important nodes in a network, such as social networks or citation graphs.

Imagine you are a librarian and you want to decide which books in a huge library are the most important. You cannot read them all, so you use the structure of who refers to whom. A book that is cited by many other important books should be considered important itself. But importance flows: if a book is cited by a very important book, that citation counts more than being cited by a book nobody reads. This is the core idea of PageRank: importance is not just how many links point to you, but who those links come from. Now think about a person surfing the web. They start on a random page and click a link at random to go to another page. They keep doing this, but occasionally, they get bored and jump to a completely random page. Over time, the proportion of time the surfer spends on each page stabilises to a fixed set of numbers — the PageRank scores. Pages with many links from important pages get visited more often and thus get higher scores. This 'random surfer' model is a random walk on the web graph, with a damping factor that represents the jump to a random page. The damping factor ensures that the process always converges to a unique set of scores, no matter where you start, and it also handles the problem of pages with no outgoing links — 'dangling nodes' — because the surfer can jump away from them. The final scores are the stationary distribution of this random walk: the long-term probability of being on each page.

Think of a university campus with a statue of a famous alumnus. Students gather around the statue, but not because the statue itself is interesting — they gather because it is located at the junction of many footpaths, and the footpaths originate from other important buildings like the library and the lecture halls. Now, replace the statue with a webpage and the footpaths with hyperlinks. The importance of the statue is not just the number of paths leading to it, but how many people walk along those paths, and those people come from other important places. Now, imagine a single wandering student who starts at a random building and walks along a random path each minute, but every ten minutes, they teleport to a random building because they are lost. Where will you most likely find them after many hours? In the building that is most 'central' in terms of the flow of walkers — that is the PageRank. The analogy breaks down in a few ways. First, in the real web, a page can link to itself, which would mess up the random walk, but we usually ignore or handle that. Second, not all web pages are equally important in the eyes of a human, but PageRank only uses the link structure, so it can be gamed. Third, the damping factor is a fixed number, but in reality, a surfer's boredom might vary. Nonetheless, the core idea — importance flows through links, and a random walk with teleportation measures it — is exactly what PageRank does.

PageRank is a method for ranking nodes in a directed graph by computing the stationary distribution of a random walk that, at each step, either follows an outgoing edge uniformly at random or, with a fixed 'damping' probability, teleports to a uniformly random node.

You have not yet studied graph theory directly, but PageRank is the first node in that family. It builds on the everyday idea of moving through a network, but it uses a surprising mathematical tool: the stationary distribution of a random process. Critically, PageRank is the first place you will meet the concept of an eigenvector, which is a core idea in linear algebra and appears again in many AI algorithms, such as principal component analysis and the power iteration method. Your library notes that PageRank is the dominant eigenvector of a modified link matrix; in this page, you will see why that is true. The neighboring concepts you will later study — Dijkstra and BFS/DFS — tell you about paths, but PageRank tells you about importance, which is a different kind of central measure. It also sets the stage for social network analysis and knowledge graphs, where you rank nodes by their position in the whole structure.