Explications sur la formule du PageRank

Par Olivier Duffez , Samedi 6 septembre 2008

Le PageRank est une méthode inventée par Google pour mesurer l'importance relative des pages du web, que l'on appelle souvent la popularité. Elle est basée sur la topologie du web, c'est-à-dire sur l'étude des liens entre les pages. Voici des explications sur la formule initiale du PageRank.

Mise à jour : cet article date de plusieurs années, attention à le lire pour votre culture web personnelle ! En effet bien des choses ont changé et les informations ou techniques décrites ici ne sont plus forcément applicables à 100%... En particulier le PageRank n'est plus un élément capital, de nombreux autres critères sont plus importants. Je vous conseille plutôt de lire mon tutoriel sur le netlinking.

L'idée principale est que si une page A fait un lien vers une page B, alors c'est que la page A juge que la page B est suffisamment importante pour mériter d'être citée et d'être proposée aux visiteurs. Ce lien de A vers B augmente le PageRank de B.

Deux idées supplémentaires mais essentielles viennent la compléter :

• l'augmentation de PageRank de la page B est d'autant plus importante que le PageRank de la page A est élevé. En d'autres termes, il est bien plus efficace d'avoir un lien depuis la page d'accueil de Google que depuis une page du site de votre petit cousin (ou alors c'est un génie en puissance  !).
• l'augmentation de PageRank de la page B est d'autant plus importante que la page A fait peu de liens. En d'autres termes, si la page A juge qu'il n'y a qu'une page qui mérite un lien, alors il est normal que le PageRank de la page B augmente plus que dans le cas où de nombreuses pages obtiennent un lien.

Maintenant que vous connaissez les principes du PageRank, passons à sa formulation mathématique... Nous nous basons sur un article rédigé par les deux fondateurs de Google (1), même si depuis l'algorithme a dû évoluer : la base reste la même.

Soient A1, A2, ..., An : n pages pointant vers une page B. Notons PR(Ak) le PageRank de la page Ak, N(Ak) le nombre de liens sortants présents sur la page Ak, et d un facteur compris entre 0 et 1, fixé en général à 0,85.

Alors le PageRank de la page B se calcule à partir du PageRank de toutes les pages Ak de la manière suivante :

PR(B) = (1-d) + d x ( PR(A1) / N(A1) + ... + PR(An) / N(An) )

Comme vous pouvez vous en rendre compte, cette formule est à la fois simple et compliquée. Simple parce qu'elle ne dépend que de quelques termes, compliquée parce qu'elle récursive : pour calculer le PageRank d'une page, il faut avoir calculé celui de toutes les pages pointant vers elle. Mais alors comment commencer ?

En fait c'est très simple, il suffit de commencer avec des valeurs arbitraires de PageRank (par exemple 1). Le choix de cette valeur n'a pas d'influence sur le résultat final à condition que toutes les pages commencent avec la même valeur. Une application de la formule permet de calculer un nouveau PageRank pour chaque page, plus proche de la réalité que la valeur par défaut que nous avons choisie au début.
Ensuite nous recommençons à calculer les PageRank de toutes les pages en appliquant de nouveau la formule, mais en partant cette fois des valeurs que nous avons calculées précédemment. Après un certain nombre d'itérations, le système converge : les valeurs de PageRank de chaque page ne bougent plus entre deux itérations.
En pratique la convergence est obtenue au bout de plusieurs dizaines d'itérations (tout dépend du nombre de pages considérées  !).

Etape suivante : Premières constatations sur le PageRank.

(1) The Anatomy of a Large-Scale Hypertextual Web Search Engine, Sergey Brin et Lawrence Page, www-db.stanford.edu/~backrub/google.html

Si vous souhaitez publier un extrait de cet article sur votre site, assurez-vous de respecter les conditions générales d'utilisation de WebRankInfo.