The Ranking of Nodes in Networks

When you enter keywords into a Web search engine, you'll be presented with pages in descending order of relevance. This ranking is not carried out for each user for each query, but the search engine does from time to time carry out a general ranking of all the pages on the Web according to their importance. When keywords are entered, the engine searches for pages corresponding to the question asked in this complete ranked list.

A mathematical problem and numerical algorithms lie behind such ranking. Search engines use a variety of strategies to achieve this ranking, some of which are classified as trade secrets. Here, we will describe the best-known ranking algorithm, the PageRank algorithm, and the mathematical methods it uses. As we'll see later, this algorithm has many more applications than just ranking web pages. PageRank and Google are registered trademarks.

Part of this article is borrowed from , and we would like to thank the editors of the journal Matapli and the Société de Mathématiques Appliquées et Industrielles for publishing it. These results are themselves derived from the work of the authors of this article and are cited in the bibliography.

The Königsberg bridge problem was solved in 1736 by the Swiss mathematician Leonhard Euler (1707-1783), who can be considered the inventor of graph theory. The city is crossed by a river on which two islands lie. Seven bridges (the edges of the graph) link the two banks and the two islands (the nodes of the graph). The challenge was to find a route linking them without crossing the same bridge twice. The problem faced by the Web is similar in nature, but on a completely different scale. Tools had to be forged to find the right information in this enormous mass of data, to structure it and find the most important nodes. What's more, on the Web, nodes and edges are constantly changing.

The first ideas on information ranking can be traced back to the work of Derek J. de Solla Price (1922-1983) in 1965 . The aim was to evaluate scientific articles according to their number of citations. Mathematically, this is an eigenvalue problem. A matrix is constructed in which each element (i,j) is worth 1 or 0, depending on whether or not article i cites article j. It is therefore possible for element (i,j) to be worth 1, while element...