Le classement des sommets dans les réseaux

Quand on insère des mots-clés dans un moteur de recherche sur le Web, on obtient les pages par ordre décroissant de pertinence. Ce classement n’est pas effectué pour chaque utilisateur à chacune de ses requêtes, mais le moteur de recherche procède de temps en temps à un classement général de toutes les pages du Web selon leur importance. Quand des mots-clés sont introduits, le moteur recherche les pages qui correspondent à la question posée dans cette liste classée complète.

Un problème mathématique et des algorithmes numériques se cachent derrière un tel classement. Les moteurs de recherche utilisent plusieurs stratégies pour effectuer ce classement, dont certaines relèvent du secret industriel. Nous allons exposer ici l’algorithme le plus connu pour effectuer ce classement, l’ algorithme PageRank , ainsi que les méthodes mathématiques auxquelles il fait appel. Comme nous le verrons plus loin, cet algorithme a beaucoup d’autres applications que le seul classement des pages du Web. Signalons que PageRank et Google sont des marques déposées.

Une partie de cet article est empruntée à et nous tenons à remercier les éditeurs du journal Matapli ainsi que la Société de Mathématiques Appliquées et Industrielles qui le publie. Ces résultas sont eux-mêmes issus des travaux des auteurs de cet article et sont cités dans la bibliographie.

Le problème des ponts de Königsberg a été résolu en 1736 par le mathématicien suisse Leonhard Euler (1707-1783) qui peut être considéré comme l’inventeur de la théorie des graphes. Cette ville est traversée par une rivière sur laquelle se trouvent deux îles. Sept ponts (les arêtes du graphe) relient les deux rives et les deux îles (les nœuds du graphe). Il s’agissait de trouver un parcours les reliant sans passer deux fois par le même pont. Le problème rencontré par le Web est de nature semblable mais à une toute autre échelle. Il a fallu forger les outils permettant de trouver la bonne information dans cette énorme masse de données, de les structurer et de trouver les nœuds les plus importants. De plus, sur le Web, les nœuds et les arêtes changent constamment.

On peut faire remonter les premières idées sur le classement d’informations aux travaux de Derek J. de Solla Price (1922-1983) en 1965