L'algorithme itératif du PageRank de Google
Introduction
Cette page explique comment l'algorithme PageRank de Google fonctionne. Il y a plusieurs façons de calculer le PageRank d'un graphe. Cette page explique comment implémenter la version itérative de l'algorithme PageRank de Google en s'appuyant sur le papier original de Google.
Le papier original de Google
D'après le papier original de Google, la PageRank est défini comme ceci :
Supposons qu'une page \(A\) soit pointée pardes liens provenant des pages \(T1...Tn\). Le paramètre \(d\) est un facteur d'amortissement qui peut être choisi entre 0 et 1. On choisit généralement \(d\) égal à 0.85. La section suivante discute du facteur \(d\) plus en détails. Nous définissons aussi \(C(A)\) comme le nombre de liens sortants de la page \(A\). Le PageRank de la page \(A\) est donné par :
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
Notons que les PageRanks forment une distribution de probalilités sur l'ensemble des pages. De cette façon, la somme des PageRanks de toutes les pages sera égal à 1.
PageRank ou PR(A) peut être calculé en utilisant un simple algorithme itératif, et correspond au principal vecteur propre de la matrice d'adjacence du web.
Le PageRank de chaque page est alors calculé avec la formule suivante :
$$ PR(A) = (1-d) + d\left(\dfrac{PR(T1)}{C(T1)} + ... + \dfrac{PR(Tn)}{C(Tn} \right) $$
- \(PR(A)\) est le PageRank de la page \(A\)
- \(C(Tn)\) est le nombre de liens sortants de la page \(Tn\)
- \(d\) est le facteur d'ammortissement.
Le facteur d'amortissement est expliqué de la façon suivante par Sergey Brin et Lawrence Page:
Le PageRank peut être considéré comme un modèle de comportement de l'utilisateur. Nous supposons qu'il existe un "surfeur aléatoire" à qui l'on donne une page Web au hasard et qui continue à cliquer sur les liens, sans jamais appuyer sur "retour", mais qui finit par se lasser et passe à une autre page aléatoire. La probabilité que le surfeur aléatoire visite une page est son PageRank. Et le facteur d'amortissement d est la probabilité qu'à chaque page, le "surfeur aléatoire" se lasse et demande une autre page aléatoire.
Exemple
COnsidérons le graphe du web simplifié ci-dessous :
- Comme la page 1 n'a qu'un seul lien sortant : \(C(1) = 1\).
- Comme la page 2 n'a qu'un seul lien sortant : \(C(2) = 1\).
- Comme la page 3 n'a qu'un seul lien sortant : \(C(3) = 2\).
$$ \begin{align} C(1) &= 1 \\ C(2) &= 1 \\ C(3) &= 2 \\ \end{align} $$
Valeurs initiales des PageRanks
Un problème avec l'algorithme est que pour calculer le PageRank des pages, nous avons besoin d'une valeur initiale de ces PageRanks. En réalité, peu importe la valeurs initiales, l'algorithme convergera toujours vers les mêmes valeurs. Comme "la somme des PageRanks de toutes les pages du web est égale à 1." nous allons démarrer avec une valeur initiale de 1 pour chaque page (pas 1/3, vous comprendre pourquoi dans la dernière section) :
$$ \begin{align} PR(1) &= 1 \\ PR(2) &= 1 \\ PR(3) &= 1 \\ \end{align} $$
Première itération
Détaillons la première itération pour chaque page :
La page 1 est pointée par un lien provenant de la page 3 :
$$ PR(1) = (1-d) + d\left(\dfrac{PR(3)}{C(3)}\right) $$ $$ PR(1) = (1-0.85) + 0.85\left(\dfrac{1}{2}\right) $$ $$ PR(1) = 0.575 \label{eq:PR1} $$
La page 2 est pointée par deux liens provenant des pages 1 et 3:
$$ PR(2) = (1-d) + d\left(\dfrac{PR(1)}{C(1)} + \dfrac{PR(3)}{C(3)}\right) $$ $$ PR(2) = (1-0.85) + 0.85\left(\dfrac{0.575}{1} + \dfrac{1}{2}\right) $$ $$ PR(2) = 1.06375 $$
Notons que le PageRank de la page 1 a précédemment été mis à jour avec l'équation\eqref{eq:PR1} : \(PR(1)=0.575\).
La page 3 est pointée par un lien provenant de la page 2 :
$$ PR(3) = (1-d) + d\left(\dfrac{PR(2)}{C(2)}\right) $$ $$ PR(3) = (1-0.85) + 0.85\left(\dfrac{1.425}{1}\right) $$ $$ PR(3) = 1.0541 $$
Après la première itération les PageRanks sont :
$$ \begin{align} PR(1) &= 0.5750 \\ PR(2) &= 1.0637 \\ PR(3) &= 1.0542 \\ \end{align} $$
Itérations suivantes
Si l'on répéte l'algorithme sur plusieurs itérations, voici les PageRanks :
| Iteration | \(PR(1)\) | \(PR(2)\) | \(PR(3)\) |
|---|---|---|---|
| 1 | 0.575 | 1.064 | 1.054 |
| 2 | 0.598 | 1.106 | 1.090 |
| 3 | 0.613 | 1.135 | 1.115 |
| 4 | 0.624 | 1.154 | 1.131 |
| 5 | 0.631 | 1.167 | 1.142 |
| 6 | 0.635 | 1.175 | 1.149 |
| 7 | 0.638 | 1.181 | 1.154 |
| 8 | 0.640 | 1.185 | 1.157 |
| 9 | 0.642 | 1.187 | 1.159 |
| 10 | 0.643 | 1.189 | 1.160 |
Voici l'évolution des PageRanks sur 20 itérations. On peut voir que les valeurs évoluent assymptotiquement :
PageRank final
Après 100 itérations, les PageRanks finaux sont :
$$ \begin{align} PR(1) &= 0.6444 \\ PR(2) &= 1.1922 \\ PR(3) &= 1.1634 \\ \end{align} $$
Comme l'explique Sergey Brin and Lawrence Page: "la somme des PageRanks de toutes les pages du web est égale à 1.".
Vérifons :
$$ 0.6444 + 1.1922 + 1.1634 = 3 $$
Ce n'est pas exactement ce que j'appelle 1. En réalité, il faut lire "la somme normalisée de tous les PageRanks" à la place de "La somme de tous les PageRanks", en d'autres mots la moyenne :
$$ \dfrac{0.6444 + 1.1922 + 1.1634 }{3} = 1 $$
Voilà pourquoi nous avons commencé avec des PageRank de 1 et non 1/3.
Téléchargement
L'algorithme a été implémenté sous MATLAB. Tous les résultats présentés sur cette page ont été calculés avec le script ci-dessous :
Sources
- The Google Pagerank Algorithm and How It Works par Ian Rogers
- The Anatomy of a Large-Scale Hypertextual Web Search Engine par Sergey Brin et Lawrence Page
Voir aussi
- Combien de caractères dans les requêtes des moteurs de recherche ?
- PageRank Random Surfer
