Page ranking algorithm

PageRank is a link analysis algorithm (Brin and Page, Google) that ranks web pages by their importance, computed from the hyperlink structure of the web. The idea: a page is important if many important pages link to it. A link from page A to page B is like a "vote" by A for B; votes of important pages count more, and a page's vote is shared among all its outgoing links.

Formula

PR(P) = (1 − d) + d × Σ [ PR(Tᵢ) / C(Tᵢ) ]

• Tᵢ = the pages linking to P (in-links)
• C(Tᵢ) = number of outgoing links of Tᵢ
• d = damping factor (usually 0.85): the probability that a random surfer follows a link; 1 − d is the chance of jumping to a random page.

PageRank is the probability of a random surfer being on the page; it is computed iteratively until the values converge.

Example

Pages A, B, C with links A → B, A → C, B → C, C → A. Start with PR = 1 for all; d = 0.85.

• PR(A) = 0.15 + 0.85·PR(C)/1
• PR(B) = 0.15 + 0.85·PR(A)/2
• PR(C) = 0.15 + 0.85·(PR(A)/2 + PR(B)/1)

(Each iteration uses the values from the previous one; the sum is always 3, the number of pages.) C and A are the more important pages.

Notes

Rank sinks (groups of pages that link only to each other) are handled by the damping factor, i.e. the random jump; dangling pages (no out-links) are usually treated as linking to all pages, so their rank is spread evenly. PageRank is query-independent and is combined with content relevance in a search engine. It is a web structure mining technique; HITS (hubs and authorities) is another.