A Short History of Iterative Ranking Algorithms
Google’s PageRank, discovered in 1998, has been instrumental in the success of Google’s search engine. It is used to determine the importance of a website through analyzing the hyperlinks that point to it along with their value. An important component of PageRank is that it constantly re-evaluates a website as the importance of other websites varies. This is known as iterative ranking algorithms and they are vital to network theory.
When thinking about Google’s PageRank, it may be too easy to forget that their approach was not completely new. In his 2010 paper, Italian computer scientist Massimo Franceschet points out that iterative ranking algorithms go as far back as the 1940s.
In 1941, the Harvard economist Wassily Leontief published a paper where he divided the economy of a country into sectors (industries) that supply and receive resources from each other, just in varying amounts. The question then became how to value each sector once they are highly integrated? The answer was to develop an iterative approach to value each sector that was based on the importance of the sectors that supplied it. Leontief was awarded the Nobel Prize in economics in 1973 for this work.
In 1965, Charles H Hubbell at UC Santa Barbara published a paper that detailed the method for determining the importance of people based upon the importance of the people who endorsed them.
The most fascinating aspect of Franceschet’s paper, however, was when he detailed the fact that Professor Jon Kleinberg developed an almost identical approach to PageRank, which predated Google’s PageRank by a few years. The name if his algorithm was Hypertext Induced Topic Search (HITS). Webpages were considered as hubs and authorities requiring an iterative approach to solve.
PageRank owes a lot of its success to the research and works created by these great thinkers. It is by standing on the shoulders of giants that others can build on what has already been discovered.
Sources:
http://arxiv.org/pdf/1002.2858v3.pdf
http://www.technologyreview.com/view/417529/scientist-finds-pagerank-type-algorithm-from-the-1940s/