# PageRank

Ranking nodes by the stationary distribution of a random walk that occasionally teleports, so importance flows from important neighbours.

**Rests on:** Markov Decision Processes, Vector Spaces and Rank

*Mathematical Foundations · Graph Theory*


## Why learn this

PageRank is the algorithm that made modern search engines possible. You have likely used it every time you looked up something on Google or another major search engine. Learning how it works helps you understand why some websites appear at the top of your results while others do not. It also explains how recommendation systems decide which products, articles, or videos are 'important' enough to show you first. Concretely, this page prepares you to: (1) explain in simple terms how a search engine decides what is relevant among billions of pages, (2) follow discussions about online reputation and ranking algorithms, and (3) recognize how similar logic is used to find influential people in social networks or key papers in scientific citations. For example, if a page has 10 links pointing to it from pages that are themselves very popular, PageRank calculates that this page deserves a high score, even if it only has those 10 links.


## The intuition

Imagine you are a librarian trying to decide which books in a huge library are the most important. You cannot read every book in its entirety, so you use a simpler rule based on who refers to whom. If Book A cites Book B, it suggests that Book B is useful or authoritative. But importance flows through these citations. If Book B is cited by many other important books, Book B becomes more important itself. Crucially, not all citations are equal. A citation from a highly respected, widely-read book counts for more than a citation from an obscure, little-known book. This is the core idea of PageRank: importance is not just about how many links point to you, but who those links come from.

Now, think about a person surfing the web as a 'random surfer.' Imagine this person starts on any random webpage. They look at the links on that page and choose one at random to click. They arrive at a new page, look at its links, and choose another at random. They keep clicking like this forever. However, sometimes they get bored or lost. Let’s say there is a 15% chance at any step that they stop clicking links and instead jump to a completely new, random page on the internet (this is the 'damping factor' in action). Over a very long time, the surfer will spend varying amounts of time on different pages. Some pages will be visited far more often than others. These visit frequencies stabilize into fixed percentages. Pages that are linked to by other important pages get visited more often and thus receive higher PageRank scores. The final score for each page is simply the long-term proportion of time the random surfer spends on that page.


## An analogy

Think of a university campus with a statue of a famous alumnus in the center square. Students gather around this statue, but not because the statue itself is inherently interesting — they gather there because it sits at the junction of many footpaths, and those footpaths lead from other important places like the library, lecture halls, and the dining hall. If you wanted to know which spot on campus is most 'central' or important, you wouldn’t just count how many paths touch it; you would watch where the students actually go.

Now, replace the statue with a webpage and the footpaths with hyperlinks. Replace the students wandering randomly with our random web surfer who occasionally teleports. The importance of the webpage is determined by how often the surfer ends up there, which depends on how many important pages link to it, and whether those linking pages are easy to reach. In this analogy, a page linked from the library (a very important place) gets more 'traffic' than a page linked from a quiet study room. The PageRank score is effectively the average number of times you would find the surfer standing in front of that specific webpage if you checked randomly after many hours. The analogy has limits: in the real web, pages can link to themselves, and human judgment of importance varies, but the core idea — that importance flows through connections and can be measured by a steady pattern of movement — holds true.",


## Definition

PageRank is a method for ranking items in a network by simulating a random walker who mostly follows links but occasionally jumps to a random item; the final score of each item is the long-term percentage of time the walker spends there."


## How it connects

This concept sits alongside Dijkstra’s algorithm, which finds the shortest path between two points, and Breadth-First Search (BFS) or Depth-First Search (DFS), which explore all reachable items from a starting point. While those methods focus on *how* to get from A to B, PageRank focuses on *which* places are most significant within the whole network by analyzing the flow of connections. It also sets the stage for understanding social network analysis, where it helps identify key influencers in groups of people.


## The mathematics

This concept rests on linear algebra and probability. Linear algebra (specifically, matrices, vectors, and eigenvectors) is the language for systems of many interacting numbers — here, the importance of millions of pages. Probability is the language of randomness and long-term averages, exactly what the random surfer provides. The key operation you need is **matrix-vector multiplication**, which is just a rule for taking a list of numbers (the vector of importance scores) and a table of numbers (the matrix of link structure) and producing a new list that combines both. Let's build it from scratch. Suppose you have two pages: A and B. A has a link to B; B has no links. We can write a matrix M where each row represents the 'from' page and each column the 'to' page, and M[i][j] = 1/(number of out-links from page i) if there is a link from i to j, else 0. For example, if A has 2 out-links (to B and C), then the row for A is [0, 1/2, 1/2]. Now, the PageRank vector r (a list of scores) is updated by r_new = M * r_old, which means: the new score of page j is the sum over all pages i that link to j of (1/outdegree(i)) * r_old[i]. This is exactly the random surfer idea: the chance of being on page j next is the sum of the chances of being on each i and then clicking the link to j. The stationary distribution is the vector r such that M * r = r, and that is an eigenvalue equation with eigenvalue 1. Power iteration is the simple procedure of repeatedly multiplying the current vector by M, and it converges to the dominant eigenvector, which is what we want.

The PageRank vector r is defined by:

r = (1 - d) / N + d * M * r

where:

- r is a column vector of PageRank scores, one per page, summing to 1 (after normalisation).
- d is the damping factor, a number between 0 and 1, usually set to 0.85.
- N is the total number of nodes (pages).
- M is the link matrix, where M[i][j] = 1/outdegree(i) if page i links to page j, and 0 otherwise. If a page has no out-links, we treat it as linking to every page (or just ignore it in the sum).
- The formula is solved by iterating: start with any vector r0, repeatedly compute r_{k+1} = (1-d)/N + d * M * r_k, and the vector r converges to the unique stationary distribution.

The stationary distribution is the dominant eigenvector of the matrix (1-d)/N * J + d * M, where J is an all-ones matrix, but you do not need to remember that for now.


## A worked example

```
Consider a tiny web of three pages: A links to B, B links to C, and C links to A. (A cycle.) We ignore the damping factor for this hand example, so each step is just multiplying by the link matrix. We start with an initial, arbitrary vector r0 = (1, 0, 0). (We could start with any positive numbers; they will converge to the same final scores.)

Step 1: Step 1: from r0 = (1, 0, 0)   # We start with all importance on A.
Step 2: r1 = (0, 1, 0)   # A has one out-link (to B), so the whole importance of A moves to B.
Step 3: Step 2: r2 = (0, 0, 1)   # B has one out-link (to C), so all importance moves to C.
Step 4: Step 3: r3 = (1, 0, 0)   # C has one out-link (to A), so we are back to where we started.
Step 5: This cycles forever: (1,0,0) -> (0,1,0) -> (0,0,1) -> (1,0,0)...   # Without damping, this graph does not converge to a unique stationary distribution — it oscillates. This is why the damping factor is essential.

Result: Our simple cycle shows that a pure random walk without damping may not stabilise; we need to add the teleportation step to guarantee a unique set of scores.
```


## From scratch, in Python

```python
# We'll build a tiny graph of 4 pages: 0->1, 0->2, 1->2, 2->3, 3->0
# (a small cycle plus an extra link)

n = 4  # number of pages

# Step 1: Build the link matrix M, but we will actually store it as a list of lists.
# To compute M[i][j] = 1 / outdegree(i) if link from i to j, else 0.

outlinks = {0: [1, 2], 1: [2], 2: [3], 3: [0]}  # dictionary: node -> list of nodes it links to

M = [[0.0] * n for _ in range(n)]  # a list of 4 lists, each with 4 zeros
for i in range(n):
    out_neighbors = outlinks[i]
    weight = 1.0 / len(out_neighbors)  # 1 divided by number of links
    for j in out_neighbors:
        M[i][j] = weight

# Step 2: The damping factor
d = 0.85

# Step 3: Power iteration
r = [1.0 / n] * n  # start with uniform scores: [0.25, 0.25, 0.25, 0.25]

for _ in range(100):  # 100 iterations is plenty for a small graph
    new_r = [0.0] * n
    for j in range(n):  # we compute new score for page j
        total = 0.0
        for i in range(n):
            if M[i][j] != 0:
                total += M[i][j] * r[i]
        new_r[j] = (1 - d) / n + d * total
    r = new_r

# Step 4: Print the scores (they should sum to 1.0 roughly)
print(r)
```


## What the code does

We first create a dictionary `outlinks` that maps each node to a list of its outgoing neighbours. For example, node 0 points to nodes 1 and 2. Then we build the matrix `M` as a list of lists, where `M[i][j]` is 0 if there is no link from i to j, and 1 divided by the number of out-links otherwise. Next, we set the damping factor `d`. The vector `r` starts with equal probabilities: 1/n each. In the loop, for each page `j`, we compute the sum of `M[i][j] * r[i]` over all `i` that link to `j`. That sum is the 'random surfer' chance of landing on `j` by following a link. Then we add the teleportation term `(1-d)/n`. We repeat this 100 times, which for a 4-node graph is more than enough to converge. Finally, we print the scores, which will be close to [0.15, 0.20, 0.28, 0.37] (the exact values depend on the graph). This is the same thing that a search engine computes on billions of pages, just on a tiny scale.


## Common misconceptions

**PageRank is the same as counting links** — A page is important if many pages link to it, regardless of who those pages are.

If a page is linked from a spam site, that link should carry little weight. PageRank uses the importance of the linking page itself, so a link from an important page contributes much more. In fact: PageRank computes importance as a recursive definition: a page is important if important pages link to it. That is why it is a fixed-point computation, not a simple count.

**The damping factor is a detail I can ignore** — I can just set the damping factor to 1 and get a correct ranking.

If d=1, the random walk does not teleport, and for many graphs (like a cycle) it may not converge to a unique ranking. Also, pages with no out-links (dangling nodes) would 'leak' importance and break the algorithm. In fact: The damping factor, typically 0.85, guarantees that the iterative process converges to a unique solution and also handles dangling nodes by giving them a way to jump away.

**PageRank is unique and objective** — There is one correct PageRank score for each page.

The scores depend on the damping factor, the treatment of dangling nodes, and any personalisation (teleportation to a preferred set of pages). Different choices give different rankings. In fact: PageRank is a model of the web with tunable parameters; the standard choice is d=0.85 and uniform teleportation, but that is not the only choice.

**PageRank tells you the most visited page** — The PageRank score is the probability that a real user will visit the page.

A real user does not click uniformly at random or teleport randomly; real browsing behaviour is far more complex. PageRank is a theoretical model, not a prediction of actual traffic. In fact: PageRank is a mathematical measure of centrality based on an idealised random walk. It correlates with popularity but is not the same as hit counts.

**You need to store a giant matrix** — Implementing PageRank on billions of pages requires storing a matrix with trillions of entries.

The link matrix is extremely sparse — most entries are zero. Real implementations store only the nonzero entries (as adjacency lists) and use power iteration, which only needs vector-matrix products. In fact: Power iteration requires only a sparse representation of the link structure, which is how Google computes PageRank for the whole web.


## In short

PageRank ranks nodes by the long-term probability of a random surfer who follows links but occasionally teleports to a random page. It is computed by repeating a simple vector-matrix multiplication (power iteration) until the scores stabilise. The damping factor guarantees convergence and handles pages with no outgoing links. The underlying mathematics is an eigenvector of a modified link matrix, but you do not need that term to use the idea. Remember: importance flows from important neighbours, not just from many links.


## Where this is used

PageRank is used far beyond its origin in web search. It is a core tool in graph analysis and is a key ingredient in systems that rank nodes by importance in a network. In **large language models (LLMs)**, PageRank appears indirectly through the attention mechanism, which draws on graph-like structures; more concretely, some retrieval systems use a variant of PageRank to rank the importance of documents in a retrieved set. In **retrieval-augmented generation (RAG)**, a knowledge base is often a graph of facts, and retrieving the most relevant and important facts can be done by running PageRank on that graph to find the central nodes. In **agentic systems** that plan and call tools, an agent might use a graph of possible actions or resources, and PageRank can help decide which tool or step is most critical to try first. In **recommendation systems**, items are often connected by user-item interactions, and PageRank on that graph can find popular or influential items. In **social network analysis**, PageRank is used to find influential users, because it captures not just follower counts but the influence of those followers. In **knowledge graphs**, entity importance is computed by PageRank to aid in question answering. Even in **fraud detection**, PageRank-like algorithms can detect important entities in a transaction graph. For a developer, implementing PageRank in a modern system often means using a graph library like NetworkX in Python, which has a built-in `pagerank` function. Under the hood, that function performs exactly the power iteration we implemented by hand. When it is done badly, such as with too small a damping factor or ignoring dangling nodes, the algorithm may fail to converge or give nonsensical results. PageRank also appears in 'TextRank' for extractive summarisation, where sentences are nodes and similarity edges are links, and the top-ranked sentences are used as a summary. That is a direct application of PageRank to natural language processing.


---

Read this on the web: https://basavapurushottam.com/learn-ai/pagerank
