PageRank ranks web pages by imagining a surfer clicking links at random
Google's founding algorithm pictures an aimless web user who follows links, and every so often gets bored and jumps somewhere random. The share of time that surfer spends on each page becomes its score. The same maths had been proposed in 1895 by Edmund Landau to decide the winner of a chess tournament.
Larry Page and Sergey Brin built PageRank at Stanford in 1996, trying to outdo then-dominant search engines such as AltaVista. The idea treats each hyperlink as a vote, but votes are weighted: a link from an important page counts for more, and a page splits its influence evenly among all its outgoing links. Because a page's score depends on the scores of pages pointing to it, the definition is recursive, and it is computed by repeated passes that gradually settle on stable values.
A four-page toy example shows the mechanics. Start each page at 0.25. If B links to A and C, C links only to A, and D links to all three, then A collects half of B's share, all of C's, and a third of D's, reaching about 0.458 after one round. A damping factor, usually set near 0.85, captures the probability that the surfer keeps clicking rather than teleporting to a random page, and a page with no outgoing links simply sends the surfer elsewhere at random. Mathematically the whole thing is a Markov chain whose states are pages.
Page and Brin's best-known paper muddled two versions of the formula, wrongly claiming that one of them produced a probability distribution. The idea also had predecessors: Eugene Garfield's citation analysis of the 1950s, journal-ranking work in 1976, and Robin Li's RankDex search engine of 1996, which Li later used when founding Baidu and which Page cited in his patents.
The patent belonged to Stanford, not Google, which licensed it exclusively. Stanford took 1.8 million Google shares in return and sold them in 2005 for $336 million. All PageRank patents had expired by September 2019, and Google now combines it with many other ranking signals.
Source: PageRank
