Upload
vuonganh
View
229
Download
0
Embed Size (px)
Citation preview
Pertinence d’une page web
Présentation historique du web
Le World Wide Web (WWW), littéralement la « toile (d’araignée) mondiale », communément appelé le web, est un système hypertexte public fonctionnant sur internet qui permet de consulter des contenus avec un navigateur.
Pertinence d’une page web
Présentation historique du web
Le 13 mars 1989, Tim Berners-Lee, engagé au CERN à Genève en 1984 pour travailler sur l’acquisition et le traitement des données, propose de développer un système hypertexte organisé en Web, afin d’améliorer la diffusion des informations internes.
Pertinence d’une page web
Présentation historique du web
Le 6 août 1991, Tim Berners-Lee rend le projet WorldWideWeb public dans un message sur Usenet.
Pertinence d’une page web
Les moteurs de recherche avant Google
Un nouvel algorithme : motivations de la recherche
Pertinence d’une page web
La formule introduite par Sergueï Brin et Larry Page dans l’article fondateur
Un outil majeur : l’algèbre linéaire
1 2
1 2
1( ) n
n
PR T PR T PR TdPR A d
N L T L T L T
L
Mesurer l’importance d’une page web
Le comptage récursif
Une page j est importante si beaucoup de pages importantes pointent vers j.
On tient compte de l’importance de la page d’origine i et du nombre de liens qui en sont émis.
Mesurer l’importance d’une page web
Le comptage récursif :
avec
1
1n
j i j ii
a j n
1
si
0 sinonii j
i jla
Mesurer l’importance d’une page web
Le comptage récursif :Les coefficients vérifient :
La matrice A constituée par ces coefficients est une matrice stochastique.
1
0 pour tout , et
1 pour tout
i j
n
i jj
a i j
a i
Mesurer l’importance d’une page web
Le comptage récursif :
système linéaire de n équations à n inconnues (les μi)
où W est la matrice ligne ayant pour coefficients les μi
W WA
Mesurer l’importance d’une page web
Le comptage récursif : interprétation probabilité d’aller de la page i à la page j, en suivant un des liens au hasard
On modélise ainsi un surfeur aléatoire.
i ja
Mesurer l’importance d’une page web
Le comptage récursif : si l’on note Xp la position du surfeur après p étapes :
soit
1 11
p
n
p p pX ii
P X j P X j P X i
11
n
p i j pi
P X j a P X i
Mesurer l’importance d’une page web
Le comptage récursif :
où Up désigne la matrice ligne ayant pour i-ème coefficient
1p pU U A
pP X i
Mesurer l’importance d’une page web
Le comptage récursif :
où Up désigne la matrice ligne ayant pour i-ème coefficient
0p
pU U A
pP X i
Mesurer l’importance d’une page web
Un modèle plus raffiné : introduction du coefficient de téléportation avec probabilité c, le surfeur abandonne la
page actuelle et recommence sur une des n pages du web, choisie de manière équiprobable ;
avec probabilité 1 c, le surfeur suit un des liens de la page actuelle j, choisi de manière équiprobable parmi tous les liens émis.
Mesurer l’importance d’une page web
On obtient :
ou encore
puisque
11
1n
p i j pi
cP X j c a P X i
n
11
1n
p i j pi
cP X j c a P X i
n
1
1n
pi
P X i
Mesurer l’importance d’une page web
Cela se traduit par la relation matricielle :
où J désigne la matrice carrée de format (n,n) dont tous les coefficients sont égaux à 1.
1 1p p
cU U J c A
n
Mesurer l’importance d’une page web
Suite de matrices lignes de type arithmético-géométrique
on commence par chercher un point fixe : H en posant : , on obtient :
puis
p pV U H
01p p
pV c V A
01p p
pU c U H A H
Mesurer l’importance d’une page web
La constante c est un paramètre du modèle.
c=0,15 correspond à suivre environ 6 liens en moyenne.