PageRank

In one sentence: PageRank gives each web page a score based on which other pages link to it, and a link from a page with a high score counts for more.

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

Read it out loud: “PR of p equals one minus d, divided by N, plus d times the sum, over every page q that links to p, of PR of q divided by L of q. PR of p is the score of page p. d is the damping factor, usually 0.85. N is the number of pages being ranked. The sum sign means add up one share for each page q that links to p. L of q is the number of links that leave page q.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Web page, link and graph: A web page is one page on the internet. A link is a clickable connection from one page to another. Pages and links together form a graph: each page is a vertex, and each link is an arrow from the page that contains it to the page it points to. PageRank is worked out on this graph of arrows, and the numbers of arrows in and out of each page matter.
Score and the name $PR(p)$: $PR(p)$ is read ‘PR of p’. It is the score of page $p$ , a number that says how important the page is. The letters $PR$ are only a label for the score, and $p$ names the page. So $PR(q)$ is the score of a different page, named $q$ . The scores are found by a calculation, not measured.
The sum sign $\sum$: The capital Greek letter sigma, written $\sum$ and said ‘SIG-muh’, is the sum sign. It means add up a list of terms. The small labels under it say which terms to add. Here $\sum_{q \to p}$ means add one term for every page $q$ that links to $p$ . If three pages link to $p$ , the sum has three terms.
Arrows $q \to p$ and $L(q)$: The arrow $q \to p$ means page $q$ contains a link to page $p$ . The notation $L(q)$ , read ‘L of q’, is the number of links that leave page $q$ . Page $q$ shares its score among these $L(q)$ links, so each linked page receives one share. A page with 2 outgoing links gives each target half of its score-share.
Damping factor $d$: The damping factor $d$ is usually 0.85. It is a fraction between 0 and 1, and $0.85$ means 85%. It is the chance that a random visitor follows a link on the current page. The chance that the visitor jumps to some other page at random is $1 - d$ , which is 0.15 when $d = 0.85$ .
Iteration: repeat until the scores settle: An iteration is one round of the same calculation. Each round uses the scores from the round before, and the scores change less each time. When they hardly change, they have settled. Repetition is needed because each page’s score depends on the scores of the pages that link to it, and those scores are themselves still being worked out.

What each symbol means

Symbol	Meaning
$PR(p)$	The PageRank of page $p$ : its score, which says how important the page is. When all the scores are scaled to add up to 1, each score is a number between 0 and 1. The example scores after one round are 0.3333, 0.1917 and 0.4750.
$N$	The total number of pages in the set being ranked. It is a plain count with no unit. The example has $N = 3$ pages, called A, B and C, so the starting share for each page is $\frac{1}{3}$ .
$d$	The damping factor, usually 0.85. It is the chance that a random visitor follows a link instead of jumping to a random page. It is a fraction with no unit, and the example uses $d = 0.85$ , which means 85%.
$q \to p$	The arrow notation under the sum sign: the sum runs over every page $q$ that links to page $p$ . These are the incoming links of $p$ . The arrow is not a number, but it tells you which pages to add up.
$PR(q)$	The current score of a page $q$ that links to $p$ . It comes from the previous round of the calculation, and when the scores add up to 1, it is a number between 0 and 1. In the example, the starting score of each page is $\frac{1}{3}$ .
$L(q)$	The number of outgoing links on page $q$ : the links that leave $q$ and point to other pages. It is a count with no unit. In the example $L(A) = 2$ , because page A links to pages B and C.

The formula piece by piece

$\frac{PR(q)}{L(q)}$: One page’s share. Page $q$ has a score $PR(q)$ , and it splits this score equally among its $L(q)$ outgoing links. Each linked page receives one share, $\frac{PR(q)}{L(q)}$ . In the example, page A has a score of $\frac{1}{3}$ and 2 links, so each link carries $\frac{1/3}{2} = \frac{1}{6}$ .
$\sum_{q \to p} \frac{PR(q)}{L(q)}$: Add up the shares from all the incoming links. The sum sign adds one share for each page that links to $p$ . The total is the link part of $p$ ’s score: the votes that page $p$ receives from the other pages.
$d \sum_{q \to p} \frac{PR(q)}{L(q)}$: Keep only a fraction $d$ of the link total. Multiplying by $d = 0.85$ keeps 85% of the incoming shares, which is the part of the score that comes from following links. The rest is covered by the random-jump share in the next piece.
$\frac{1 - d}{N}$: The random-jump share. A random visitor who does not follow a link jumps to any page, so every one of the $N$ pages receives $\frac{1 - d}{N}$ . With $d = 0.85$ and 3 pages, it is $0.15 \div 3 = 0.05$ . Every page gets this share, so no page can end up with a score of zero.
$PR(p) = \frac{1 - d}{N} + d \sum_{q \to p} \frac{PR(q)}{L(q)}$: The whole formula as one sentence: the score of page $p$ is the random-jump share, plus $d$ times the shares of score that arrive from every page that links to $p$ .

What the formula is doing, and why

The idea is a vote with weight. A link from page $q$ to page $p$ counts as a vote for $p$ . A vote from a page with a high score counts for more, because that page’s score is passed on. A page that links to many pages spreads its score across them, so each link carries a smaller share.

Why divide by $L(q)$ ? Page $q$ has one score to give away. Its $L(q)$ outgoing links share that score equally, so each link carries $\frac{PR(q)}{L(q)}$ . Adding these shares over every page that links to $p$ gives the link part of $p$ ’s score. A page with many outgoing links gives each target only a small share.

Why the damping factor? The damping factor $d$ , usually 0.85, mixes in a small base. A random visitor follows a link with probability $d$ and jumps to a random page with probability $1 - d$ . The term $\frac{1 - d}{N}$ is the share that comes from those random jumps. It reaches every page, so no page is left with a score of zero, and the process cannot trap all the score in a few pages.

Why repeat? The formula uses the scores of other pages, and those scores are not known at the start. So you start every page at $\frac{1}{N}$ , apply the formula to all the pages, and repeat. The scores change less each round, and they settle. The method comes from the 1998 paper by Brin and Page cited below.

When does it apply? This version assumes that each page has at least one outgoing link. A page with no outgoing links is a dead end, and its score would leak out of the system. Practical versions handle such pages in other ways, which this page does not cover.

An everyday picture

Think of a town where a recommendation counts for more when it comes from a respected person. A recommendation from a well-regarded neighbor is worth more than one from a stranger. A neighbor who recommends ten shops gives each shop only a tenth of their weight, because the weight is shared among all the recommendations. PageRank is the same idea with web pages: a link is a recommendation, and a page’s score is the weight it carries.

Worked example: Three pages that link to each other

A tiny web has $N = 3$ pages: A, B and C. Page A links to B and C, page B links to C, and page C links to A. So $L(A) = 2$ , $L(B) = 1$ and $L(C) = 1$ . Start every page at $\frac{1}{3}$ , which is about 0.3333, so the three scores add up to 1. Use $d = 0.85$ and work through one round of updates. The pages are made up for this example.

Find the random-jump share. The base term for every page is $\frac{1 - d}{N} = \frac{0.15}{3} = 0.05$ . The number 0.15 is $1 - 0.85$ , the chance that a visitor jumps to a random page. Dividing by $N = 3$ gives each page an equal share of that jumping.
Update page A. Only page C links to A, and C has one outgoing link, so C passes its whole score of $\frac{1}{3}$ to A. Then $PR(A) = 0.05 + 0.85 \times \frac{1/3}{1} = 0.05 + 0.2833 = 0.3333$ . The factor 0.85 keeps 85% of the score that arrives through links.
Update page B. Only page A links to B. A has two outgoing links, so each one carries $\frac{1/3}{2} = \frac{1}{6}$ , which is about 0.1667. Then $PR(B) = 0.05 + 0.85 \times \frac{1}{6} = 0.05 + 0.1417 = 0.1917$ .
Update page C. Two pages link to C. Page A gives C one share of $\frac{1}{6}$ , as above. Page B has one link, so it gives C its whole score of $\frac{1}{3}$ . The two incoming shares add up to $\frac{1}{6} + \frac{1}{3} = 0.5$ . Then $PR(C) = 0.05 + 0.85 \times 0.5 = 0.05 + 0.425 = 0.475$ .
Check the total. The new scores are $0.3333 + 0.1917 + 0.4750 = 1.0000$ . They still add up to 1, so no score was lost in this round. A total that drifted away from 1 would be a sign of a mistake.
Read the result. Page C has the highest score, 0.475, because two pages link to it. Page A has 0.3333. Page B has the lowest score, 0.1917, because only one page links to it, and that page splits its own score between two links.
Repeat. The next round starts from these new scores and repeats the same updates. The scores keep changing, but by less each round, until they stop changing much. This repetition is how PageRank is found for a real web of many pages.

Answer: After one round, page C has the highest score, 0.475, because two pages vote for it. Page A has 0.3333, and page B has 0.1917. The next round starts from these new scores, and they keep changing until they settle.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Forgetting to divide by $L(q)$ . A page with many outgoing links gives each target a smaller share, not its full score.
Using $d$ where the base term belongs. The base term is $\frac{1 - d}{N}$ , the random-jump share, which is $0.15 \div 3 = 0.05$ when $d = 0.85$ and $N = 3$ . Writing $d$ instead gives a far larger base.
Summing over the outgoing links of $p$ . The sum runs over the pages that link to $p$ , which are the incoming links, not the links that leave $p$ .
Expecting one round to give the final scores. Repeat the update until the scores stop changing.

Where you will meet it

Ranking web pages in search, the method described in the 1998 Brin and Page paper on a large-scale web search engine.
Ranking scientific papers by their citation links, where a paper cited by highly ranked papers scores higher.
Finding influential accounts in social networks, using the same link-based scores.
Teaching graph theory and random processes, since PageRank is the long-run share of time a random surfer spends on each page.

Questions people ask

Why is $d$ set to 0.85?

It is the value most descriptions use. It means a random surfer follows links about 85% of the time and jumps to a random page the rest of the time. Other values work, and the scores shift a little when $d$ changes.

Do the scores have to add up to 1?

With this version of the formula, yes, as the example shows. Some texts write the base term as $1 - d$ with no division by $N$ , and then the scores add up to $N$ instead.

What about a page with no outgoing links?

It is called a dangling page, or a dead end. Its score would leak out of the system, so the scores would no longer add up to 1. Practical versions share such a page’s score across all the pages. This page does not cover that case in detail.

TF-IDF: TF-IDF gives a word a high score in a document when the word appears often there but rarely across all the other documents.
Complete Graph Edges: A complete graph joins every pair of points with one line, and this formula counts how many lines that takes, given how many points there are.
Euler's Formula for Planar Graphs: Euler’s formula says that if you draw a connected network on a flat sheet with no crossing lines, then corners minus lines plus regions always comes to 2.