La lecture à portée de main
Description
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.