Algorithms

PageRank

PageRank scores a page by who links to it, and how much score those pages have to give. Run it enough times and the numbers settle.

The key idea

Score flows along links

A page hands its score out evenly across the links it has.
A page collects more when more pages point at it.
Damping gives every page a small share for free, so score cannot pool in a closed loop.

Run the round enough times and the numbers stop moving.

Strategy

Iterative approximation

Start every page equal, work out all the scores again from the current ones, and repeat until they stop moving.

Seed: give every page the same starting score.
Spread: each page splits its score evenly among the pages it links to.
Repeat: run another round on the new scores until they settle.

Every node starts with the same score. Press Step to run one round and watch the scores move toward their final values.

Purpose

Score how important each page in a link graph is.

Input

A link map as map[string][]string, a damping factor, and how many rounds to run.

Output

A score for every page as map[string]float64, all of them adding up to 1.

Constraints

Every page needs at least one outgoing link, since a page with none would divide by zero.
The damping factor sits between 0 and 1, and 0.85 is the value from the original paper.
Scores are relative, so the ranking between pages is what means anything.

How PageRank works

A map from each page to the pages it links to, plus a damping factor.

0.85 is the value from the original paper. It is the share of a page's score that flows along its links, with the rest spread evenly over everything.

links := map[string][]string{
    "A": {"B", "C"}, // A links to B and C
    "B": {"C"},
    "C": {"A"},
    "D": {"C"},
}

d := 0.85 // damping factor

Walk through it

Start every page equal

Two steps before any rounds run.

Every page starts with the same score, and they add up to 1. That total never changes, which is what makes the scores comparable.

n := float64(len(nodes))

// Everyone starts equal.
for _, id := range nodes {
    rank[id] = 1 / n
}

Spread each score along the links

The rule applied to each page, once per round.

A page hands out its score evenly across its outgoing links, so a link from a page with two links is worth more than one from a page with fifty.

Damping is what stops a small group of pages linking only to each other from hoarding all the score.

// A page splits its score evenly among everything it links to.
sum += rank[from] / float64(len(links[from]))

// Then damping decides how much of the score is earned
// from links, and how much everyone gets for free.
next[id] = (1-d)/n + d*sum

Run the next round on the new scores

Each round computes every page's new score from the previous round's numbers, then swaps them in.

Building a separate next map matters. Updating in place would let a page computed early in the round feed its new score into one computed later, and the result would depend on map order.

for i := 0; i < iters; i++ {
    next := make(map[string]float64, len(nodes))
    for _, id := range nodes {
        // ... add up what links into id
    }
    rank = next // swap in the new round
}

What comes out

A score for every page, all adding up to 1.

In the example, C wins because three pages link to it. D is last because nothing links to D at all, so it only ever gets the damping share.

rank := pageRank(links, 0.85, 20)

The whole program main.go Show

package main

import (
    "fmt"
    "sort"
)

// pageRank runs the iterative approximation for a fixed number of rounds.
// d is the damping factor: how much of a page's score is earned from links,
// with the rest handed out evenly to everyone.
func pageRank(links map[string][]string, d float64, rounds int) map[string]float64 {
    var nodes []string
    for id := range links {
        nodes = append(nodes, id)
    }
    sort.Strings(nodes)

    n := float64(len(nodes))
    rank := make(map[string]float64, len(nodes))

    // Everyone starts equal.
    for _, id := range nodes {
        rank[id] = 1 / n
    }

    for i := 0; i < rounds; i++ {
        next := make(map[string]float64, len(nodes))
        for _, id := range nodes {
            sum := 0.0
            for from, outs := range links {
                for _, to := range outs {
                    if to == id {
                        // A page splits its score evenly among
                        // everything it links to.
                        sum += rank[from] / float64(len(outs))
                    }
                }
            }
            next[id] = (1-d)/n + d*sum
        }
        rank = next // swap in the new round
    }
    return rank
}

func main() {
    links := map[string][]string{
        "A": {"B", "C"}, // A links to B and C
        "B": {"C"},
        "C": {"A"},
        "D": {"C"},
    }

    rank := pageRank(links, 0.85, 20)

    var ids []string
    for id := range rank {
        ids = append(ids, id)
    }
    sort.Strings(ids)

    total := 0.0
    for _, id := range ids {
        fmt.Printf("%s %.3f\n", id, rank[id])
        total += rank[id]
    }
    fmt.Printf("total %.3f\n", total)
}

Four pages after twenty rounds.

Terminal

$ go run pagerank.go
A 0.373
B 0.196
C 0.394
D 0.038
total 1.000

When to stop

A fixed round count always ends, and is what the code above uses.

The better stopping rule is to watch how far the scores moved this round and stop once that is small enough. The scores converge, so that threshold is always reached.

// Either run a fixed number of rounds ...
for i := 0; i < iters; i++ {

// ... or stop once the numbers stop moving.
if delta < 1e-6 {
    break
}

Cost

Case	Time	When it happens
Per round	O(V + E)	Every page once, plus every link once.
Total	O(k(V + E))	k rounds. In practice a few dozen is enough, whatever the size of the graph.
Space	O(V)	Two score maps, the current round and the next.

Previous Manhattan Distance Next Topic bufio