Calcul de PageRank sur des exemples

Exemple 1, site à 2 pages (liens internes)

Considérons l'exemple très simple d'un site contenant seulement 2 pages : une page A et une page B.
Dans la page A il y a un lien vers la page B donc C(A) = 1.
Dans la page B il y a un lien vers la page A donc C(B) = 1.
Prenons comme hypothèse de départ que chaque PR = 1. Je justifierai ce choix après.

PR(A) = (1 - 0,85) + 0,85 (PR(B)/C(B))
or PR(B) = 1 et C(B) = 1
PR(A) = (1 - 0,85) + 0,85 * 1
PR(A) = 1
de la même façon
PR(B) = 1

"C'est évident puisqu'on était parti de 1 comme valeur, en fait rien n'a changé" me direz-vous.
Oui mais attention, c'est ici le point sans doute le plus délicat de tout l'exposé.
Il y a 2 choses importantes ici :

1) Google doit connaître le PR(B) pour calculer le PR(A) or PR n'existe pas au départ donc PR(B) ne peut être calculé. Si PR(B) ne peut être calculé, alors PR(A) ne peut être calculé et si PR(A) ne peut être calculé, alors PR(B) ne peut être calculé ??? et on n'en sort pas. Vous comprenez maintenant pourquoi il doit exister absolument chez Google des pages indexées (qui ont un PR) ayant des liens pointant vers vos pages.

2) En fait, le calcul que fait Google est itératif. C'est à dire que le calcul est fait en boucle de nombreuses fois pour obtenir une valeur de PR stable. A la place de 1 pour la valeur de PR de départ, prenons par exemple 0. Cela paraît assez logique puisque au départ il n'y a pas de PR défini pour les pages A et B. Refaisons le calcul.

PR(A) = (1 - 0,85) + 0,85 (PR(B)/C(B)) or PR(B) = 0 et C(B) = 1
PR(A) = (1 - 0,85) + 0,85 * 0
PR(A) = 0,15
Attention nous avons un PR(A) = 0,15, nous allons l'utiliser pour le calcul de PR(B)

PR(B) = (1 - 0,85) + 0,85 (PR(A)/C(A)) or PR(A) = 0,15 et C(A) = 1
PR(B) = (1 - 0,85) + 0,85 * 0,15/1
PR(B) = 0,2775

C'est tout à fait différent.
Maintenant que nous avons de vraies valeurs de PR calculées, recommencons le calcul (itération).

PR(A) = (1 - 0,85) + 0,85(PR(B)/C(B)) or PR(B) = 0,2775 et C(B) = 1
PR(A) = (1 - 0,85) + 0,85 * 0,2775
PR(A) = 0,385875

PR(B) = (1 - 0,85) + 0,85(PR(A)/C(A)) or PR(A) = 0,385875 et C(A) = 1
PR(B) = (1 - 0,85) + 0,85 * 0,385875
PR(B) = 0,47799375

Encore différent.
Recommencons le calcul avec les nouvelles valeurs.

PR(A) = (1 - 0,85) + 0,85(PR(B)/C(B)) or PR(B) = 0,47799375 et C(B) = 1
PR(A) = (1 - 0,85) + 0,85 * 0,47799375
PR(A) = 0,5562946875

PR(B) = (1 - 0,85) + 0,85(PR(A)/C(A)) or PR(A) = 0,5562946875 et C(A) = 1
PR(B) = (1 - 0,85) + 0,85 * 0,5562946875
PR(B) = 0,622850484

Et ainsi de suite.
Regardons comment évoluent les PR(A) et PR(B).

PR(A) = 0,15 puis 0,385875 puis 0,5562946875.
PR(B) = 0,2775 puis 0,47799375 puis 0,622850484.

Vous remarquez que les valeurs augmentent avec le nombre d'itérations.
En fait, au bout d'un certain nombre d'itérations on tend vers les valeurs :

PR(A) = 1
PR(B) = 1

C'est à dire le même résultat que la première fois. Il faudrait à peu près entre 50 et 100 itérations pour être proche de ces valeurs.

Que se passerait-il si on prenait une valeur élevée de départ par exemple 60.
Recommencons les calculs.

PR(A) = (1 - 0,85) + 0,85(PR(B)/C(B)) or PR(B) = 60 et C(B) = 1
PR(A) = (1 - 0,85) + 0,85 * 60
PR(A) = 51,15

PR(B) = (1 - 0,85) + 0,85(PR(A)/C(A)) or PR(A) = 51,15 et C(A) = 1
PR(B) = (1 - 0,85) + 0,85 * 51,15
PR(B) = 43,6275

Encore une fois

PR(A) = (1 - 0,85) + 0,85(PR(B)/C(B)) or PR(B) = 43,6275 et C(B) = 1
PR(A) = (1 - 0,85) + 0,85 * 43,6275
PR(A) = 37,233375

PR(B) = (1 - 0,85) + 0,85(PR(A)/C(A)) or PR(A) = 37,233375 et C(A) = 1
PR(B) = (1 - 0,85) + 0,85 * 37,233375
PR(B) = 31,79836875

Vous remarquez que les valeurs diminuent, c'est tout à fait normal puisqu'on les multiplie à chaque fois par le facteur 0,85 et que on ne les augmente que de 0,15. En fait au bout d'un certain nombre d'itérations on obtiendrait :

PR(A) = 1
PR(B) = 1

Quelquesoit le PR de départ, on obtient le même résultat c'est donc la structure des liens qui impose le résultat. C'est absolument FONDAMENTAL. C'est la base du PageRank. C'est cette interactions des liens entre les pages qui rend impossible un calcul direct. Dans notre exemple quand vous calculez PR(A), vous obtenez une valeur qui intervient dans le cacul de PR(B) qui lui même intervient dans le calcul de PR(A). D'où la nécessité de faire les calculs en boucle.

Remarquez également que le PR total maximum du site est égal au nombre de pages. C'est toujours vrai (sauf exceptions de sites très mal conçus, cf. plus loin). De plus dans notre exemple, les liens sont également partagés. C'est ce qui explique l'égalité du résultat final.

Certains sites proposent des programmes pour calculer les itérations (voir dans la page liens).

[haut] [index Google référencement] [suite]