Comment le PageRank est-il calculé ?
Le calcul du PageRank d'une page
peut être effectué sans connaître le PR final
des pages émettant
un lien vers
elle. Cela peut sembler bizarre, mais chaque itération
fait converger les
résultats vers une
valeur de plus en plus
précise. La seule chose à faire, est
de retenir la valeur obtenue pour pouvoir
démarrer
l'itération suivante
avec
cette dernière. Ce sera plus simple
avec quelques exemples :
Réinventons le Web dans sa forme la plus simple :
| 2
pages A et B pointant l'une vers l'autre.
Chaque page a un lien sortant,
donc C(A) = C(B) = 1
|
|
| Première estimation :
Nous ne
connaissons pas le PR des deux pages,
donc il nous faut une valeur de départ :
1.0 par exemple.
|
|
PR(A) |
= (1 - d) + d(PR(B)/1) |
|
PR(B) |
= (1 - d) + d(PR(A)/1) |
|
| Soit, avec un facteur d'amortissement
de 0.85 :
Les valeurs ne changent pas...Nous avons
peut-être
eu trop de chance avec notre estimation.
Prenons une valeur de
départ différente : 0
|
|
PR(A) |
= 0.15 + 0.85 * 1 |
= 1 |
|
PR(B) |
= 0.15 + 0.85 * 1 |
= 1 |
|
| Première itération
|
|
PR(A) |
= 0.15 + 0.85 * 0 |
= 0.15 |
|
PR(B) |
= 0.15 + 0.85 * 0.15 |
= 0.2775 |
|
| Deuxième itération
|
|
PR(A) |
= 0.15 + 0.85 * 0.2775 |
= 0.385875 |
|
PR(B) |
= 0.15 + 0.85 * 0.385875 |
= 0.47799375 |
|
| Troisième itération
|
|
PR(A) |
= 0.15 + 0.85 * 0.47799375 |
= 0.5562946875 |
|
PR(B) |
= 0.15 + 0.85 * 0.5562946875 |
= 0.622850484375 |
|
|
Nous remarquons que les valeurs augmentent
à chaque
itération.
Dans notre exemple, avec nos deux pages A et B,
nous
savons que le PR
doit être égal à un,
l'algorithme nous précisant que le PR
moyen de toutes
les pages du Web est égal à 1.
Est-ce que nos valeurs de PR
calculées
ne peuvent pas augmenter indéfiniment et dépasser 1,
ce qui
invaliderait la formule ?
Essayons avec une valeur supérieure pour voir
ce qui
se passe :
|
|
| Prenons une valeur 2.0 pour redémarrer
notre expérience.
|
|
PR(A) |
= 0.15 + 0.85 * 2 |
= 1.85 |
|
PR(B) |
= 0.15 + 0.85 * 1.85 |
= 1.7225 |
|
| Cela baisse !
|
|
PR(A) |
= 0.15 + 0.85 * 1.7225 |
= 1.614125 |
|
PR(B) |
= 0.15 + 0.85 * 1.614125 |
= 1.52200625 |
|
| Essayons
une troisième fois :
Nos valeurs continuent
à converger vers 1.
|
|
PR(A) |
= 0.15 + 0.85 * 1.52200625 |
= 1.4437053125 |
|
PR(B) |
= 0.15 + 0.85 * 1.4437053125 |
= 1.377149515625 |
|
|
Premier enseignement :
Quelle
que soit la valeur de départ prise pour le calcul du PR,
la moyenne normalisée
tendra vers 1.
|
|
Accélérer les calculs grâce au facteur d'amortissement
L'exemple qui a précédé nous montre un Web
simplissime, seulement 2 pages.
Combien d'itérations
faut-il pour voir les
résultats converger pour un grand
nombre de pages ?
A l'heure actuelle,
Google a près de 4 milliards de pages dans sa base, ce qui pourrait nécessiter
plusieurs milliards d'itérations.
C'est ici que le facteur d'amortissement joue son
rôle.
S'il est choisi trop élevé, le calcul demandera un nombre
d'itérations énorme,
alors que s'il est trop bas
les valeurs
ne convergeront pas
véritablement, mais finiront
par osciller autour de la valeur théorique
vraie,
un peu à la manière d'un pendule. Avec un facteur d'amortissement de 0.85,
il nous
faut une quarantaine d'itérations pour affiner le calcul
du PageRank.
Deuxième exemple : quatre pages liées
Dans cet exemple, nous avons un site comprenant
quatre pages, dont une ne recevant aucun lien
(la page D).
Le PR de cette
page sera donc de 0.15, grâce au premier terme de la formule
du PageRank (1 - d) .
Bien qu'ayant un PR calculé, il est vraisemblable
que
cette page disparaîtra
de l'index Google très vite,
n'ayant aucun lien entrant. Au bout d'une vingtaine d'itérations,
les valeurs de
PR pour nos pages convergent vers les valeurs suivantes :
| Nous voyons que la page C a le
PR le plus élevé.
C'était prévisible dès l'examen du graphique,
comme elle
reçoit un lien entrant des pages A,B et D
et n'en émet qu'un seul vers la page
A.
|
|
Page A |
1.49 |
|
Page B |
0.78 |
|
Page C |
1.58 |
|
Page D |
0.15 |
|
Somme des PageRank |
4.0 |
|
Moyenne |
1.0 |
|
Calculez vous-même les exercices suivants
Pour les exemples suivants, le lecteur
souhaitant expérimenter par lui même
le calcul du pagerank
pourra utiliser
un calculateur prévu à cet effet, disponible sur le site de WebWorkShop
WebworkShop s'ouvrira dans une
autre fenêtre pour vous permettre de faire
les exercices
tout en poursuivant
la
lecture de l'article.
|
Suite
|
|
|
|
