Quelques centaines - voire quelques milliers - d'interventions sur des forums dédiés au référencement de France ou d'ailleurs m'ont fait réaliser que la notion de PageRank (PR) est parmi celles qui pose le plus de problèmes de compréhension au Webmaster débutant.


L'algorithme du PageRank est un des sujets qui a suscité le plus de débats passionnels auprès des Webmasters.
Il existe de ce fait de nombreux articles traitant du sujet sur Internet, mais la plupart sont rédigés en anglais. Cette barrière linguistique limite l'intérêt de ces articles pour toute une classe de Webmestres francophones.
Nous citerons tout de même l'excellent article de Ian Rogers : "The Google Pagerank Algorithm and How It Works" qui nous a largement inspiré pour la rédaction de celui-ci.

Essayons donc ensemble de lever un voile sur cet algorithme dont la compréhension est indispensable à un bon référencement sur le Roi des moteurs.

Le PageRank, c'est quoi ?

La base du PageRank - que nous noterons parfois PR dans la suite de ce document - est une formule mathématique, à l'allure rébarbative, mais en définitive assez simple à comprendre. Cette méthode est utilisée par Google pour déterminerl'importance d'une page Web. Elle se base sur un concept très simple : un lien émis par une page A vers une page B est assimilé à un " vote " de A pour B. Au plus une page reçoit de " votes ", au plus cette page est considérée comme importante par Google, exactement comme le principe des élections que nous connaissons tous. La comparaison avec les élections s'arrête là car toutes les pages n'ont pas le même pouvoir de " vote ". Nous reviendrons plus en détail sur ce point, mais retenez dès à présent qu'un vote émis par la page d'accueil d'un site majeur tel que Microsoft ou CNN pèse beaucoup plus lourd qu'un vote émis par la page perso de votre cousine, si mignonne soit-elle.


Combattons les idees fausses

Retenons aussi que le PageRank est une mesure de l'importance d'une page, et non d'un site entier. Vous entendrez souvent parler de " site de rang n ", il s'agit d'un abus de langage décrivant le rang de la page d'accueil du site.

Il n'y a pas, nous le verrons plus bas, de notion d'importance de site dans l'algorithme du PageRank. De même, l'importance d'une page est sans rapport aucun avec l'intérêt ou la pertinence de celle-ci, ces deux dernières notions étant totalement absentes de l'algorithme du PageRank. Elles interviennent néanmoins dans les pages de résultat de recherche.

Ce PageRank peut être visualisé par les utilisateurs de la " toolbar " Google, outil téléchargeable gratuitement, uniquement disponible pour Internet Explorer sous Windows. La représentation graphique se fait sur une échelle de 1 à 10. L'exemple ci-dessus montre l'affichage d'une page ayant un PageRank égal à 5 (noté PR5).


La version 2.0 de la toolbar Google
Elle permet aussi de bloquer les popups indésirables

Et cette fameuse formule, alors ?
En reprenant - après traduction - la publication originale de Google, voici les explications données :

Nous assumons qu'une page A reçoit des liens (ou "votes") émis par les pages T1...Tn. Le paramètre d est un facteur d'amortissement pouvant être ajusté entre 0 et 1. Nous donnons généralement à d la valeur 0.85. De même, C(A) est défini comme le nombre de liens émis par la page A (liens sortants). Le PageRank de la page A est défini comme suit :

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Le PageRank peut être calculé en utilisant un simple algorithme itératif, et correspond au vecteur propre principal de la matrice normalisée des liens du Web.

Tout cela est bien moins compliqué qu'il n'y paraît, essayons de disséquer l'expression.
Pour ce faire, voici l'explication de la notation utilisée :

PR(A)	le PageRank de la page A
PR(Tn)	le PageRank de la page Tn
C(Tn)	le nombre de liens émis sur la page Tn
d	tous les " votes " sont additionnés, mais pour en limiter l'importance, le total est multiplié par ce coefficient d'amortissement (0.85)
1 - d	Un petit peu de " magie mathématique " qui permet de garantir que la moyenne des PageRank de l'ensemble des pages du Web sera de 1.

L'examen de cette formule permet de voir que le PageRank d'une page n'ayant aucun lien entrant sera de 0.15 , soit : (1 - 0.85) + 0.85*(0) = 0.15
Et là apparaît la cause de la confusion la plus répandue au sujet du PageRank :

Que vient faire ici cette valeur fractionnaire alors que la toolbar n'affiche que des valeurs entières ?


Oublions la toolbar quelques instants !


Il est généralement admis que l'échelle du PageRank est logarithmique, sans que ceci ne soit officiellement confirmé. Pour cette raison, la base utilisée ne peut qu'être estimée. Il est de même raisonnable de penser que cette base évolue dans le temps.
Prenons une échelle logarithmique de base 10 pour simplifier nos calculs, le raisonnement restant valable quelle que soit le base choisie.

PageRank Affiché (log base 10)	PageRank réel (calculé)
PR0	0 = PR < 1
PR1	1 = PR < 10
PR2	10 = PR < 100
PR3	100 = PR < 1000
PR4	1000 = PR < 10000
et ainsi de suite jusqu'au PR10 pour les plus heureux.

On voit ici, que chaque niveau de PageRank est 10 fois plus élevé que le niveau précédent. Ce qui signifie en clair qu'il est 10 fois plus ardu de passer de PR4 à PR5 que de passer de PR3 à PR4 (pour mémoire, la base 10 a été choisie arbitrairement dans notre exemple).
Une des raisons pour lesquelles on estime que l'échelle évolue dans le temps, est que le PageRank maximum n'est calculé que lorsque Google fait sa mise à jour de l'index, et que le nombre de pages indexées est en constante augmentation.
Cette évolution de l'échelle expliquerait pourquoi certaines pages voient leur PageRank diminuer au fil des indexations, alors que le nombre de liens entrant reste inchangé.
En reprenant l'exemple de la page sans lien entrant donné précédemment (PR=0.15), nous voyons que la toolbar nous affichera bien la valeur 0.

Comment le page rank est-il calcule?

Nous avons vu que le PageRank d'une page A dépend du PageRank des pages T1...Tn qui émettent un lien vers A, et ne peut donc pas être déterminé sans connaître le PR de ces dernières, et de toutes celles qui émettent un lien vers elles, et ainsi de suite...
Lorsqu'on réalise que les liens inter pages peuvent boucler, cela ressemble bien à " mission impossible ".

Reprenons la publication de Google décrivant le PageRank :

Le PageRank peut être calculé en utilisant un simple algorithme itératif, et correspond au vecteur propre principal de la matrice normalisée des liens du Web

Ceci signifie que 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 paradoxal, 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 :

PR(A)	= 0.15 + 0.85 * 1	= 1
PR(B)	= 0.15 + 0.85 * 1	= 1

Bon, 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

Première itération

PR(A)	= 0.15 + 0.85 * 0	= 0.15
PR(B)	= 0.15 + 0.85 * 0.385875	= 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

Bon, cela baisse ! Essayons une fois de plus :

PR(A)	= 0.15 + 0.85 * 1.7225	= 1.614125
PR(B)	= 0.15 + 0.85 * 1.614125	= 1.52200625

Une troisième fois :

PR(A)	= 0.15 + 0.85 * 1.52200625	= 1.4437053125
PR(B)	= 0.15 + 0.85 * 1.4437053125	= 1.377149515625

Nos valeurs continuent à converger vers 1, c'est ce que nous attendions.

Premier enseignement :
Quelle que soit la valeur de départ prise pour le calcul du PR, la moyenne normalisée tendra vers 1.

Accelerer 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 :

Page A	1.49
Page B	0.78
Page C	1.58
Page D	0.15
Somme des PageRank	4.0
Moyenne	1.0

Nous voyons que dans notre exemple, 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.

Calculez vous-même les exercices suivants...

Pour les exemples suivants, nous intégrerons les résultats directement dans le graphique, pour ne pas alourdir l'article avec les tableaux comprenant les valeurs de PageRank intermédiaires. Sauf indication contraire, la valeur 1.0 est prise pour la première itération, et le nombre d'itérations sera de 40. Le lecteur qui souhaite expérimenter par lui même pourra utiliser l'excellent calculateur de PageRank disponible sur le site de WebWorkShop ou de notre version simplifiée en Français. Celui-ci s'ouvrira dans une fenêtre popup pour vous permettre de faire les exercices tout en poursuivant la lecture de l'article.

Nous avons délibérément simplifié le calculateur de WebWorkShop, pour ne retenir que les fonstions essentielles permettant de suivre les exemples de l'article.

Troisième exemple : liens circulaires

Cases cochées pour l'exemple 3

Comme on pouvait s'y attendre dans ce cas, les liens circulaires ne favorisent aucune page du site, chaque page ayant exactement un lien entrant et un lien sortant.
Le PageRank de chaque page s'établira donc à 1.0

Quatrième exemple : structure hiérarchique simple

Cases cochées pour l'exemple 4

Voilà qui est mieux ! Le PageRank de la page A est optimisé grâce à la structure de liens hiérarchique.

Cinquième exemple : on lie à tout va !

Cases cochées pour l'exemple 5

Ici, on a voulu lier toutes les pages entre-elles, ce qui fait qu'aucune page n'est prépondérante. La page d'accueil du site hérite d'un PR1, au même titre que toutes les autres pages. On obtient le même PR qu'avec les liaisons circulaires, tout en gagnant en facilité de navigation pour les visiteurs. Ce type de chaînage devient très vite difficile à réaliser dès que le nombre de pages du site augmente.

Sixième exemple : structure hiérarchique avec lien entrant

Cases cochées pour l'exemple 6

Nous avons estimé à 1.0 le PR de la page externe (backlink) liant vers notre page A. Dans notre exemple, comme nous faisons abstraction du reste du Web, nous imaginerons que le Webmaster du site extérieur nous aime vraiment beaucoup et que le seul lien émis par sa page pointe vers la nôtre. Ceci a peu de chances de se produire dans la réalité.

C'est tout bénéfice pour la page d'accueil qui, non contente d'hériter de 0.85 point de PR de la page externe, répercute cet accroissement de PR sur les pages internes du site et le récupère grâce aux liens en retour. Cela fait pas moins de trois points de PR gagnés par la page d'accueil par rapport à la structure hiérarchique de notre quatrième exemple .

Gardons à l'esprit un point important !

Les valeurs de PageRank données ici sont celles reprises dans notre tableau en début d'article, dans la colonne "Pagerank Réel"et non dans celle du Pagerank affiché par le Toolbar. Ne rêvons tout de même pas, il ne suffit pas d'un petit lien à PR1 pour obtenir un PR4 affiché par la toolbar !

En reprenant ce tableau et dans l'hypothèse d'une échelle logarithmique de base 10, cette page aurait un PR1 affiché, son PR réel se situant dans l'intervalle 1...10