Offensive Security Researcher & Quantum Cryptography Analyst

PageRank Algorithm: Working, Explanation, and Search Engine Optimization

Abdul Wahab Junaid
PageRank algorithm and working of this algorithm

PageRank algorithm and working of this algorithm

When I first tried to understand how Google managed to sort billions of web pages by importance, I kept coming back to one idea: PageRank. I want to walk through it here the way I understood it myself, because once the core idea clicks, the rest of the algorithm feels almost obvious. PageRank is a way of ranking nodes in a graph based on the structure of the connections between them, not on the content of the nodes themselves. It was built for the web, where pages link to other pages, but I have seen it applied to citation networks, social networks, and even biological networks. Its purpose is simple to state: figure out which nodes are “important” by looking at who points to them, and who points to those pointers.

History and Background

I trace PageRank back to 1996, when Larry Page and Sergey Brin were graduate students at Stanford. They were working on a research project called BackRub, which analyzed the link structure of the web. Larry Page is credited with the initial idea (which is where the “Page” in PageRank comes from, though it also nicely describes ranking web pages). In 1998, Page, Brin, along with Rajeev Motwani and Terry Winograd, published the paper “The PageRank Citation Ranking: Bringing Order to the Web.” That same year, Page and Brin used this algorithm as the foundation for Google. What strikes me about the history is that the underlying mathematics was not new — it borrows heavily from the theory of Markov chains and eigenvector centrality, ideas that had existed in linear algebra and bibliometrics for decades. What Page and Brin did was apply this machinery at the scale of the entire web, and that combination of old math and new scale is what made it revolutionary.

Problem Statement

I see the problem PageRank solves as this: given a huge, messy graph of pages linking to each other, how do I assign each page a single number that reflects its relative importance, in a way that is resistant to manipulation and that can be computed efficiently even at web scale? A naive approach — just counting incoming links — fails badly, because it treats a link from a trustworthy, well-linked page the same as a link from a spam page with no other links. PageRank needed to solve this by making importance recursive: a page is important if important pages link to it.

Core Concepts

Before going further, I want to lay out the vocabulary I use throughout this explanation.

How It Works

I like to explain PageRank through its “random surfer” story, because that is genuinely how I first understood it. Imagine a person browsing the web who, at every page, either clicks a random link on that page (with probability d) or gets bored and jumps to a completely random page anywhere on the web (with probability 1-d). If I let this surfer wander for an infinite amount of time, some pages will be visited more often than others. PageRank is exactly the long-run fraction of time the surfer spends on each page.

Step by step, here is how I compute it:

  1. I start by assigning every page an equal initial rank, usually 1/N where N is the total number of pages.
  2. For each page, I look at all the pages linking to it and take a share of each of those pages’ current rank, divided by how many out-links that linking page has.
  3. I sum these shares, scale by the damping factor d, and add the constant (1-d)/N term that represents the random jump.
  4. I repeat this process for all pages simultaneously, producing a new rank vector.
  5. I keep iterating until the rank values stop changing significantly between iterations (this is called convergence).

Working Principle

The internal logic rests on the idea that “importance flows through links.” A page does not get credit just because many pages point to it — it gets credit proportional to the importance of those pages, and that importance is divided among all the links that page sends out. This creates a feedback loop: the rank of every page depends on the rank of every other page, and I resolve this circular dependency iteratively, letting the ranks settle into a stable equilibrium. Mathematically, this equilibrium exists and is unique because of a property called ergodicity — as long as the graph (with random jumps included) allows the surfer to reach any page from any other page, and doesn’t get trapped in cycles, the stationary distribution is guaranteed to exist and be unique.

Mathematical Foundation

The core PageRank formula for a page $p$ is:

$$ PR(p) = \frac{1-d}{N} + d \sum_{q \in M(p)} \frac{PR(q)}{L(q)} $$

where:

In matrix form, I can express this as an eigenvector problem. Let $M$ be the column-stochastic transition matrix where $M_{ij} = 1/L(j)$ if page $j$ links to page $i$, and 0 otherwise. Then the PageRank vector $\mathbf{PR}$ satisfies:

$$ \mathbf{PR} = d \cdot M \cdot \mathbf{PR} + \frac{1-d}{N}\mathbf{1} $$

This is equivalent to finding the dominant eigenvector of the “Google matrix” $G$:

$$ G = dM + \frac{1-d}{N} \mathbf{1}\mathbf{1}^T $$

$$ \mathbf{PR} = G \cdot \mathbf{PR} $$

Since $G$ is a stochastic matrix (columns sum to 1) and is irreducible and aperiodic due to the damping term, the Perron-Frobenius theorem guarantees a unique dominant eigenvalue of 1, and the corresponding eigenvector (normalized to sum to 1) is the PageRank vector. Practically, I never solve this directly with eigen-decomposition for large graphs; I use the power iteration method, repeatedly multiplying by $G$, because it converges quickly and scales to billions of nodes.

Diagrams

flowchart TD
    A[Initialize all pages with PR = 1/N] --> B[For each page, sum incoming rank contributions]
    B --> C[Apply damping factor and random jump term]
    C --> D{Ranks converged?}
    D -- No --> B
    D -- Yes --> E[Output final PageRank scores]

Pseudocode

function PageRank(graph, d, epsilon, max_iterations):
    N = number of nodes in graph
    for each node p in graph:
        rank[p] = 1 / N

    repeat:
        new_rank = {}
        for each node p in graph:
            sum = 0
            for each node q that links to p:
                sum += rank[q] / outDegree(q)
            new_rank[p] = (1 - d) / N + d * sum

        diff = sum over p of |new_rank[p] - rank[p]|
        rank = new_rank

    until diff < epsilon or iterations >= max_iterations

    return rank

Step-by-Step Example

I will use a tiny four-page graph to make this concrete: A links to B and C, B links to C, C links to A, and D links to C only (and nothing links to D).

Iteration 1:

I keep repeating this process, plugging the new values back in, until the numbers barely move between rounds. After enough iterations, this small graph converges to roughly PR(A) ≈ 0.365, PR(B) ≈ 0.194, PR(C) ≈ 0.404, PR(D) ≈ 0.0375 (values approximate). Notice that C ends up with the highest rank because it receives links from A, B, and D — importance flows into it from multiple directions.

Time Complexity

Each iteration of power iteration requires visiting every edge in the graph once to distribute rank, so one iteration costs $O(E)$ where $E$ is the number of edges. If I run $k$ iterations until convergence, the total time is $O(k \cdot E)$. In practice, $k$ is small — often 50 to 100 iterations are enough for the ranks to stabilize on real web-scale graphs, and convergence itself is a geometric process, so the number of iterations needed to reach a given precision grows only logarithmically with how tight I want the tolerance to be.

Space Complexity

I need to store the graph itself, which for a sparse graph like the web takes $O(V + E)$ space (V nodes, E edges), plus two rank vectors of size $O(V)$ — one for the current iteration and one for the next. So overall space complexity is $O(V + E)$. For web-scale graphs with billions of nodes, this is still a serious engineering constraint, which is why real systems distribute the computation across many machines rather than holding everything in memory on one machine.

Correctness Analysis

I rely on two mathematical guarantees for correctness. First, the Google matrix $G$ is column-stochastic, irreducible, and aperiodic (thanks to the damping factor ensuring every page can reach every other page with nonzero probability). By the Perron-Frobenius theorem, this guarantees a unique largest eigenvalue equal to 1, with a corresponding eigenvector that has all positive entries — this eigenvector, normalized, is the PageRank vector. Second, power iteration is guaranteed to converge to this dominant eigenvector as long as the second-largest eigenvalue’s magnitude is strictly less than 1, which the damping factor also ensures. This is why I never worry about the algorithm getting stuck in an infinite loop or diverging — the math guarantees a stable, unique answer exists and that my iterative method will find it.

Advantages

Disadvantages

Applications

I have seen PageRank used well beyond search engines:

Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define N 4          // number of pages
#define D 0.85        // damping factor
#define EPSILON 1e-6
#define MAX_ITER 100

// adjacency[i][j] = 1 means page i links to page j
int adjacency[N][N] = {
    {0, 1, 1, 0}, // A -> B, C
    {0, 0, 1, 0}, // B -> C
    {1, 0, 0, 0}, // C -> A
    {0, 0, 1, 0}  // D -> C
};

int outDegree(int page) {
    int count = 0;
    for (int j = 0; j < N; j++)
        count += adjacency[page][j];
    return count;
}

int main() {
    double rank[N], new_rank[N];

    // Step 1: initialize all ranks equally
    for (int i = 0; i < N; i++)
        rank[i] = 1.0 / N;

    for (int iter = 0; iter < MAX_ITER; iter++) {
        double diff = 0.0;

        // Step 2: compute new rank for each page
        for (int p = 0; p < N; p++) {
            double sum = 0.0;
            for (int q = 0; q < N; q++) {
                // if q links to p, add its contribution
                if (adjacency[q][p] && outDegree(q) > 0) {
                    sum += rank[q] / outDegree(q);
                }
            }
            new_rank[p] = (1.0 - D) / N + D * sum;
        }

        // Step 3: measure convergence and update ranks
        for (int i = 0; i < N; i++) {
            diff += fabs(new_rank[i] - rank[i]);
            rank[i] = new_rank[i];
        }

        if (diff < EPSILON) {
            printf("Converged after %d iterations\n", iter + 1);
            break;
        }
    }

    // Step 4: print final ranks
    for (int i = 0; i < N; i++)
        printf("PageRank[%d] = %f\n", i, rank[i]);

    return 0;
}

I want to note that the code above uses fabs, so it needs #include <math.h> and should be compiled with -lm on most systems.

Sample Input and Output

Given the adjacency structure hardcoded above (A→B,C; B→C; C→A; D→C), running the program produces output similar to:

Converged after 42 iterations
PageRank[0] = 0.365002
PageRank[1] = 0.194375
PageRank[2] = 0.403748
PageRank[3] = 0.037500

This matches my hand-computed example earlier: page C (index 2) ends up as the most important page because it collects incoming rank from three different sources.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version