Google PageRank ou une facon de classer les pages web

Olivier Guibé

Description

Les moteurs de recherche tels que Yahoo, Altavista, Lycos ont ete depasses par Google.

Informations

• Publié par: Force_IT
• Nombre de lectures: 10
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

GooglePageRankouunefac¸ondeclasser
les pages web

´
Olivier GUIBE
LaboratoiredeMath´ematiquesRaphae¨lSalem
CNRS-Universite´deRouen

Gre`vedef´evrier2009

Pour celles et ceux qui se
souviennent

LesmoteursderecherchetelsqueYahoo,Altavista,Lycosonte´t´e
d´epass´esparGoogle:
•tenirBraegaPglooeGnd8p99n1eerce´taoi
•origine du PageRank : article de Brin et Page«The Anatomy
of a Large-Scale Hypertextual Web Search Engine», Stanford
University, 1998
•esirean´lireebg`alspagntdesemeclasuq:ehtimogir,ela
–souvent– pertinent

But

Un algorithme qui permet de classer les pages web
•uepiuq)smevetieceffreettˆemtne´n(tnmilpe´erronspaousnelev
•donner un (unique) classement pertinent pour l’utilisateur
Nousnenousint´eresseronspasaucontenu(c’estuntort).

Ide´e
Une«heecfl`»de 1 vers 2 veut dire que la page 1 contient un lien
verslapage2,etc.Voiciunmod`eletre`sr´eduit!

Plus une page est la cible de liens venant d’autres pages plus
elleadechanced’eˆtrefiableetinte´ressante

Mais

Un classement qui ne tient compte que du nombre de liens :
•ı¨ftrnaop
•facile d’augmenter le rang d’une pageAcneedtnae´resagsp
qui pointent versA
•opene´dnatuaucevmeˆeefd´mnesbneredilnctiondurationfo
sur les pages
Lapage4seraitclasse´een1eralorsque7et8semblentplus
pertinentes.
Il serait moins na¨ıf de demander :
une pageiest importante si beaucoup de pages importantes
pointent versi

Transformation en un tableau
ou une matrice
TableauCo`ucij(lignei, colonnej) contient 1 sijpointe suriet 0
sinon.
Ond´ecidequecii=0 ;ne pas tenir compte des liens internes.

Transformation en un tableau
ou une matrice
TableauCou`cij(lignei, colonnej) contient 1 sijpointe suriet 0
sinon.
Ond´ecidequecii=0 ;ne pas tenir compte des liens internes.
 
0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 1 0 1 0
 
 
0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0

Beaucoupdez´eros!

Transformation en un tableau
ou une matrice
TableauCu`ocij(lignei, colonnej) contient 1 sijpointe suriet 0
sinon.
Onde´cidequecii=ne pas tenir compte des liens internes.0 ;
on compte le nombre de liens sur chaque page (en colonne)
 
0 00 0 0 0 0 0 0 0
1 00 1 0 0 0 0 0 0
0 10 0 0 0 0 0 0 0
1 11 0 0 0 0 0 0 1
1 00 0 0 1 0 0 0 0
0 00 0 1 0 0 0 0 0
0 00 1 0 1 0 0 1 0
0 00 0 0 0 1 0 1 0
 
 
0 00 0 0 0 0 1 0 0
0 01 0 0 0 0 0 0 0
 
3 22 2 1 2 1 1 2 1
N1N2

Score de pertinence

On cherche le rang de chaque pagei,´toneriruotturi´epofie,ivqu
i∈ {1, . . . ,N}
N
X
cij
ri=rj
Nj
j=1

•iodssuoctp`elafatientcomlasommepauegedereaqch
ponde´re´aveclenbredeliens
siNj=arıˆpaapem’ntere0lemmsolansdaastp
•
•l’ajout de pages«vides de sens»eratr`espeulerangmdofii
(auront unrjdeheerz´o)corp
•dre!esoucst’eqeaunu´ea`´ritno

Des maths!

Posons la matriceQ
 
0 0 0 00 0 00 0 0
1/3 00 1/0 0 00 02 0
0 1/0 0 00 0 0 02 0
1/3 1/2 1/2 0 0 0 00 0 1
1/0 13 00 0/0 02 0 0
Q=
0 0 0 01 0 00 0 0
0 0 01/2 0 1/2 0 0 1/2 0
0 0 0 00 0 10 1/2 0
 
 
0 0 0 00 0 01 0 0
0 01/2 0 0 0 00 0 0
Notreproble`merevient`atrouverunvecteurresntsaopmoca`
positivesve´rifiantQr=r.rest vecteur propre deQssa´icola`ea
valeur propre 1.