L’intuition derrière le PageRank

L’intuition derrière le PageRank

Le pagerank, qui permet de quantifier la popularité d'une page web, est au coeur d'un moteur de recherche moderne comme Google. Quantité algorithmiquement simple à définir, le pagerank devient complexe à calculer du fait même de la taille du web. Par ailleurs, les enjeux économiques liés aux sites web font qu'une large
communauté de personnes essaye de le manipuler.

Il y a maintenant presque un an, nous avions écrit (nous = Thomas et moi-même) un chapitre sur la notion de PageRank pour le livre "Informatique Mathématique une photographie en 2014" (je précise que je ne touche rien sur les ventes). Nous avons choisi de faire un mini cycle de billets à partir de ce chapitre sur le blog. Vous pourrez donc voir les choses suivantes :

Principe d’un moteur de recherche et taxonomie de la triche
L'intuition derrière le PageRank (ce billet)
Comment amplifier le PageRank (1/3)
Comment amplifier le PageRank (2/3)
Comment amplifier le PageRank (3/3)

L'intuition

Comme mentionné plus haut, le pagerank a été pensé comme une mesure de la popularité des pages. La popularité ainsi définie ne provient alors que des liens entre les pages, et pas du contenu de ces pages.  En revanche, contrairement à une idée très répandue, le pagerank est une propriété des chemins du graphe du web, et pas seulement une propriété des liens entrants sur une page donnée. En effet, le pagerank est transmis de page en page, et donc une page à fort pagerank aura un impact sur des pages qui lui sont reliées, même si c'est via un long chemin.

Le modèle proposé par Brin et Page [1] pour légitimer cette notion de popularité est celui du surfeur aléatoire. Intuitivement, il s'agit d'un internaute qui parcourt le web en cliquant aléatoirement sur les liens sortants de la page sur laquelle il est à un moment donné. Parfois, le surfeur aléatoire peut décider de changer totalement de voisinage, ce qui est implicitement modélisé par une probabilité de continuer, ou non, à suivre les liens. Lorsqu'il décide de ne plus suivre les liens, il recommence son parcours à partir d'une page tirée aléatoirement sur le web. On parle parfois de téléportation pour désigner cet évènement.

Le modèle abouti naturellement à la formulation suivante :

pi_i = frac{1-c}{n} + sum_{j rightarrow i} frac{pi_j}{d^{+}(j)}.

Ici, pi_i est le pagerank de la page i, c est la probabilité pour le surfeur aléatoire de continuer à suivre les liens, j rightarrow i signifie que la page j fait un lien vers la page i (il y a un arc de j vers i dans le graphe), et enfin d^{+}(j) est le degré sortant de la page j. En outre le graphe contient |G|=n pages.

On voit alors que la définition même du pagerank est liée au comportement du surfeur aléatoire. En effet, le pagerank d'une page est défini comme étant la probabilité qu'à un moment donné, le surfeur alétoire se trouve sur cette page. On comprend alors pourquoi on parle de popularité : plus une page a un fort pagerank, plus elle est visitée par des surfeurs aléatoires, et donc plus elle est populaire.

Il reste à expliciter le rôle de c. Il s'agit d'un paramètre de contrôle sur le calcul du pagerank. Plus c est proche de 1, plus la convergence de la méthode de calcul du pagerank est lente et la capacité ségrégative du pagerank est forte, c'est-à-dire plus les pages auront des pageranks différents les uns des autres. En revanche, si c est proche de 0, alors toutes les pages ont des pagerank proches, avec une convergence rapide.

Plus de détails

Nous allons maintenant donner plus de détails sur le calcul du pagerank. Le lecteur intéressé par des explications encore plus complètes pourra lire les articles de Langville et Meyer [2], de Bianchini et al [3], ou encore les livres de Manning et al [4] ou Easley et Kleinberg [5]. Je vous préviens, chers lecteurs, qu'il s'agit de lectures très techniques.

On représente le web par une matrice M telle que M_{ij} est la probabilité que le surfeur aléatoire suive un lien de la page i vers la page j. On a donc :

M_{ij} = frac{#(i rightarrow j)}{d^{+}(i)}.

Le problème qui se pose alors est que M n'est pas une matrice stochastique. Elle n'est donc pas la matrice de transition d'une chaîne de Markov finie, et on ne peut donc pas trouver de loi stationnaire (et donc de pagerank).

Si cette matrice n'est pas stochastique, c'est d'abord parce que certaines lignes de la matrice peuvent ne contenir que des zéros, ce qui arrive pour les noeuds du graphe correspondant à une page sans liens sortants. On appelle ces noeuds des puits (dangling nodes en anglais).
Pour pallier ce problème, on va remplacer chaque zéro des lignes ne contenant que des zéros par frac{1}{n}. Intuitivement, cela signifie que les noeuds puits sont maintenant des noeuds qui renvoient uniformément vers n'importe quel noeud du graphe, c'est-à-dire que ces noeuds correspondent à une téléportation vers une page choisie aléatoirement uniformément. La matrice obtenue par cette opération est notée widehat{M}.

Cependant, la chaîne de Markov associée à la matrice widehat{M} ne permet pas de calculer une loi stationnaire car elle n'est pas irréductible (chaque état n'est pas accessible à partir de n'importe quel autre état). En effet, le graphe sous-jacent à cette matrice n'est pas nécessairement fortement connexe. La solution standard pour garantir que la chaîne de Markov soit irréductible est de construire une nouvelle matrice, que nous noterons P, et qui est la combinaison convexe entre la matrice stochastique widehat{M} et une matrice de perturbation :

P = alpha widehat{M} + (1-alpha) {bf 1}v^T,

avec 0 leq alpha < 1 et ||v||_1 = 1.
En procédant ainsi, il y a toujours une probabilité de transition non nulle entre deux noeuds du graphe, même si elle est parfois très petite. Quelle est cette variable alpha ? Il s'agit du paramètre c que nous avons vu plus haut. Enfin, v^T va être typiquement défini de façon à obtenir une téléportation. C'est-à-dire pour permettre de rejoindre n'importe quel noeud du graphe, de manière uniforme.

Une fois obtenue la matrice P, on peut définir le pagerank du graphe G associé. Il s'agit de la loi stationnaire pi^T de la chaîne de Markov. Ce vecteur  pi^T peut être trouvé par la résolution du système linéaire suivant :

pi^T (I - P) = 0^T .

I est ici la matrice identité. Dans les deux cas, il faut rajouter une condition de normalisation sur le vecteur pour garantir qu'il définit bien une probabilité.

Il existe de nombreuses méthodes pour calculer le pagerank, mais la plus simple est sans doute celle de la puissance itérée. En effet, la définition du pagerank comme étant le vecteur pi^T tel que (pi^T P ) = pi^T implique que pi est le vecteur propre à gauche de P, associé à la valeur propre dominante 1.

Le principe de la méthode de la puissance itérée est très simple (voir [1] par exemple), mais je vais vous faire grâce de l'algorithme, qui se trouve dans le chapitre de livre si vous souhaitez en savoir plus. La vitesse de convergence de la méthode est raisonnable. Une estimation du nombre d'itérations nécessaires, donnée dans
[1], est :

frac{log_{10} varepsilon}{log_{10} alpha}.

le varepsilon est la précision de l'algorithme : plus il est précis, plus la convergence est lente, plus il est rapide, plus le résultat est incorrect ! Cette formule correspond à 114 itérations pour varepsilon = 10^{-8} et alpha = 0,85. Comme évoqué plus haut, changer la valeur de alpha à un impact très fort. Ainsi, si on passe à 0.99 pour alpha, en maintenant une précision de  varepsilon = 10^{-8}, alors le nombre d'itérations pour obtenir la convergence est de 1833.

Nous avons vu dans cette section ce qu'il faut savoir au minimum concernant le pagerank. Le calcul du pagerank est cependant un domaine qui a été extrêmement dynamique et fécond, et qui continue à être très étudié. Parmi les approches intéressantes, on trouve des méthodes de Monte Carlo [6] et bien d'autres encore. Une lecture qui vaut le détour sur le sujet : la thèse de Taher Haveliwala, qui parle du calcul du pagerank, mais aussi du fameux pagerank thématique que nous n'aborderons pas ici [7].

[1] Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer networks and ISDN systems, 30(1), 107-117.

[2] Langville, A. N., & Meyer, C. D. (2004). Deeper inside pagerank. Internet Mathematics, 1(3), 335-380.

[3] Bianchini, M., Gori, M., & Scarselli, F. (2005). Inside pagerank. ACM Transactions on Internet Technology (TOIT), 5(1), 92-128.

[4] Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to information retrieval (Vol. 1, p. 6). Cambridge: Cambridge university press.

[5] Easley, D., & Kleinberg, J. Networks, Crowds, and Markets. Cambridge University.

[6] Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N. (2007). Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal on Numerical Analysis, 45(2), 890-904.

[7] Haveliwala, T. H. (2005). Context-sensitive Web search (Doctoral dissertation, Stanford University).

Comments ( 2 )

  • C’est toujours bon une petite séance de révision ! En revanche, tu pourrais spinner l’introduction histoire d’améliorer la pertinence entre les 2 articles sur le sujet ! 😉

  • Bonjour,

    Bon, à la première lecture, j’ai (rien|pas tout) compris… Merci quand meme pour toutes ces formules, je penses que je vais reprendre tout cela à tête reposée.