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 . Il s’agissait alors d’évaluer les articles scientifiques selon leur nombre de citations. Mathématiquement, il s’agit d’un problème de valeurs propres. On construit une matrice dont chaque élément (i,j) vaut 1 ou 0 selon que l’article i cite ou non l’article j. Il se peut donc que l’élément (i,j) vaille 1 alors que l’élément (j,i) vaut 0. Les articles étaient ainsi classés suivant leur nombre de citations.

Le premier moteur de recherche qui classifiait automatiquement les pages du Web afin d’identifier les plus pertinentes d’entre elles a été Altavista dans les années 1997-1998. Ce moteur recherchait le nombre d’occurrences des mots-clés introduits par l’utilisateur, leur proximité et leur positionnement dans le texte. Les limites de cette méthode de sélection ont conduit à la recherche d’autres critères de classification. On est ainsi passé à des critères indépendants du contenu des pages pour passer à des méthodes de tri basées sur la popularité. C’est sur la co-citation que se base l’algorithme HITS (Hyperlink-Induced Topic Search ou Hubs and authorities) développé par Jon M. Kleinberg, professeur à Cornell University , ou l’algorithme PageRank que nous allons exposer maintenant. Nous n’en donnerons ici qu’une description simplifiée alors que le procédé complet est bien plus complexe.

En 1996, deux étudiants de l’université de Stanford, Larry Page et Sergey Brin (ils seront les fondateurs de la société Google), proposèrent un nouvel algorithme de classement des pages du Web . Selon cet algorithme, l’importance d’une page est définie par son rang dans une liste, appelé PageRank (nous conserverons ici l’appelation anglo-saxonne). À l’heure actuelle, les moteurs de recherche sur Internet ne se contentent pas de ce seul algorithme, mais utilisent simultanément de nombreux autres facteurs de classement, environ 200. Récemment, ces algorithmes ont reçu des applications dans divers domaines qui seront évoqués à la fin de cet article.

Il existe différentes façons d’appréhender intuitivement l’idée dominante de PageRank. La première d’entre elles est de savoir que cet algorithme a été bâti afin d’utiliser la structure d’un graphe pour quantifier l’importance de chacun de ses nœuds. Les utilisations de cet algorithme, en dehors du contexte du Web, font cependant toutes appel à une notion d’importance qui, selon l’application, peut prendre des significations diverses.

On peut interpréter PageRank comme un fluide circulant dans un réseau, passant d’un nœud à l’autre par ses arêtes et mettant en relation les nœuds les plus importants. Une autre interprétation consiste à le penser en termes de suffrages : un nœud acquiert les votes des autres nœuds le long des arêtes entrantes, et il donne sa voix à des nœuds plus importants, ceux qui ont intuitivement le plus de valeur. Enfin, une autre façon de penser l’algorithme est en termes de marche aléatoire à travers un réseau. Le PageRank d’un certain nœud est simplement la probabilité de se retrouver à ce nœud après être parti d’un nœud quelconque dans le réseau et en circulant pas à pas dans le graphe après avoir sélectionné une arête aléatoire à chaque nœud. C’est la simplicité et l’élégance de PageRank et le fait qu’il utilise uniquement la structure d’un graphe qui en font un outil qui peut être appliqué à d’autres réseaux.

Nous avons volontairement limité la bibliographie car elle est très vaste. On en trouvera une bonne partie dans . Un certain nombre de notions simples d’algèbre linéaire sont nécessaires pour aborder cet article (voir [AF1221]).