par
le classement des pages
par les moteurs de recherche
Les pages du Web sont innombrables. Pourtant, les moteurs
de recherche comme Google les classent en une fraction de
seconde. Ils sont capables de repérer les pages les plus
populaires, aussi bien que celles qui se cache nt ...
L
es moteurs de recherche comme
G oog le utili se nt le gra phe du
We b (vo ir l'encadré) pour proposer une li ste de pages tra itant d ' un
sujet donné, en les cl assant selo n le urs
degrés de pertinence . Par exe mple , si
l'on effectue une recherche du mot « tangente » (le 4 juin 2014), on obtient 1,73
milli o n d e rés ult a ts e n un qu a rt d e
le produit matriciel
Au centre du calcul effectué dans notre exemple se trouve la matrice
( 0 1/ 2 0 0 \
l
l
O li 3 01
d
' 1 dis 'b . d
d
M -
correspon ant a a tn ution es scores e
0
0
1 / 3 0
0 1/ 2 1/ 3 1
chaque page. C'est pourquoi la somme des termes de chaque
l
( : ~ :J \
colonne est égale à 1. Partant de la distribution initiale X -
1 14
,
1 / 4
les distributions suivantes sont MX, M
2 X, M3X, etc. où le produit
matriciel s'opère de la façon suivante :
l
( :: :: ~ ::'Jl ( ~ \
J = ( l :::: : :::: : ~;: : :::: \ J .
d, d 2 d 3 d 4 x 4
d 1 x 1 + d 2 x 2 + d 3 x 3 + d 4 x 4
La stabilisation des pages dépend donc des puissances de la matrice
M. La question se trouve ainsi liée aux valeurs propres de M et on
montre que, en général, cette suite converge ( voir le Théorème de
Perron-Frobenius dans Tangente Sup 44-45).
seco nd e ! Le pre mi er es t l'artic le de
Wikipédi a, qui concerne la géo métrie,
le de uxiè me concern e un magazine de
culture math é matique. D ' où vient ce
cl asseme nt ? La ré ponse est qu ' il est
dû aux intern autes e ux- mêmes, qui fo nt
po inter le urs pages ou non vers te ll e ou
te lle autre. C haque page a ainsi un score
se lo n le no mbre de pages po inta nt ve rs
e ll e, score qu 'e lle di stribue à ce ll es sur
lesque ll es e ll es po intent.
le mode de calcul
Pour préc iser les ca lcul s, imag inons la
parti e du We b tra itant du sujet cherché
limitée à quatre pages.
Pour simplifier, les pages sont dés ignées
par des lettres . Les fl èches dés ignent les
pages vers lesquelles chaque page pointe,
c'est-à-dire les pages auxquelles on peut
accéder en un c li c de souri s.
A
le classement des pages
par les moteurs de recherche
Les pages du Web sont innombrables. Pourtant, les moteurs
de recherche comme Google les classent en une fraction de
seconde. Ils sont capables de repérer les pages les plus
populaires, aussi bien que celles qui se cache nt ...
L
es moteurs de recherche comme
G oog le utili se nt le gra phe du
We b (vo ir l'encadré) pour proposer une li ste de pages tra itant d ' un
sujet donné, en les cl assant selo n le urs
degrés de pertinence . Par exe mple , si
l'on effectue une recherche du mot « tangente » (le 4 juin 2014), on obtient 1,73
milli o n d e rés ult a ts e n un qu a rt d e
le produit matriciel
Au centre du calcul effectué dans notre exemple se trouve la matrice
( 0 1/ 2 0 0 \
l
l
O li 3 01
d
' 1 dis 'b . d
d
M -
correspon ant a a tn ution es scores e
0
0
1 / 3 0
0 1/ 2 1/ 3 1
chaque page. C'est pourquoi la somme des termes de chaque
l
( : ~ :J \
colonne est égale à 1. Partant de la distribution initiale X -
1 14
,
1 / 4
les distributions suivantes sont MX, M
2 X, M3X, etc. où le produit
matriciel s'opère de la façon suivante :
l
( :: :: ~ ::'Jl ( ~ \
J = ( l :::: : :::: : ~;: : :::: \ J .
d, d 2 d 3 d 4 x 4
d 1 x 1 + d 2 x 2 + d 3 x 3 + d 4 x 4
La stabilisation des pages dépend donc des puissances de la matrice
M. La question se trouve ainsi liée aux valeurs propres de M et on
montre que, en général, cette suite converge ( voir le Théorème de
Perron-Frobenius dans Tangente Sup 44-45).
seco nd e ! Le pre mi er es t l'artic le de
Wikipédi a, qui concerne la géo métrie,
le de uxiè me concern e un magazine de
culture math é matique. D ' où vient ce
cl asseme nt ? La ré ponse est qu ' il est
dû aux intern autes e ux- mêmes, qui fo nt
po inter le urs pages ou non vers te ll e ou
te lle autre. C haque page a ainsi un score
se lo n le no mbre de pages po inta nt ve rs
e ll e, score qu 'e lle di stribue à ce ll es sur
lesque ll es e ll es po intent.
le mode de calcul
Pour préc iser les ca lcul s, imag inons la
parti e du We b tra itant du sujet cherché
limitée à quatre pages.
Pour simplifier, les pages sont dés ignées
par des lettres . Les fl èches dés ignent les
pages vers lesquelles chaque page pointe,
c'est-à-dire les pages auxquelles on peut
accéder en un c li c de souri s.
A