Système développé
par les fondateurs de Google qui attribue une
notation à une page web en fonction des liens
externes pointant vers cette page et de la
nature des sites sur lesquels ces liens sont
présents. Le PageRank (TM) est un des éléments
influençant fortement la position d’une page
dans les résultats de Google.
Le PageRank (terme anglais signifiant «
classement d'une page ») ou PR désigne l'indice
de popularité d'une page Web utilisé par le
moteur de recherche Google pour le classement de
ses résultats de recherche. PageRank fait aussi
référence à Larry Page cofondateur de Google et
inventeur de ce principe.
Google affecte une note de popularité à chaque
page Web. Cette note est faite en fonction des
liens externes (popularité de liens) pointant
vers elle et des liens qu'elle fait vers
elle-même (liens internes). Dans ce calcul est
intégré un des algorithmes PageRank pour donner
une note stable à chaque page.
Le PageRank réel d'une page n'est connu que de
Google, mais les internautes peuvent obtenir une
approximation du classement de la page en
consultant la zone PageRank de la Google Toolbar,
qui indique sa valeur sur une échelle de 0 à 10
(Échelle logarithmique).
Le PageRank a été un facteur prégnant dans le
classement des résultats de recherche de Google.
C'est moins vrai aujourd'hui.
Les référenceurs ont longtemps créé massivement
des échanges de liens. Google ayant alors une
vision quantitative de la popularité d'une page,
cette technique permettait de gonfler
artificiellement son indice de popularité.
Google a réagi : d'une part en instaurant des
filtres (comme la Sandbox) détectant et
sanctionnant les campagnes massives de liens
artificiels ; d'autre part en intégrant des
critères qualitatifs à l'analyse des liens
(sémantique, confiance : indice TrustRank).
Consultez également notre définition concernant
le TrustRank.
Améliorer la "pertinence" des résultats
constitue un objectif technologique majeur pour
la plupart des moteurs de recherche. Le
problème, c’est que cette "pertinence" est une
notion purement subjective, qu’il est donc
difficile de manier avec des algorithmes
purement mathématiques.
Le moteur de recherche Google, notammment,
cherche depuis plusieurs années une solution à
ce problème. Les premières pistes en ce sens ont
été lancées par Larry Page, dans une publication
publiée alors qu’il était encore étudiant à
l’université de Stanford.
Stanford conserve depuis l’époque de Page et
Brin, les fondateurs de Google, un département
de recherche consacré au Pagerank. Depuis deux
ans, une nouvelle équipe de chercheurs a ouvert
la voie à des solutions permettant de calculer
des PageRank personnalisés, et donc d’affiner,
avec une économie de moyens remarquable, les
pages de résultats des moteurs dans un contexte
donné.
Ces travaux sont mal connus, en dehors du cercle
des spécialistes et ne sont pas tous encore
utilisés par les moteurs. Mais il y’a fort à
parier que les premiers moteurs thématiques,
construits autour de ce type d’algorithme, ne
devraient pas tarder à sortir : certains des
chercheurs de Stanford ont constitué en juin
2003 la société Kaltix, rachetée par Google fin
septembre 2003...
Les avantages et les limites du Pagerank
L’algorithme du Pagerank : la force brute du
calcul au service de la pertinence des résultats
Google a construit son succès autour d’un
algorithme de calcul permettant de stocker dans
l’index du moteur, avec chaque page, une
"valeur" indicative de l’"importance" de ces
pages sur le web. On se référera aux excellents
articles de Dan Hetzel pour en comprendre les
principes [1] Cette valeur part du principe
intuitif que l’importance d’une page dépend du
nombre de liens entrants pointant vers cette
page, mais aussi de l’importance des pages d’où
partent ces liens.
Calculer un Pagerank pour une page demande donc
un calcul itératif, puisque doter une page d’un
pagerank modifie par ricochet le pagerank de
toutes les pages vers lesquelles pointe un lien
de cette même page, et de toutes les pages
reliées à ces pages. Toute modification du
pagerank d’une page se "propage" donc au fil des
liens de page en page... Mais si l’une des pages
ainsi reliée, quel que soit le nombre de liens
qui la sépare de la page dont on a calculé le
pagerank, contient un lien réciproque vers la
page de départ, cela modifie également le
pagerank de la page de départ.
L’algorithme itératif de calcul du Pagerank
converge au bout d’un certain nombre
d’itérations, vers une valeur fixe. Le problème,
c’est que cette "convergence" de la suite des
résultats n’est pas assurée en théorie (mais
elle l’est dans la pratique compte tenu de la
structure réelle du web) et la "vitesse de
convergence" (le nombre d’itérations pour
atteindre une valeur précise proche de la
limite) est très variable suivant les zones du
web.
Le calcul du Pagerank nécessite du temps et une
puissance de calcul phénomale
La puissance de calcul nécessaire pour calculer
le Pagerank pour un index de la taille de Google
est assez fantastique. Mais heureusement, il
s’agit essentiellement de calculs matriciels
très simples, qui sont facilement gérables avec
une architecture basée sur un grand nombre de
machines calculant chacune les valeurs pour une
petite zone de la colossale matrice du web.
Selon quelques "fuites" en provenance du
Googleplex, le temps de calcul nécessaire pour
calculer le PageRank de toutes les pages du Web
indexées prenait jusqu’à une bonne semaine...
(La méthode utilisée a changé au printemps 2003,
on le verra plus loin.)
Par contre, une fois ce calcul effectué, le
pagerank est stocké dans l’index avec les pages,
et est donc disponible pour affiner le calcul
des positions sur les pages de résultats, qui
dépend aussi d’autres critères plus classiques,
mais propres à chaque page, comme la densité de
mots clés par exemple.
L’architecture d’un moteur basé sur le Pagerank
La méthode imaginée par Page et Brin a deux
vertus : les calculs les plus complexes et les
plus longs se font offline. Le moteur n’a plus
que des calculs très simples à effectuer pour
construire les pages de résultats à la volée.
Ensuite, la prise en compte du seul "nombre de
liens" comme critère permet une totale
modélisation mathématique du calcul de la
"valeur d’une page". Sur le plan théorique, le
PageRank est un calcul qui mesure les
conséquences du comportement d’un internaute
téléporté au hasard de page en page au hasard
des liens qui les relient.
Les limites du PageRank
Sur le plan théorique, le postulat de Brin et
Page selon lequel la valeur des pages dépend du
nombre de liens entrants a été critiqué dès 1999
par les chercheurs du laboratoire Almaden d’IBM.
Ces critiques portaient sur deux points :
ce postulat fait fi de la véritable structure du
web, qui n’est pas uniformément reliée par des
liens hypertextes.
le pagerank n’apporte aucune info sémantique, et
est susceptible de donner de l’importance à des
pages qui n’en ont pas
On peut vérifier dans la pratique la justesse de
ces remarques en consultant les pages de
résultats renvoyées par Google.
Suite de l’article (Deuxième partie) :
Les différentes pistes pour calculer un PageRank
Personnalisé
