METHODES D'EXTRAPOLATION POUR LE CLASSEMENT DES PAGES DU WEB

Michela Redivo-Zaglia
Université de Padoue, Italie

Un problème important dans la recheche sur le web est de classer les pages 
par ordre décroissant d'importance.
Du point de vue mathématique, cela consiste à calculer le vecteur propre 
dominant d'une matrice stochastique.
Cette matrice n'étant pas réductible, on la modifie en y introduisant un 
paramètre c qui redonne le problème initial lorqu'il tend vers 1. 
Google choisit c=0.85.
On calcule ensuite le vecteur propre dominant de cette nouvelle matrice 
(le vecteur PageRank) à l'aide de la méthode de la puissance. Cependant, 
lorsque c est voisin de 1, le probème devient mal conditionné et, de plus, 
la méthode de la puissance converge lentement (comme c^n).

Dans ce travail, nous proposons de calculer le vecteur PageRank pour 
différentes valeurs de c petites, puis d'extrapoler ensuite ces vecteurs 
en 0.85 (ou en un autre point). Naturellement, pour que cette extrapolation
fournisse de bons résultats, il est nécessaire que la fonction par laquelle 
on extrapole représente de manière approchée le véritable comportement du 
vecteur PageRank en fonction de c.
Après avoir anlysé ce comportement, nous donnerons un certain nombre de 
procédures d'extrapolation sur cette idée.
Des résultats d'expériences numériques seront présentés.
Ce travail a été fait en collaboration avec Claude Brezinski.