Eigenvectors and PageRank

Research poster · Linear algebra, Python, NumPy

How did Google decide which web pages matter? The answer turns out to be an eigenvector problem. For this project I researched Google’s PageRank algorithm, explored the matrix and eigenvector methods behind it, and implemented a simplified version in Python using NumPy to model the relationships between webpages with matrix operations.

The idea

A page is important if important pages link to it. That sounds circular, but we can turn it into a rule: every page splits its own rank equally between the pages it links to, and a page’s new rank is the total it receives. Repeat that and the ranks settle down.

There is one extra ingredient. With probability d (the damping factor) a surfer follows a link, and otherwise jumps to a random page. This keeps rank from getting trapped and makes the process settle on one answer.

Try it

Six pages, with arrows showing which pages link to which. Bigger circles have higher rank. Drag the iterations slider, or press Play, to watch rank flow along the links, then change the damping factor to see how the result shifts.

Notice that page C ends up on top: it is linked to by A, B, E and F, so lots of rank flows into it. Pages B and F end up lowest, because each one only receives a share of a single other page’s rank.

Why it’s an eigenvector

One step of the process can be written as a matrix multiplication. Put the link structure in a matrix L, where column j splits page j’s rank between the pages it links to. Then with N pages and rank vector r:

r′ = (1 − d)/N + d · L r

When the ranks stop changing, r′ = r, which means r is an eigenvector with eigenvalue 1 of the matrix that describes one step. Repeatedly multiplying by that matrix (called power iteration) is a way of finding it, and that is exactly what the slider above is doing.

A sketch in NumPy

The whole idea fits in a few lines. This version assumes every page links to at least one other page.

import numpy as np

def pagerank(links, d=0.85, iters=100):
    # links[i] is the list of pages that page i links to
    n = len(links)
    L = np.zeros((n, n))
    for i, outs in enumerate(links):
        for j in outs:
            L[j, i] = 1 / len(outs)   # column i shares page i's rank
    r = np.full(n, 1 / n)             # start with equal rank
    for _ in range(iters):
        r = (1 - d) / n + d * (L @ r)
    return r