Page Rank Algorithm and the Kleinberg's HITS algorithm

The most famous quality measure is PageRank [221], discussed earlier, which builds on the intuition that a page which is cited by many other pages is likely to be of significant quality. The insight of PageRank is that the obvious way to subvert that model is to set up a load of dummy pages to cite the page which one wanted to boost. But if a page is cited by many other pages which themselves have a high PageRank, then it is likely to be of high quality. The PageRank method has another intuitive characterisation that at first sight seems to have nothing to do with quality: it is the probability that a random surfer will reach the page [47]. The value of these measures is reflected in the success of Google in terms of longevity, market value and share of the search engine market. Further, other measures of quality exploit the idea of random walks [181], sometimes explicitly extending the ideas underlying PageRank [235].

A related idea is Kleinberg's HITS algorithm, based on the idea of impact factors from bibliometrics [171]. The original explanation of impact factors for academic journals was that one could look at the number of citations to a journal in the context of a discipline as a whole. One can then model the influence weight of a journal as a function of the influence weights of citing journals and the fraction of the citations of those citing journals that cite the journal in question. Analogous reasoning establishes an algorithm for measuring webpage quality, both in terms of its authority value and its hub value.

The page rank algorithm is very similar to an algorithm for ranking research papers by counting the number of other papers referencing them.