Chapitre 5 — PageRank, une manière d’estimer l’importance des pages web

Lorsqu’un chercheur veut publier une communication dans une revue spécialisée, il doit passer par des comités de lecture qui évaluent la qualité de son travail selon des critères précis. Pour passer à la télévision ou dans un journal, il suffit d’avoir une bonne histoire à raconter.

Surfer sur internet c’est comme pour le sexe : tout le monde se vante de faire plus qu’il ne fait. Mais pour le cas d’Internet, on se vante bien plus.

Omnes Viae ad Googlem ducent

Ce chapitre va essayer de poser les bases à la fois intuitives, axiomatiques et théoriques des méthodes de classement de type PageRank, mises en valeur par le célèbre moteur de recherche Google [Goo98]. Ce travail fastidieux de survey m’a été grandement facilité par Mohamed Bouklit, qui en débroussaillant, avec l’aide d’Alain Jean-Marie, le terrain avant moi [Bou01, BJ02], m’a permis d’avoir toutes les références nécessaires.

Il existe dejà un certain nombre de surveys à propos du PageRank (cf [BGS02, BGS03, LM04]), mais nous avons jugé ce chapitre nécessaire, car il présente l’ensemble des PageRanks sous un même point de vue, celui de l’interprétation stochastique, et met en évidence quelques résultats de convergence qu’on ne trouve pas ailleurs¹.

5.1 Une aiguille dans un océan de foin…

On trouve (de) tout sur le web, à peu près tous les usagers du réseau sont d’accord là-dessus. Savoir si l’information que je recherche existe sur la toile n’est plus crucial. De nos jours, le problème est devenu : Comment trouver la page que je recherche ?

• En connaissant, d’une manière ou d’une autre, l’adresse en question. Par exemple, en lisant sur un paquet de farine l’adresse d’un site qui donne des recettes de cuisine, en recevant un mail d’un ami qui recommande d’aller visiter une adresse web, ou en ayant l’adresse dans ses Bookmarks…
• En naviguant (surfant) sur le web, à partir d’une adresse connue. Si par exemple je recherche une page qui parle des ratons laveurs, et si je connais un site de zoologie, partir de ce site peut être une bonne façon de trouver la page que je cherche.
• En utilisant un moteur de recherche. Celui-ci, en échange d’une requête, c’est-à-dire d’un ensemble de mots essayant de décrire plus ou moins précisément ce que je recherche, va nous donner une liste de pages susceptibles de répondre à cette requête. D’après [LG99], l’utilisation des moteurs de recherche concerne 85% des internautes.

Tout le problème des moteurs de recherche est d’arriver à renvoyer les pages que l’utilisateur recherche. Seulement, les réponses à une requête donnée se comptent souvent par centaines, voire par milliers², comme le montre le Tableau 5.1. D’un autre côté, les utilisateurs se lassent vite, et on estime que 90% des utilisateurs ne dépassent pas la première page de résultats.

Le but des moteurs est donc d’arriver à afficher dans les dix à vingt premières réponses les documents répondant le mieux à la question posée. Dans la pratique, aucune méthode de tri n’est parfaite, mais leur variété offre aux moteurs la possibilité de les combiner pour mieux affiner leurs résultats. Les principales méthodes de tri sont les suivantes :

Tri par pertinence

Le tri par pertinence est la méthode de tri la plus ancienne et la plus utilisée. Elle est basée sur le nombre d’occurrences des termes de la recherche dans les pages, de leur proximité, de leur place dans le texte [Sal89, YL95]… Malheureusement, cette méthode présente l’inconvénient d’être facile à détourner par des auteurs désireux de placer leurs pages en tête de liste. Pour cela, il suffit de surcharger la page de mots importants, soit dans l’en-tête, soit en lettres invisibles à l’intérieur du corps de la page.

Étude de l’URL

On peut également donner de l’importance à une page en fonction de son URL. Par exemple, selon le contexte, les URLs appartenant au Top Level Domain http:.com pourraient avoir plus d’importance que les autres, de même que les URLs contenant la chaîne de caractère http:home [Li+00]. Il a également été suggéré que les URLs de faible hauteur dans l’arbre-cluster étaient plus importantes que les autres [CGP98].

Liens entrants

Le comptage de citations consiste à attribuer aux pages une importance proportionnelle aux nombres de liens vers cette page connus. Cette méthode a largement été utilisée en scientométrie pour évaluer l’importance des publications [Pri63].

PageRank

Comme nous allons le voir, le PageRank est une sorte de généralisation récursive du comptage de citations.

5.2 Les deux axiomes du PageRank

Le PageRank, introduit par Brin et al. en 1998 [Pag+98], est la méthode de classement qui a fait la spécificité du moteur de recherche Google [Goo98]. Il s’agit en fait d’une adaptation au Web de diverses méthodes introduites par les scientomètres³ depuis les années 1950. Deux méthodes scientométriques en particulier doivent être évoquées :

Le comptage de citations

En 1963, Price publie Little Science, Big Science [Pri63]. Dans ce livre, premier ouvrage majeur traitant de ce qui deviendra plus tard la scientométrie, il propose de mesurer la qualité de la production scientifique grâce, entre autres, à une technique très simple, le comptage de citations : une des manières de mesurer la qualité d’une publication est de dénombrer le nombre de fois où cette publication est citée.

Modélisation markovienne

Les chaînes de Markov, décrites au Chapitre 4, permettent non seulement de jouer au Monopoly (marque déposée), mais aussi de modéliser l’évolution d’une population répartie entre plusieurs états à condition d’arriver à estimer les probabilités de transition entre états. Par exemple, Goffman propose en 1971 l’étude de l’évolution de la recherche dans différents sous-domaines de la logique à l’aide de chaînes de Markov [Gof71].

Voyons maintenant comment Brin et al. ont adapté ces concepts à l’estimation de l’importance des pages Web.

5.2.1 Une page importante est pointée par des pages importantes

Transposée telle quelle aux graphes du Web, la méthode du comptage de citations revient à dire que l’importance d’une page est proportionnelle à son degré entrant, c’est-à-dire au nombre de pages qui la citent à travers un hyperlien :

où signifie qui pointe sur .

Bien que cette mesure puisse effectivement être utilisée pour estimer l’importance des pages [CGP98], elle se trouve en partie dénaturée par l’inexistence d’un contrôle de qualité. En effet, lorsqu’un chercheur veut publier une communication dans une revue spécialisée, il doit passer par des comités de lecture qui évaluent la qualité de son travail selon des critères précis. À cause de cela, le fait même d’être publié donne un minimum d’importance aux articles considérés, et on a une certaine garantie que les citations que reçoit un papier ne sont pas complètement fantaisistes. Dans le cas du Web, ce garde-fou n’existe pas : à cause du faible coût intellectuel et matériel d’une page Web, n’importe qui peut pointer vers n’importe quoi sans que cela ait forcément un véritable sens⁴. Par exemple, pourquoi ne pas créer une multitude de pages vides de sens, mais qui me citent par des hyperliens, pour augmenter à l’envi ma propre importance ?

Brin et al. proposent de contrer ce problème par une description récursive de l’importance : Qu’est-ce qu’une page importante ? C’est une page pointée par des pages importantes. Concrètement, si une page est pointée par pages , l’importance de doit être définie par :

Il nous reste à définir et résoudre Équation (5.2).

5.2.2 Le surfeur aléatoire : le hasard fait bien les choses

Une image d’Épinal du Web est le principe de la navigation par hyperliens : pour trouver ce qu’il cherche, l’internaute va naviguer de page en page et de clic en clic jusqu’à l’arrivée à bon port. Bien sûr, ce n’est pas ce qui se passe en pratique, autant pour des raisons techniques (il n’est pas toujours possible de rejoindre une page à partir d’une page ) que sociales (utilisation des moteurs de recherche, lassitude de l’internaute…)⁵.

Brin et al. ont eu pour idée de modéliser le comportement de l’internaute cliqueur par une chaîne de Markov. Tout ce qu’il fallait, c’était trouver les probabilités de transitions d’une page à une autre. Une des manières les plus simples de voir les choses est de considérer qu’une fois sur une page donnée, l’internaute va cliquer de manière équiprobable sur un des liens contenu dans cette page :

Ceci est la base du modèle du surfeur aléatoire. Pour Brin et al., étant donné que les graphes du Web reflètent une architecture volontaire et réfléchie, les pages intéressantes doivent être structurellement facile d’accès, tout comme une ville est d’autant plus accessible par le réseau routier qu’elle est importante. Donc, comme le surfeur aléatoire se laisse guider par le réseau des hyperliens, statistiquement, il devrait tomber d’autant plus souvent sur une page que celle-ci est importante. D’où l’idée de définir l’importance d’une page Web par la probabilité asymptotique de se trouver sur cette page dans le modèle du surfeur aléatoire.

5.2.3 Cohérence des deux interprétations

Maintenant que nous avons défini deux façons de considérer l’importance d’une page, constatons qu’elles se recoupent et désignent le même phénomène : en effet, dans le modèle du surfeur aléatoire, il est possible d’estimer la probabilité asymptotique de présence sur une page en fonction de celles des pages qui pointent vers :

On peut constater qu’on a bien une relation de transfert d’importance comme celle définie par l’Équation (5.2), et que l’Équation (5.4) obéit en plus à un principe de conservation : une page donnée transmet l’intégralité de son importance, celle-ci étant équitablement répartie entre les différentes pages pointées. La probabilité, vue comme une importance, se transmet donc à travers les hyperliens à la manière d’un flot.

5.3 Les modèles classiques

Bien qu’on parle souvent du PageRank au singulier, il existe en réalité une multitude de PageRank(s). Nous allons voir ici comment, à partir du modèle théorique du surfeur aléatoire que nous venons de décrire, plusieurs variations ont été introduites afin de s’adapter à la réalité des graphes du Web. Ce travail de survey a déjà été effectué pour l’ensemble des PageRank(s) issus de processus rendus explicitement stochastiques [BGS02, BGS03, LM04], mais nous voulons ici prendre également en compte les modèles sous-stochastiques.

5.3.1 Cas idéal

Dans le cas où le graphe du Web que l’on veut étudier est apériodique et fortement connecté, les principes vus dans la Section 5.2 s’appliquent directement : en effet, il s’agit de rechercher une distribution de probabilité sur vérifiant :

Ceci revient à trouver la distribution asymptotique de la chaîne de Markov homogène dont la matrice de transition est :

Comme vu lors de la Section 4.3, la suite de distribution

initiée par une distribution de probabilité quelconque ⁶, converge géométriquement vers l’unique distribution vérifiant

c’est-à-dire vérifiant la relation Équation (5.5).

Cette distribution de probabilité est appelée PageRank.

5.3.2 Renormalisation simple

La plupart du temps, un graphe du Web n’est pas fortement connexe. Il existe en particulier un nombre non négligeable de pages sans lien, qui sont soit des pages ne contenant effectivement aucun lien, soit tout simplement des pages connues, mais non indexées. Les lignes de correspondant à ces pages sans lien ne contiennent donc que des , et est donc strictement sous-stochastique. En conséquent, la suite des va converger⁷ vers un vecteur nul en dehors des éventuelles composantes fortement connexes récurrentes sur lesquelles est stochastique⁸. Pour éviter ce problème, on pourrait envisager d’enlever récursivement toutes les pages sans liens jusqu’à obtenir une matrice stochastique, avec l’inconvénient de considérer un graphe plus petit que le graphe initial. Une autre approche, proposée par [Pag+98], consiste à renormaliser à chaque itération :

Ce procédé itératif est une méthode de la puissance ([Ste94]), on sait donc qu’il va converger vers un vecteur propre associé à la plus grande valeur propre de . Deux cas sont alors à considérer :

• Si la matrice est sous-irréductible, alors sa valeur propre maximale est strictement inférieure à 1. D’après le Théorème 4.6⁹, l’espace propre associé est de dimension , où est le nombre de composantes pseudo-récurrentes, et son support est celui engendré par l’union des filtres des composantes pseudo-récurrentes. Dans le cas particulier où est pseudo-irréductible, l’espace propre est une droite, et il existe un vecteur propre associé strictement positif : grâce à la renormalisation, tout se passe alors comme dans le cas d’une matrice stochastique irréductible.

• Si la matrice n’est pas sous-irréductible, contient au moins une composante fortement connexe récurrente sur laquelle est stochastique. La valeur propre maximale de est donc , ce qui signifie que la renormalisation ne va rien changer au résultat initial : le vecteur propre sera une combinaison linéaire des vecteurs propres sur les différentes composantes fortement connexes sur lesquelles est stochastique¹⁰.

Processus stochastique équivalent

L’utilisation de matrices sous-stochastiques fait que l’on perd l’interprétation naturelle du surfeur aléatoire. Il est cependant parfois possible de compléter la matrice en une matrice stochastique équivalente, c’est-à-dire de trouver une matrice stochastique vérifiant :

• si , avec maximal, alors

S’il existe un unique vecteur de probabilité maximal pour , la plus simple façon de définir une telle matrice est de considérer le défaut stochastique de : si est sous-stochastique, on définit le défaut stochastique de comme étant le vecteur . La matrice

est bien une matrice stochastique¹¹ supérieure à , et il est facile de voir que est une distribution de probabilité homogène à , donc égale à .

La matrice présente l’avantage de donner une interprétation stochastique au procédé de renormalisation simple : asymptotiquement, le surfeur aléatoire suit à chaque étape un lien suivant les probabilités données par . Quand il ne sait pas quoi faire, il zappe vers une autre page selon la distribution de probabilité qui est vecteur propre maximal de .

Par contre, dès que l’espace propre maximal a une dimension supérieure à , le problème est délicat, voire très délicat dans le cas de composantes pseudo-récurrentes dont les filtres ont une intersection non nulle. Nous limiterons par conséquent notre étude des processus stochastiques équivalents aux cas d’unicité du vecteur propre maximal.

5.3.3 Complétion stochastique

Afin de remplacer par une matrice stochastique, et d’éviter à travers une simple renormalisation d’établir un processus stochastique équivalent non contrôlé, une idée naturelle est d’ajouter des transitions aux pages sans liens. Une des méthodes possibles consiste à modéliser l’emploi de la touche Back, et sera l’objet du Chapitre 6. Une autre méthode, proposée¹² initialement par [Pag+98] (sous la forme de l’Algorithme 5.1) et étudiée entre autres par [LM04], consiste à définir une distribution de probabilité par défaut sur , et à s’en servir pour modéliser le comportement du surfeur aléatoire quand il arrive sur une page sans lien. Concrètement, on va remplacer dans chaque ligne nulle (qui correspond donc à une page sans lien) par la ligne .

Ce procédé peut se généraliser pour compléter toute matrice sous-stochastique : La complétion par de est alors la matrice stochastique

Choix de et interprétation

représente le comportement du surfeur aléatoire lorsque ne précise pas où il doit aller, c’est-à-dire tous les changements de page qui ne sont pas dûs à l’usage des hyperliens (adresse tapée manuellement, Bookmarks, requête dans un moteur de recherche…). Généralement, on choisit pour la distribution uniforme :

qui représente un zap n’importe où et au hasard sur le Web connu.

Il a également été proposé de «personnaliser» , notamment par [Pag+98]. Par exemple, il est possible de se restreindre aux pages d’accueil des sites. D’une part, cela évite de donner implicitement aux sites une mesure partielle d’importance proportionnelle au nombre de pages crawlées (voir Section 7.5). D’autre part, cela obéit à une certaine intuition naturelle : quand on rompt la navigation par hyperliens pour zapper sur autre chose, il est probable qu’on va commencer par une page d’accueil. Cette intuition est confirmée par de nombreuses études qui démontrent l’existence de pages qui jouent le rôle de «hubs» pour les utilisateurs réels [CP95, Kle98, Mil+04, WM04].

Irréductibilité de

On dira d’une distribution de probabilité qu’elle est recouvrante si son support vérifie . C’est une condition naturelle à imposer à toute distribution de zap, puisqu’elle garantit que toutes les pages connues sont potentiellement accessibles après un zap. La distribution uniforme est évidemment recouvrante. Il en est de même de la distribution sur les pages d’accueil si toutes les pages connues d’un site sont accessibles à partir de la page d’accueil. C’est aussi le cas de la distribution par importance si, et seulement si, toutes les pages de ont un degré entrant non nul.

5.3.4 Source de rang : facteur zap

Afin de régler le problème de l’irréductibilité, Brin et al. [Pag+98] proposent une autre incorporation de la distribution de zap . Ils remplacent en effet par , et cherchent à résoudre :

Si , on a alors la garantie d’opérer sur une matrice positive irréductible et apériodique, puisque le graphe sous-jacent est une clique¹³. Le théorème de Perron-Frobenius assure donc la convergence du processus itératif vers le vecteur propre associé à la valeur propre maximale. Par contre, sauf si , la nouvelle matrice n’est pas stochastique, ni même sous-stochastique, ce qui rend l’interprétation en terme de surfeur aléatoire délicate. Afin de pouvoir plus facilement donner une interprétation au processus itératif, Brin et Page normalisent la matrice en prenant la moyenne pondérée par de A et de :

La nouvelle matrice obtenue possède la (sous-)stochasticité de , et elle est irréductible et apériodique. Si est stochastique, correspond au cas idéal de la Section 5.3.1¹⁴. Le vecteur propre maximal, que nous appellerons PageRank avec facteur zap, est alors obtenu par l’Algorithme 5.2. Ce vecteur représente la dernière version académique du PageRank présentée par Brin et Page avant que les méthodes de classement de Google ne deviennent un secret industriel. C’est à lui qu’on fait généralement référence lorsque l’on parle de PageRank.

Interprétation

Lorsque est stochastique, la double interprétation de est assez simple :

Transfert d’importance

avec le facteur zap, les pages ne transmettent qu’une fraction de leur importance. En contrepartie, chaque page se voit attribuer un PageRank Minimal d’Insertion (PRMI) égal à .

Surfeur aléatoire

à chaque étape du processus stochastique décrit par , le surfeur aléatoire va cliquer au hasard sur un des liens sortants, avec une probabilité , ou zapper avec une probabilité quelque part sur le graphe en selon la distribution .

5.3.5 Choix de

Avant d’aller plus loin, il convient de parler du choix du paramètre et des raisons qui ont poussé à faire ce choix. Pour commencer, précisons une réalité empirique universelle et inaltérable : vaut , à près. Depuis les débuts du PageRank, a en effet toujours été la valeur de référence, et à ma connaissance, les calculs pratiques de PageRank suivant le modèle de source de rang vu lors de la Section 5.3.4 utilisent toujours un compris entre et .

Compromis convergence/altération du graphe

D’après le Théorème 5.2, si est stochastique, ce que l’on peut supposer quitte à effectuer une complétion, les valeurs propres de autres que sont inférieures à en valeur absolue¹⁷. Cela garantit aux algorithmes Algorithme 5.2 et Algorithme 5.3 une convergence géométrique de raison au plus égale à . On a donc intérêt à choisir le plus petit possible… sauf que plus est petit, plus l’influence du zap, qui est une composante extérieure au graphe intrinsèque du Web, est grande. Un petit altère, voire dénature le graphe sous-jacent. Choisir le plus grand garantissant une convergence raisonnable semble donc un bon compromis. Or, les limitations techniques font que le nombre d’itérations réalisables par un moteur de recherche comme Google est de l’ordre de la centaine¹⁸. offre une précision de au bout de itérations, au bout de itérations, et semble donc être heuristiquement le compromis recherché. En effet, comme nous le verrons dans la Section 5.5, correspond au seuil de différenciation d’un graphe du Web d’un million de pages, alors que est le seuil de différenciation pour un milliard de pages.

5.4 Source de rang et matrices sous-stochastiques

Dans le modèle avec source de rang vu lors de la Section 5.3.4, nous avons vu que si l’ajout d’un facteur zap associé à une distribution recouvrante garantit l’irréductibilité de , la stochasticité de reste celle de . Lorsque est sous-stochastique, il faut donc s’adapter, et nous allons voir dans cette section les principales solutions envisageables.

5.4.1 Modèle hybride : facteur zap et renormalisation

est pseudo-irréductible (puisqu’elle est irréductible). Une première méthode envisageable pour obtenir un point fixe est donc d’appliquer la méthode de la renormalisation simple (cf Section 5.3.2) à la matrice .

L’interprétation en terme de surfeur aléatoire est la même que dans le cas où est stochastique, à ceci près qu’il faut compléter le défaut stochastique de par un zap selon la loi définie par le vecteur propre maximal de probabilité associé à .

5.4.2 Complétion et source de rang : -compensation

La complétion stochastique étant un moyen relativement simple d’assimiler toute matrice sous-stochastique à une matrice stochastique, il est intéressant d’hybrider la méthode de complétion stochastique avec une méthode de type zap ou ajout d’une page virtuelle (voir Section 5.6). On évite ainsi de devoir renormaliser à chaque itération, et on a une plus grande cohérence en terme d’interprétation stochastique. De plus, si on choisit une distribution de complétion égale à la distribution de zap , on obtient un algorithme très simple (l’Algorithme 5.3) : l’algorithme de -compensation. L’interprétation est tout aussi simple : à chaque étape du processus stochastique décrit par , le surfeur aléatoire va cliquer au hasard sur un des liens sortants (s’il en existe), avec une probabilité . Dans tous les autres cas, il va zapper selon .

5.4.3 PageRank non-compensé

L’algorithme de PageRank non-compensé consiste à calculer , exactement comme dans l’Algorithme 5.2, sans se préoccuper de la renormalisation. On obtient un vecteur strictement positif, qui peut servir à définir un PageRank, comme le montre le Théorème 5.3 et l’interprétation qui s’en suit.

5.4.4 Comparaison : algorithmes -compensé ou non-compensé ?

Il existe un lien très fort entre l’algorithme -compensé et l’algorithme non-compensé : ils donnent le même résultat, comme le montre le Théorème 5.4.

Convergence

Les tests que nous avons pu effectuer montrent que avec le choix de comme distribution initiale, il n’y a aucune différence significative entre la convergence de l’algorithme de -compensation et celui non-compensé. La convergence est dans les deux cas très rapide lors des premières itérations, et se stabilise ensuite vers une convergence de raison (cf boucle principale de la Figure 5.1).

Vitesse des itérations

La -compensation doit calculer le paramètre à chaque itération, alors que la non-compensation n’en a pas besoin. Est-ce que cela a une grande influence sur les performances ?

• Si la matrice ne tient pas en mémoire, le facteur limitant dans le calcul d’une itération est la multiplication de par . Le temps utilisé pour compenser est alors négligeable, et la vitesse des itérations n’a alors aucune influence dans le choix entre les deux algorithmes.
• En revanche, si , ou même simplement la matrice d’adjacence, tient en mémoire, le calcul et l’incorporation de prend une durée comparable à celle du calcul de . En fait, tout calcul de norme alourdit de manière non-négligeable le calcul d’une itération, et même le calcul du paramètre de convergence diminue considérablement les performances. On aboutit ainsi à l’algorithme SpeedRank (5.4), qui calcule le PageRank non-compensé en estimant grossièrement le nombre d’itérations nécessaires à une bonne convergence. Nos expériences ont mis en évidence un gain de vitesse de plus de sur les itérations entre SpeedRank et l’Algorithme 5.3, ce qui compense plus que largement la légère sur-estimation du nombre d’itérations nécessaires pour converger.

En terme de performances, l’algorithme -compensé est donc à proscrire si l’on travaille sur des «petits» graphes. On s’étonnera au passage que Kamvar et al. utilisent la -compensation dans leur algorithme BlockRank [Kam+03b], qui est justement basé sur la décomposition du PageRank sur des petits graphes. Pour des spécialistes de l’optimisation du calcul de PageRank (cf [Kam+03a]), il est curieux de passer à côté d’un gain de vitesse de …