COMMENT FONCTIONNE GOOGLE?

COMMENT FONCTIONNE GOOGLE?
MICHAEL EISERMANN

AGGOUNI  MOHAMED

 
R´ESUM´E. Le point fort du moteur de recherche Google est qu’il trie intelligemment ses r´esultats par
ordre d’importance. Nous expliquons ici l’algorithme PageRank qui est `a la base de ce classement. Il
faut d’abord ´etablir un mod`ele qui permet de d´efinir ce que l’on entend par « importance ». Une fois ce
mod`ele formalis´e, il s’agit de r´esoudre astucieusement un immense syst`eme d’´equations lin´eaires.
Il va sans dire que l’application pratique est devenue tr`es importante. Bien qu’´el´ementaires, les
arguments math´ematiques sous-jacents n’en sont pas moins int´eressants : l’approche fait

naturellement
intervenir l’alg`ebre lin´eaire, la « marche al´eatoire » sur un graphe et le th´eor`eme du point fixe. Tout ceci
en fait un tr`es beau sujet pour la culture des math´ematiques et leurs applications.
TABLE DES MATI`ERES
Introduction 1
1. Que fait un moteur de recherche ? 2
2. Comment mesurer l’importance d’une page web ? 3
3. Marche al´eatoire sur la toile 6
4. Existence et unicit´e d’une solution 8
5. Impl´ementation efficace 11
6. Quelques points de r´eflexion 12
R´ef´erences 15
INTRODUCTION
Cet article discute les math´ematiques utilis´ees par Google, un moteur de
recherche g´en´eraliste qui a eu un succ`es fulgurant depuis sa cr´eation en
1998. Le point fort de Google est qu’il trie par ordre d’importance les
r´esultats d’une requˆete, c’est-`a-dire les pages web associ´ees aux motscl
´es cherch´es. L’´etonnante efficacit´e de cette m´ethode a fait le succ`es de Google et la fortune de ses
fondateurs, Sergey Brin et Lawrence Page. L’id´ee est n´ee lors de leur th`ese de doctorat, puis publi´ee
dans leur article [1]. Il s’agit essentiellement de r´esoudre un grand syst`eme d’´equations lin´eaires et
fort heureusement l’algorithme it´eratif qui en d´ecoule est aussi simple que puissant. On s’int´eresse ici
de plus pr`es `a cet algorithme, `a la fois simple et ing´enieux. En conjonction avec une habile strat´egie
d’entreprise, on pourrait dire que Google gagne des milliards de dollars avec l’alg`ebre lin´eaire !
Ajoutons que Google a eu la chance de naˆıtre dans une situation favorable, quand la « nouvelle
´economie » ´etait encore en pleine croissance : le volume d’internet explosait et les moteurs de recherche
de premi`ere g´en´eration avaient du mal `a s’adapter aux exigences grandissantes. Si vous voulez
savoir plus sur la foudroyante histoire de l’entreprise Google, ses l´egendes et anecdotes, vous lirez
avec profit le livre de David Vise et Mark Malseed [2].
Date: 16 mai 2006. Derni`ere mise `a jour: 13 mai 2009. URL: www-fourier.ujf-grenoble.fr/~eiserm
Universit´e Joseph Fourier Licence de Math´ematiques cours « Math´ematiques assist´ees par ordinateur ».
1
2 MICHAEL EISERMANN
1. QUE FAIT UN MOTEUR DE RECHERCHE ?
1.1. Fouille de donn´ees. `A premi`ere vue, le principe d’un moteur
de recherche est simple : on copie d’abord les pages web concern´ees
en m´emoire locale, puis on trie le contenu (les mots-cl´es) par ordre
alphab´etique afin d’effectuer des recherches lexiques. Une requˆete est
la donn´ee d’un ou plusieurs mots-cl´es ; la r´eponse est une liste des
pages contenant les mots-cl´es recherch´es. C’est en gros ce que faisaient les moteurs de recherche,
dits de premi`ere g´en´eration, dans les ann´ees 1990. Apr`es r´eflexion, cette d´emarche simpliste n’est
pas si ´evidente car la quantit´e des documents `a g´erer est ´enorme et rien que le stockage et la gestion
efficaces posent des d´efis consid´erables. Et cela d’autant plus que les requˆetes doivent ˆetre trait´ees en
temps r´eel : on ne veut pas la r´eponse dans une semaine, mais tout de suite.
Une impl´ementation op´erationnelle `a cette ´echelle doit donc employer la force brute d’un r´eseau
puissant, afin de r´epartir les donn´ees et les tˆaches sur plusieurs ordinateurs travaillant en parall`ele.
Plus important encore sont les algorithmes, hautement sp´ecialis´es et optimis´es, sans lesquels mˆeme
un r´eseau de quelques milliers d’ordinateurs resterait impuissant devant cette tˆache hercul´eenne. Pour
se faire une id´ee de l’ordre de grandeur, voici quelques chiffres sur l’entreprise Google :
Cerveaux: environ 6 000 employ´es (d´ebut 2006)
Ordinateurs: plus de 60 000 PC en r´eseau sous Linux (on ignore les chiffres exacts)
M´emoire vive: plus de 130 000 Go de RAM pour les calculs (on ignore les chiffres exacts)
Disques dures: plus de 5 000 000 Go pour stocker les donn´ees (on ignore les chiffres exacts)
Trafic en ligne: quelques milliers de requˆetes par secondes (on ignore les chiffres exacts)
Part du march´e: plus de 50% aux ´ Etats-Unis et dans de nombreux autres pays
Chiffre d’affaires: plus de $6 000 000 000 en 2005, dont $1 465 400 000 b´en´efices net
Cotation boursi`ere: environ $80 000 000 000 en aoˆut 2005
Pr´ecisons que la recherche sur Google est un service gratuit. En 1998 il n’´etait pas du tout ´evident
comment gagner de l’argent avec un produit gratuit, aussi appr´eci´e qu’il soit. Jusqu’en 2000 l’entreprise
accumulait des pertes et fut mˆeme menac´ee de faillite. L’id´ee qui l’a sauv´ee a ´et´e la vente de
liens commerciaux et depuis 2001 ces placements publicitaires g´en`erent de plus en plus de b´en´efices.
1.2. Classement des r´esultats. L’´enorme quantit´e des donn´ees entraˆıne un deuxi`eme probl`eme, plus
d´elicat encore : les pages trouv´ees sont souvent trop nombreuses, il faut donc en choisir les plus pertinentes.
La grande innovation apport´ee par Google en 1998 est le tri des pages par ordre d’importance.
Ce qui est frappant est que cet ordre correspond assez pr´ecis´ement aux attentes des utilisateurs.
Par exemple, si vous vous int´eressez `a la programmation et vous faites chercher les mots-cl´es « C++
compiler », vous trouverez quelques millions de pages. Des pages importantes comme gcc.gnu.org
se trouvent quelque part en tˆete du classement, ce qui est tr`es raisonnable. Par contre, une petite page
personnelle, o`u l’auteur mentionne qu’il ne connaˆıt rien du C++ et n’arrive pas `a compiler, ne figurera
que vers la fin de la liste, ce qui est ´egalement raisonnable. Comment Google distingue-t-il les deux ?
Selon les informations fournies par l’entreprise elle-mˆeme, l’index de Google porte sur plus de 8
milliards de documents web. Une bonne partie des informations r´epertori´ees, pages web et documents
annexes, changent fr´equemment. Il est donc hors de question de les classer manuellement, par des
ˆetres humains : ce serait trop coˆuteux, trop lent et jamais `a jour. L’importance d’une page doit donc
ˆetre d´etermin´ee de mani`ere automatis´ee, par un algorithme. Comment est-ce possible ?
COMMENT FONCTIONNE GOOGLE? 3
2. COMMENT MESURER L’IMPORTANCE D’UNE PAGE WEB ?
2.1. Le web est un graphe. La particularit´e des documents hypertexte
est qu’ils fournissent des liens, des r´ef´erences mutuelles pointant de l’une
vers l’autre. Ainsi on peut consid´erer le web comme un immense graphe,
dont chaque page web j est un sommet et chaque lien j!i est une arˆete.
2 3 4 5
1 7 8
6
9 10
11 12 13 14
FIG. 1. Le web vu comme un graphe
Dans la suite on num´erote les pages par 1;2;3; : : : ;n et on ´ecrit j ! i si la page j pointe vers la
page i (au moins une fois ; on ne compte pas les liens multiples). Ainsi chaque page j ´emet un certains
nombre ` j de liens vers des pages « voisines ». `A noter que les arˆetes sont orient´ees : si l’on a j !i,
on n’a pas forc´ement le sens inverse i! j. Le graphe de la figure 1, par exemple, s’´ecrit comme suit :
1!2;3;4;5;6 ; 2!1;3 ; 3!1;4 ; 4!1;5 ; 5!1;2 ; 6!7;8;9 ; 7!8;1 ; 8!6 ;
9!8;10 ; 10!6;11;12;13;14 ; 11!10;12 ; 12!10;13 ; 13!10;14 ; 14!10; 11.
2.2. Comment rep´erer des pages importantes ? Dans une premi`ere approximation nous allons
n´egliger le contenu des pages et ne tenir compte que de la structure du graphe.
– Regardons d’abord le groupe des pages 1;2;3;4; 5. Le dessin sugg`ere que la page 1 sert de racine
tandis que les pages 2;3;4;5 sont subordonn´ees. Dans ce sens, la page 1 sera sans doute un bon
point de d´epart si vous cherchez des informations.
– Il en est de mˆeme pour le groupe 10;11;12;13; 14, o`u la page 10 sert de racine alors que
11;12;13;14 sont subordonn´ees. `A titre d’exemple, il pourrait s’agir d’une page d’accueil et
quatre pages annexes, ou d’une introduction et quatre chapitres d’un ouvrage.
– La structure du groupe 6;7;8;9 est similaire. `A noter toutefois que les pages 1 et 10, d´ej`a reconnues
comme importantes, font toutes deux r´ef´erence `a la page 6. On pourrait ainsi soupc¸onner
que la page 6 contient de l’information essentielle pour tout l’ensemble.
Heuristiquement, on conclut que les pages 1;6;10 semblent les plus importantes, avec une l´eg`ere
pr´ef´erence pour la page 6. Soulignons toutefois que notre dessin dans le plan sugg`ere une organisation
hi´erarchique qui n’est qu’artificielle. Un ordinateur qui analyse cette situation n’a que l’information
brute des liens 1!2;3;4;5;6 ; 2!1;3 ; etc.
Question 1. Est-il possible, par un algorithme, d’associer `a chaque page i = 1; : : : ;n une mesure
d’importance ? Plus explicitement, on souhaite que cette mesure soit un nombre r´eel mi 0 avec la
convention que plus mi est grand, plus la page i est « importante ».
4 MICHAEL EISERMANN
Remarque 2. La notion d’importance d’une page est n´ecessairement vague. Qu’est-ce que l’importance
? Peut-il y avoir une mesure objective ? Si oui, comment la d´efinir ? Cette question semble au
coeur de toute la probl´ematique. Si vous avez une nouvelle id´ee pertinente `a ce sujet, impl´ementez-la
et devenez riche ! (Ou bien venez en discuter avec moi.)
Dans la suite notre but sera modeste : le mieux que l’on puisse esp´erer est que notre analyse d´egage
un r´esultat qui approche bien l’importance ressentie par les utilisateurs. Pour toute application professionnelle
les r´esultats num´eriques seront `a tester et `a calibrer empiriquement.
2.3. Premi`ere id´ee : comptage des liens. Il est plausible qu’une page importante rec¸oit beaucoup de
liens. Avec un peu de na¨ıvet´e, on croira aussi l’affirmation r´eciproque : si une page rec¸oit beaucoup
de liens, alors elle est importante. Ainsi on pourrait d´efinir l’importance mi de la page i comme suit :
(1) mi = å
j!i
1:
Interpr´etation: La somme (1) veut juste dire que mi est ´egal au nombre de liens j !i rec¸us par i.
C’est facile `a d´efinir et facile `a calculer : il suffit de compter.
Exemple: Dans notre exemple, les pages 1 et 10 rec¸oivent 5 liens chacune, alors que la page 6
n’en rec¸oit que 3. Ainsi m1 = m10 = 5 mais seulement m6 = 3.
Inconv´enient: La mesure m ainsi d´efinie ne correspond pas `a l’importance ressentie par les utilisateurs
: elle sous-estime l’importance de la page 6.
Manipulation: On peut artificiellement augmenter l’importance d’une page i en cr´eant des pages
« vides de sens » pointant vers i. Cette faiblesse fait du comptage une approche peu fiable.
2.4. Seconde id´ee : comptage pond´er´e. Certaines pages j ´emettent beaucoup de liens : ceux-ci sont
donc moins sp´ecifiques et dans un certain sens leur poids est plus faible. Ainsi on pourrait d´efinir une
mesure d’importance plus fine comme suit :
(2) mi = å
j!i
1
` j
:
Interpr´etation: Comme avant, la somme (2) compte les liens rec¸us par la page i, mais maintenant
chaque lien j!i n’est compt´e qu’avec un poids 1
` j . Il suffit de sommer.
Exemple: Dans notre exemple, on trouve des sommes m1 = m10 = 2:5 et m6 = 1:4.
Inconv´enient: La mesure m ainsi d´efinie ne correspond toujours pas bien `a l’importance ressentie
par les utilisateurs : elle sous-estime `a nouveau l’importance de la page 6.
Manipulation: Comme avant, on peut artificiellement augmenter l’importance d’une page i en
cr´eant une foule de pages « vides » pointant vers i. De nouveau, la mesure n’est pas fiable.
2.5. Troisi`eme id´ee : d´efinition r´ecursive. La derni`ere id´ee en date, finalement, est celle utilis´ee par
Google. Le principe : une page i est importante si beaucoup de pages importantes pointent vers i.
Ainsi on est amen´e `a d´efinir l’importance mi de mani`ere r´ecursive comme suit :
COMMENT FONCTIONNE GOOGLE? 5
(3) mi = å
j!i
1
` j
mj:
Interpr´etation: La somme (3) compte chaque lien rec¸u par i avec poids 1
` j mj : ceci tient compte de
l’importance mj de la page d’origine j, et du nombre ` j des liens qui en sont ´emis.
Exemple: Dans notre exemple, on trouve, apr`es calcul, les valeurs m6 = 6 et m1 = m10 = 5 puis
m8 = 4. Les autres pages suivent avec un grand ´ecart et n’obtiennent que mi = 2.
Plausibilit´e: Les pages 6;1;10;8 sont effectivement rep´er´ees comme les plus importantes. Ceci
veut dire que la mesure m ainsi obtenue correspond assez bien `a l’importance ressentie par les
utilisateurs, comme motiv´ee ci-dessus. (On discutera pourquoi au x6.)
Robustesse: Si l’on ajoute des pages « vides de sens » elles recevront l’importance 0 et ne contribueront
pas au calcul. Ainsi la manipulation ´evidente n’influence plus le r´esultat.
L’´equation (3) est facile `a ´ecrire mais moins ´evidente `a r´esoudre : na¨ıvement parlant, pour calculer
mi il faut d’abord connaˆıtre les termes de droite, donc les mj, ce qui a l’air circulaire. . . Notre objectif
est donc d’expliquer pourquoi une solution existe et comment la calculer de mani`ere efficace.
2.6. Apparaˆıt l’alg`ebre lin´eaire. . . Apr`es r´eflexion, l’´equation (3) n’est rien autre qu’un syst`eme
d’´equations lin´eaires. Plus explicitement, pour tout couple d’indices i; j 2 f1; : : : ;ng, on d´efinit ai j par
(4) ai j :=
(
1
` j si j!i,
0 sinon.
On obtient ainsi une matrice A = (ai j), et notre ´equation (3) s’´ecrit comme
m = Am ou encore (A􀀀I)m = 0;
ce qui est un honnˆete syst`eme lin´eaire, que l’on peut r´esoudre par des m´ethodes ad´equates.
Exemple 3. Dans notre exemple, A est la matrice 14 14 explicit´ee ci-dessous et l’´equation m = Am
admet la solution ´enonc´ee. (Le v´erifier !) C’est mˆeme la seule `a multiplication par un scalaire pr`es.
A =
0
BBBBBBBBBBBBBB@
0 1=2 1=2 1=2 1=2 0 1=2 0 0 0 0 0 0 0
1=5 0 0 0 1=2 0 0 0 0 0 0 0 0 0
1=5 1=2 0 0 0 0 0 0 0 0 0 0 0 0
1=5 0 1=2 0 0 0 0 0 0 0 0 0 0 0
1=5 0 0 1=2 0 0 0 0 0 0 0 0 0 0
1=5 0 0 0 0 0 0 1 0 1=5 0 0 0 0
0 0 0 0 0 1=3 0 0 0 0 0 0 0 0
0 0 0 0 0 1=3 1=2 0 1=2 0 0 0 0 0
0 0 0 0 0 1=3 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1=2 0 1=2 1=2 1=2 1=2
0 0 0 0 0 0 0 0 0 1=5 0 0 0 1=2
0 0 0 0 0 0 0 0 0 1=5 1=2 0 0 0
0 0 0 0 0 0 0 0 0 1=5 0 1=2 0 0
0 0 0 0 0 0 0 0 0 1=5 0 0 1=2 0
1
CCCCCCCCCCCCCCA
; m =
0
BBBBBBBBBBBBBB@
52222624252222
1
CCCCCCCCCCCCCCA
:
D´efinition 4. Soit A 2 Rn n une matrice et soit v 2 Rnrf0g un vecteur non nul. Si Av = lv pour un
scalaire l 2 R, alors on dit que v est un vecteur propre de la matrice A, associ´e `a la valeur propre l.
Pour notre application, nous nous int´eressons donc aux vecteurs propres de A associ´e `a l = 1. On
montrera plus bas qu’un tel vecteur propre existe et que la solution est essentiellement unique (x4.2).
6 MICHAEL EISERMANN
3. MARCHE AL´E ATOIRE SUR LA TOILE
3.1. Matrices stochastiques. Les arguments du x2 nous m`enent `a
´etudier une certaine matrice A qui code la structure du web. Avant
de r´esoudre l’´equation Am = m, on va essayer d’en d´evelopper une
intuition. L’id´ee est de r´einterpr´eter m comme une mesure de « popularit´e » des pages web.
Chaque page j ´emet un certain nombre ` j de liens, ce que l’on code par des coefficients ai j suivant
l’´equation (4) ci-dessus. Par la suite nous supposons que ` j 1, ce qui n’est pas une restriction
s´erieuse : si jamais une page n’´emet pas de liens on peut la faire pointer vers elle-mˆeme.
Selon sa d´efinition, notre matrice A = (ai j) v´erifie
ai j 0 pour tout i; j et
åi
ai j = 1 pour tout j;
ce que l’on appelle une matrice stochastique. (`A noter que la somme de chaque colonne vaut 1, mais
on ne peut en g´en´eral rien dire sur la somme dans une ligne.)
On peut interpr´eter ai j comme la probabilit´e d’aller de la page j `a la page i, en suivant un des ` j liens
au hasard. La marche al´eatoire associ´ee consiste `a se balader sur le graphe suivant les probabilit´es ai j.
Notre mod`ele admet ainsi une ´etonnante interpr´etation probabiliste : aussi ´etrange que cela puisse
apparaˆıtre, on mod´elise un surfeur al´eatoire, qui ne lit jamais rien mais qui clique au hasard !
Soulignons donc `a nouveau que ce n’est pas le contenu des pages web qui soit pris en compte pour
le calcul de « l’importance », mais uniquement la structure du graphe form´e par les pages et les liens
entre elles. (Ne vous faites pas trop de souci pour l’instant, on discutera plus bas, au x6, pourquoi ce
mod`ele est tout de mˆeme plausible.)
3.2. Convergence vers une mesure invariante. Supposons qu’un vecteur x 2 Rn v´erifie
xj 0 pour tout j et å
j
xj = 1;
ce que l’on appelle un vecteur stochastique ou une mesure de probabilit´e sur les pages 1; : : : ;n : on
interpr`ete xj comme la probabilit´e de se trouver sur la page j.
Effectuons un pas dans la marche al´eatoire : avec probabilit´e xj on d´emarre sur la page j, puis on
suit le lien j !i avec probabilit´e ai j. Ce chemin nous fait tomber sur la page i avec une probabilit´e
ai jxj. Au total, la probabilit´e d’arriver sur la page i, par n’importe quel chemin, est la somme
yi =å
j
ai jxj:
Autrement dit, un pas dans la marche al´eatoire correspond `a l’application lin´eaire
T : Rn !Rn; x 7! y = Ax:
Remarque 5. Si x est un vecteur stochastique, alors son image y = Ax aussi. Effectivement, yi 0
car yi = åj ai jxj est une somme de termes positifs ou nuls et, de plus,
åi
yi =å
i
åj
ai jxj =å
j
åi
ai jxj =å
j

åi
ai j

xj =å
j
xj = 1:
COMMENT FONCTIONNE GOOGLE? 7
D´efinition 6. Une mesure de probabilit´e m v´erifiant m = T(m) est appel´ee une mesure invariante
ou une mesure d’´equilibre. En termes d’alg`ebre lin´eaire c’est un vecteur propre associ´e `a la valeur
propre 1. En termes d’analyse, m est un point fixe de l’application T.
Exemple 7. It´erer la marche al´eatoire avec une probabilit´e initiale u0 veut dire que l’on consid`ere les
mesures de probabilit´es successives u1, u2, u3, . . . d´efinies par ut+1 =Aut . Voici un exemple d´emarrant
sur la page 8, c’est-`a-dire u0 = (0;0;0;0;0;0;0;1;0;0;0;0;0;0) :
temps page 1 page 2 page 3 page 4 page 5 page 6 page 7 page 8 page 9 page 10 page 11 page 12 page 13 page 14
t=0 0:000 0:000 0:000 0:000 0:000 0:000 0:000 1:000 0:000 0:000 0:000 0:000 0:000 0:000
t=1 0:000 0:000 0:000 0:000 0:000 1:000 0:000 0:000 0:000 0:000 0:000 0:000 0:000 0:000
t=2 0:000 0:000 0:000 0:000 0:000 0:000 0:333 0:333 0:333 0:000 0:000 0:000 0:000 0:000
t=3 0:167 0:000 0:000 0:000 0:000 0:333 0:000 0:333 0:000 0:167 0:000 0:000 0:000 0:000
t=4 0:000 0:033 0:033 0:033 0:033 0:400 0:111 0:111 0:111 0:000 0:033 0:033 0:033 0:033
t=5 0:122 0:017 0:017 0:017 0:017 0:111 0:133 0:244 0:133 0:122 0:017 0:017 0:017 0:017
t=6 0:100 0:033 0:033 0:033 0:033 0:293 0:037 0:170 0:037 0:100 0:033 0:033 0:033 0:033
t=7 0:084 0:036 0:036 0:036 0:036 0:210 0:098 0:135 0:098 0:084 0:036 0:036 0:036 0:036
t=8 0:122 0:035 0:035 0:035 0:035 0:168 0:070 0:168 0:070 0:122 0:035 0:035 0:035 0:035
t=9 0:105 0:042 0:042 0:042 0:042 0:217 0:056 0:126 0:056 0:105 0:042 0:042 0:042 0:042
:::
t=28 0:125 0:050 0:050 0:050 0:050 0:151 0:050 0:100 0:050 0:125 0:050 0:050 0:050 0:050
t=29 0:125 0:050 0:050 0:050 0:050 0:150 0:050 0:100 0:050 0:125 0:050 0:050 0:050 0:050
t=30 0:125 0:050 0:050 0:050 0:050 0:150 0:050 0:100 0:050 0:125 0:050 0:050 0:050 0:050
On observe un ph´enom`ene de diffusion, tr`es plausible apr`es r´eflexion :
– On commence au temps t = 0 sur la page 8 avec probabilit´e 1:000.
– Au temps t = 1, on se trouve sur la page 6 avec probabilit´e 1:000, suivant le seul lien 8!6.
– Pour t = 2, on tombe sur une des pages voisines suivant 6!7;8; 9, chacune avec probabilit´e 1
3 .
– Dans les it´erations suivantes la probabilit´e se propage sur tout le graphe.
On constate qu’`a partir de t = 5 la distribution est partout non nulle.
– Apr`es 30 it´erations, on est tr`es proche (`a 10􀀀3 pr`es) de la solution m d´ej`a exhib´ee ci-dessus.
On conclut, au moins empiriquement, que la probabilit´e tend vers notre distribution d’´equilibre m.
`A
noter qu’il ne s’agit pas de l’´equiprobabilit´e : certaines pages sont plus fr´equent´ees que d’autres !
Comme motiv´e plus haut, ceci refl`ete bien le rˆole particulier des pages 6;1;10; 8.
Remarque 8. L’interpr´etation de la limite ut ! m est la suivante : mi est la probabilit´e de se trouver
sur la page i apr`es une tr`es longue marche al´eatoire. Ainsi les pages avec une grande probabilit´e mi
sont les plus fr´equent´ees ou les plus « populaires ». Dans la quˆete de classer les pages web par ordre
d’importance, c’est encore un argument pour utiliser la mesure m comme indicateur.
3.3. Le mod`ele PageRank utilis´e par Google. Il se trouve que notre mod`ele a encore un grave
d´efaut, quant aux propri´et´es math´ematiques ainsi qu’`a son utilit´e pratique :
Exemple 9. Le graphe suivant est une l´eg`ere variante de l’exemple donn´e au x2.1, o`u s’ajoute la page
15 qui n’´emet pas de liens. Pourtant, le r´esultat diff`ere drastiquement : la seule mesure invariante est
m = (0; : : : ;0;1), car notre surfeur al´eatoire tombera tˆot ou tard sur la page 15, o`u il demeure pour
le reste de sa vie. Ce r´esultat ne refl`ete ´evidemment pas l’importance des pages, qui devrait rester
inchang´ee (ou presque).
8 MICHAEL EISERMANN
2 3 4 5
1 7 8
6
9 10
11 12 13 14 15
FIG. 2. Une variante du graphe initial
Pour cette raison Google utilise un mod`ele plus raffin´e, d´ependant d’un param`etre c 2 [0;1] :
– Avec probabilit´e c, le surfeur abandonne la page actuelle et recommence sur une des n pages du
web, choisie de mani`ere ´equiprobable.
– Avec probabilit´e 1 􀀀 c, le surfeur suit un des liens de la page actuelle j, choisi de mani`ere
´equiprobable parmi tous les ` j liens ´emis. (C’est la marche al´eatoire discut´ee ci-dessus.)
Cette astuce ´evite en particulier de se faire pi´eger par une page sans issue. Plus g´en´eralement, elle
garantit d’arriver n’importe o`u dans le graphe, ind´ependamment des questions de connexit´e.
Ce nouveau mod`ele probabiliste se formalise comme l’application affine
T : Rn !Rn; x 7! ce +(1􀀀c)Ax:
Ici A est la matrice stochastique d´efinie par l’´equation (4). Le vecteur stochastique e = ( 1
n ; : : : ; 1n
)
correspond `a l’´equiprobabilit´e sur toutes les pages. La constante c 2 [0;1] est un param`etre du mod`ele.
Remarque 10. La valeur 1c
est le nombre moyen de pages visit´ees (= liens suivis plus 1) avant de
recommencer sur une page al´eatoire. En g´en´eral, on choisira la constante c positive mais proche de
z´ero. Par exemple, c = 0:15 correspond `a suivre environ 6 liens en moyenne. (On pourrait argumenter
que ceci correspond empiriquement au comportement des utilisateurs. . . `a d´ebattre.)
Exercice 11. Si vous vous y connaissez en probabilit´e, prouvez la remarque pr´ec´edente.
4. EXISTENCE ET UNICIT´E D’UNE SOLUTION
4.1. Le th´eor`eme du point fixe. Une fonction f : R!R est contractante
de rapport k < 1 si elle v´erifie j f (x)􀀀 f (y)j kjx􀀀yj pour tout x;y 2 R.
Sous cette hypoth`ese, f admet un et un seul point fixe m 2 R, f (m) = m,
et pour tout u0 2 R la suite it´erative um+1 = f (um) converge vers m.
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
contractante
Voici une fonction
C’est exactement l’argument qu’il nous faut pour notre application. On
a d´ej`a vu, d’ailleurs, que la convergence se produisait dans notre exemple
ci-dessus. Est-ce une co¨ıncidence ? Non, c’est encore une manifestation du
fameux th´eor`eme du point fixe. Comme nous travaillons sur les vecteurs
x 2 Rn, nous sommes amen´es `a le g´en´eraliser convenablement :
D´efinition 12. Pour un vecteur x 2 Rn on d´efinit sa norme par jxj :=åi jxij.
(C’est une honnˆete norme, qui a toutes les bonnes propri´et´es usuelles.) Une
fonction f : Rn !Rn est dite contractante de rapport k < 1 (par rapport `a
la norme j j) si elle v´erifie j f (x)􀀀 f (y)j kjx􀀀yj pour tout x;y 2 Rn.
COMMENT FONCTIONNE GOOGLE? 9
Th´eor`eme 13 (le th´eor`eme du point fixe). Si f : Rn ! Rn est une fonction contractante de rapport
k < 1, alors :
(1) Il existe un et un seul point m 2 Rn v´erifiant f (m) = m.
(2) Pour toute valeur initiale u0 2 Rn la suite it´erative um+1 = f (um) converge vers m.
(3) On a jum􀀀mj kmju0􀀀mj, la convergence vers m est donc au moins aussi rapide que celle
de la suite g´eom´etrique km vers 0. Pour le calcul concret on a l’estimation de l’´ecart
jum􀀀mj
k
1􀀀k
jum􀀀um􀀀1j:
Remarque 14. Dans la pratique, on ignore souvent la limite m mais on peut facilement calculer la
suite it´erative um. Pour contrˆoler la qualit´e de l’approximation um, on majore l’´ecart jum􀀀mj entre um
et la limite inconnue par la quantit´e k
1􀀀k jum􀀀um􀀀1j, tr`es facile `a calculer.
D´emonstration. Comme il s’agit d’une tr`es belle preuve, je ne peux m’empˆecher de la refaire ici.
Unicit´e.—Si x;y 2 Rn sont deux points fixes d’une fonction f qui est contractante de rapport k <1,
alors jx􀀀yj = j f (x)􀀀 f (y)j kjx􀀀yj. Ceci n’est possible que pour jx􀀀yj = 0, donc x = y.
Existence. — Une r´ecurrence facile montre que jum+1􀀀umj kmju1􀀀u0j pour tout m 2 N, puis
jum+p􀀀umj jum+p􀀀um+p􀀀1j+ +jum+1􀀀umj
(kp􀀀1+ +k0)jum+1􀀀umj = 1􀀀kp
1􀀀k jum+1􀀀umj
1
1􀀀k jum+1􀀀umj km
1􀀀k ju1􀀀u0j
pour tout m; p 2 N. La suite (um) est donc de Cauchy et converge puisque (Rn; j j) est complet.
Notons m := limum sa limite et v´erifions qu’il s’agit d’un point fixe. Puisque f est contractante, elle
est continue. L’´equation de r´ecurrence um+1 = f (um) donne donc
m = limum+1 = lim f (um) = f (limum) = f (m):
Vitesse de convergence.—Pour tout u0 la suite it´erative um+1 = f (um) v´erifie jum􀀀mj kmju0􀀀mj,
donc um ! m. On a d´ej`a ´etablit la majoration jum+p􀀀umj k
1􀀀k jum􀀀um􀀀1j, et le passage `a la limite
p!¥ donne l’in´egalit´e cherch´ee.
Remarque 15. La propri´et´e de f d’ˆetre contractante ne repose que sur la m´etrique de Rn. Le th´eor`eme
du point fixe et sa preuve se g´en´eralisent mot par mot `a un espace m´etrique quelconque `a condition
qu’il soit complet, c’est-`a-dire que toute suite de Cauchy converge.
Les espaces m´etriques complets sont tr`es importants parce qu’ils permettent de construire certains
objets comme limites de suites de Cauchy, l’existence ´etant assur´ee par l’hypoth`ese de compl´etude.
Notre th´eor`eme en est un exemple fondamental aussi bien pour la th´eorie que pour le calcul num´erique.
4.2. Application au mod`ele PageRank.
Proposition 16. Soit A 2 Rn n une matrice stochastique et T : Rn !Rn l’application d´efinie par
T(x) = ce +(1􀀀c)Ax
avec une constante c 2 ]0;1]. Alors l’application T est contractante de rapport k = 1􀀀c < 1. Par
cons´equent, elle admet une unique mesure invariante m = T(m) et, pour tout vecteur initial u0, la
suite it´erative um+1 = T(um) converge vers le point fixe m, avec la vitesse ´enonc´ee ci-dessus.
10 MICHAEL EISERMANN
C’est cette mesure invariante m qui nous int´eressera dans la suite et que l’on interpr´etera comme
mesure d’importance. On la calculera d’ailleurs par la m´ethode it´erative de la proposition pr´ec´edente.
D´emonstration. Il suffit de prouver que T est contractante, de rapport k = 1􀀀c < 1, pour faire appel
au th´eor`eme du point fixe. Regardons deux vecteurs x;y 2 Rn et essayons de majorer z := Tx􀀀Ty
en fonction de jx􀀀yj. On a z = kA(x􀀀y) donc zi = kåj ai j(xj 􀀀yj) pour tout i = 1; : : : ;n. Ceci nous
permet de calculer la norme :
jTx􀀀Tyj = jzj =å
i
jzij =å
i

k
åj
ai j(xj 􀀀yj)

kå
i
åj
jai j(xj 􀀀yj)j = kå
j
åi
ai jjxj 􀀀yjj
= kå
j

åi
ai j

jxj 􀀀yjj = kjx􀀀yj:
Ceci prouve que T : Rn ! Rn est contractante de rapport k comme ´enonc´e. L’application T admet
donc un unique point fixe m 2Rn. Remarquons finalement que le point fixe est un vecteur stochastique,
c’est-`a-dire qu’il satisfait mi 0 et åi mi = 1 : si l’on d´emarre avec un vecteur stochastique u0, alors
tous les it´er´es um restent stochastiques, donc leur limite m l’est aussi. (Exercice.)
Remarque 17. La proposition inclut le cas trivial c = 1 : dans ce cas T(x) = e est constante, donc
x = e est l’unique point fixe. Dans l’autre extrˆeme on pourrait consid´erer c = 0, mais T = A n’est pas
forc´ement contractante. Par exemple pour un graphe `a n sommets sans arˆetes entre eux, nous obtenons
la matrice identit´e, A = I, qui admet tout vecteur x 2 Rn comme point fixe. Un bon choix de c se situe
donc quelque part entre 0 et 1 (voir la remarque 10).
Remarque 18. Le fait que la solution soit unique est fondamental : une fois que le mod`ele est ´etabli,
le th´eor`eme nous garantit une unique mesure m, sans ´equivoque. Mieux encore, la suite it´erative
converge toujours vers m, ind´ependamment du point de d´epart. En l’absence de toute autre information
on pourra donc d´emarrer avec u0 = e = ( 1
n ; : : : ; 1
n ) pour calculer la limite um !m.
Remarquons `a ce propos que Google est oblig´e de mettre `a jour ses donn´ees r´eguli`erement, car le
web change sans cesse. Disons que Google met `a jour le vecteur m chaque semaine. Pour ce calcul,
il serait maladroit de recommencer par u0 = e ! Il est sans doute plus avantageux de recycler l’information
d´ej`a obtenue : on choisira u0 = mancien, la mesure de la semaine d’avant. Ainsi peu d’it´erations
suffiront pour r´eajuster m, en supposant que le graphe n’est que l´eg`erement modifi´e.
La morale de cette histoire : l’unicit´e garantie par le th´eor`eme nous laisse la libert´e de choisir parmi
plusieurs m´ethodes de calcul—elles aboutissent toutes au mˆeme r´esultat ! On peut en profiter si l’on
dispose d’informations suppl´ementaires, par exemple en choisissant judicieusement le point de d´epart
de l’it´eration.
Remarque 19. La proposition pr´ec´edente se g´en´eralise au th´eor`eme de Perron-Frobenius : si une
matrice r´eelle A a tous ses coefficients positifs, ai j > 0 pour i; j = 1; : : : ;n, alors le rayon spectral de A
est donn´e par une valeur propre l 2 R+ et l’espace propre associ´e El est de dimension 1. De plus, la
matrice A admet un vecteur propre v 2 El dont tous les coefficients sont positifs.
L’algorithme it´eratif correspondant est souvent appel´e la «m´ethode de la puissance ». Il se g´en´eralise
`a une matrice A quelconque et permet d’approcher num´eriquement un vecteur propre v associ´e `a la
valeur propre l de module jlj maximal, pourvu que cette valeur propre soit unique et simple.
COMMENT FONCTIONNE GOOGLE? 11
5. IMPL´E MENTATION EFFICACE
Passons `a l’impl´ementation de l’algorithme discut´e ci-dessus. Le programme
qui en r´esulte est plutˆot court (moins de 100 lignes). N´eanmoins
il est important de r´efl´echir sur la meilleure fac¸on de s’y prendre.
5.1. Matrices creuses. Rappelons que la matrice A repr´esentant le web est tr`es grande : en 2004
Google affirmait que « le classement est effectu´e grˆace `a la r´esolution d’une ´equation de 500 millions
de variables et de plus de 3 milliards de termes. » Comment est-ce possible ?
La mani`ere usuelle de stocker une matrice de taille n n est un grand tableau de n2 coefficients
index´es par (i; j) 2 f1; : : : ;ng2. Il est envisageable de stocker ainsi une matrice 1000 1000, c’est-
`a-dire un million de coefficients mais ceci est hors de question pour une matrice n n avec n 106,
voire n 108. L’approche na¨ıve est donc prohibitive pour le mod`ele PageRank. Soulignons aussi que
la m´ethode de Gauss, bien adapt´ee aux matrices de petite taille, s’av`ere inutilisable pour les grandes
matrices. Cet algorithme effectue environ n3 op´erations, ce qui est trop coˆuteux si n est grand.
Dans notre cas la plupart des coefficients valent z´ero car une page n’´emet que quelques douzaines
de liens typiquement. Dans ce cas, il suffit de stocker les coefficients non nuls, dont le nombre est
d’ordre n et non n2. Une telle matrice est appel´ee creuse (ou sparse en anglais). Pour des applications
r´ealistes, il est donc n´ecessaire d’impl´ementer des structures et des m´ethodes adapt´ees aux matrices
creuses. La m´ethode du point fixe est faite sur mesure pour ce genre d’application.
5.2. Matrices provenant de graphes. Pour simplifier, nous allons sp´ecialiser notre impl´ementation
aux matrices creuses provenant de graphes. Rappelons qu’un graphe peut commod´ement ˆetre cod´e
sous forme de listes. Dans notre exemple initial cette description ´etait :
1!2;3;4;5;6 ; 2!1;3 ; 3!1;4 ; 4!1;5 ; 5!1;3 ; 6!7;8;9 ; 7!8;1 ; 8!6 ;
9!8;10 ; 10!6;11;12;13;14 ; 11!10;12 ; 12!10;13 ; 13!10;14 ; 14!10; 11.
Les pages sont num´erot´ees par 1; : : : ;n et, pour chaque page j, on ´enum`ere tous les liens j!i1; i2; : : : ; i`
´emanant de j vers les pages voisines. Notons Lj = fi1; i2; : : : ; i`g leur ensemble et ` j = jLjj le nombre
de liens ´emis par la page j. `A noter que n peut ˆetre tr`es grand alors que ` j est en g´en´eral tr`es petit.
Comme avant nous supposons toujours que ` j 1.
Algorithme 1 Calcul efficace de T(x) = ce +(1􀀀c)Ax
Entr´ee: un vecteur x 2 Rn.
Sortie: le vecteur y = Tx.
Initialiser yi   cn
pour tout i = 1; : : : ;n // Ceci correspond au terme de base ce
pour j de 1 `a n faire // On parcourt toutes les pages ´emettrices
pour i 2 Lj faire yi  yi+ 1􀀀c
` j
xj // La page j pointe vers ` j pages voisines
fin pour
retourner y
Remarque 20. La complexit´e de cet algorithme est optimale dans le sens que l’on traite chaque lien
j ! i exactement une fois : le nombre total d’op´erations est donc proportionnel `a åj ` j. Autrement
dit, si les pages e´mettent en moyenne `¯= 1
n åj ` j liens, nous avons a effectuer n`¯ ope´rations au total,
au lieu de n2 pour une matrice dense.
12 MICHAEL EISERMANN
`A
noter aussi que notre algorithme n’utilise que les deux vecteurs x et y : la matrice A ne figure pas
explicitement dans l’impl´ementation. Effectivement, la construction explicite d’une matrice de taille
n n allouerait trop de m´emoire et sera catastrophique quand n est grand !
Remarque 21. L’algorithme 1 est adapt´e `a la structure des donn´ees choisie ci-dessus. Au lieu de
stocker les liens ´emis Lj = fi j j ! ig on pourrait stocker les liens rec¸us L
i = f j j j ! ig. Ceci
correspond `a passer de la matrice A `a sa transpos´ee A . Dans ce cas on inverse les deux boucles :
pour i allant de 1 `a n on parcourt j 2 L
i et calcule yi   yi + 1􀀀c
` j
xj. C’est essentiellement la mˆeme
d´emarche, mais il faut faire un choix pour accorder structures des donn´ees et algorithmes utilis´es.
Algorithme 2 Approximation de la mesure invariante m = T m
Entr´ee: la pr´ecision souhait´ee d > 0.
Sortie: un vecteur x tel que jx􀀀mj d.
Initialiser xi   1
n pour tout i = 1; : : : ;n // Un vecteur stochastique initial
r´ep´eter y x, x Tx jusqu’`a jx􀀀yj cd
1􀀀c // Suivant le th´eor`eme du point fixe
retourner x
Exercice 22. Si vous vous int´eressez `a la programmation, vous pouvez essayer d’impl´ementer la
m´ethode ci-dessus. Parall`element, il sera int´eressant de discuter ses aspects th´eoriques :
(1) V´erifier d’abord la correction des deux algorithmes. Pour le deuxi`eme, montrer que la condition
d’arrˆet jx 􀀀 yj cd
1􀀀c garantit que le vecteur x est suffisamment proche de la limite
cherch´ee, c’est-`a-dire jx􀀀mj d comme promis par la sp´ecification de l’algorithme.
(2) Remarquons aussi que l’efficacit´e de cet algorithme d´epend sensiblement du nombre d’it´erations
n´ecessaires. C’est ici que la vitesse de convergence, comme ´etablie dans le th´eor`eme du point
fixe, nous garantie une ex´ecution rapide.
(3) Finalement, le fait que l’application T soit contractante nous assure aussi que notre algorithme
est num´eriquement stable. Rappelons que par souci d’efficacit´e, on effectue tous les
calculs avec des nombres `a virgule flottante. Des erreurs d’arrondi sont donc in´evitables. Fort
heureusement, de telles erreurs ne sont pas amplifi´ees dans les calculs it´eratifs.
6. QUELQUES POINTS DE R´E FLEXION
On pourrait se contenter d’une conclusion pragmatique : « Bon, enfin
c¸a marche. Tout le monde s’en sert. Il n’y a plus rien `a ajouter. »
Mais, d’autre part, l’approche est suffisamment simple et l’application
importante pour se poser quelques questions.
6.1. Le mod`ele est-il plausible ? La structure caract´eristique d’un document hypertexte sont les liens
vers d’autres documents. L’auteur d’une page web ajoute ainsi des liens vers les pages qu’il consid`ere
utiles ou « importantes ». Autrement dit, on peut interpr´eter un lien comme un vote ou une recommandation.
Or, il ne suffit pas de compter les liens, car ils n’ont pas tous le mˆeme poids. Nous avons donc
raffin´e notre heuristique : une page est importante si beaucoup de pages importantes pointent vers
elle. Cette d´efinition peut sembler circulaire, mais le d´eveloppement math´ematique ci-dessus montre
comment s’en sortir (par le th´eor`eme du point fixe).
COMMENT FONCTIONNE GOOGLE? 13
Ainsi des millions d’auteurs de pages web lisent et jugent mutuellement leurs pages, puis leurs
jugements s’expriment par les liens qu’ils mettent sur leurs pages. Le mod`ele de la marche al´eatoire
en profite en transformant l’´evaluation mutuelle en une mesure globale de popularit´e. (Soulignons `a
nouveau que le surfeur al´eatoire ignore le contenu et se fie uniquement `a la structure des liens.)
6.2. Hypoth`eses implicites. D’apr`es l’autoportrait de Google, « la technologie de Google utilise
l’intelligence collective du web pour d´eterminer l’importance d’une page. » Nous venons de voir
comment cette phrase peut s’interpr´eter math´ematiquement. Une triple hypoth`ese y est implicite :
(1) Les liens refl`etent fid`element les appr´eciations des auteurs des pages web.
(2) Ces appr´eciations correspondent bien `a celles des lecteurs des pages web.
(3) Le mod`ele du surfeur al´eatoire les traduit fid`element en une mesure de popularit´e.
En soutien de ces hypoth`eses, on mentionne parfois la « nature d´emocratique » du web pour dire
que les lecteurs et les auteurs ne font qu’un et que l’´echange des informations est libre. C’est une
id´ealisation de moins en moins plausible, surtout quant `a l’aspect commercial du web. En 1993 seul
1,5% des sites web ´etaient dans le domaine .com, en 2003 ils repr´esentaient plus de 50% du web et la
fr´equentation des pages devrait donner des proportions similaires.
6.3. Descriptif ou normatif ? Le statut de Google lui-mˆeme a compl`etement chang´e :
Google se veut descriptif: Au d´ebut de son existence, Google se voulait un outil purement descriptif
: si une page est importante, alors elle figure en tˆete du classement.
En r´ealit´e il est devenu normatif: Aujourd’hui, son ´ecrasant succ`es fait de Google une r´ef´erence
normative : si une page figure en tˆete du classement, alors elle est importante.
`A
titre d’illustration, citons un exemple devenu classique. Le
math´ematicien franc¸ais Gaston Julia, n´e le 3 f´evrier 1893, devint
c´el`ebre pour ses contributions `a la th´eorie de fractales, largement
popularis´ee par son ´el`eve Benoˆıt Mandelbrot depuis les ann´ees
1970. Pour son anniversaire le 3 f´evrier 2004, la page d’accueil
de Google montrait une variation fantaisiste du logo usuel. Un clique dessus lanc¸ait la recherche
d’images associ´ees aux mots-cl´es « Julia » et « fractale ». Deux des pages en tˆete du classement
´etaient h´eberg´ees `a un institut de l’universit´e de Swinburne, `a Melbourne en Australie. Comme tous
les jours, des millions d’internautes ont visit´e la page de Google et, ce jour-l`a, une certaine fraction a
suivi le lien du logo, pour tomber sur la page `a Swinburne. Ce trafic soudain a suffit pour submerger
le serveur australien, qui rendit l’ˆame aussitˆot. Les images fractales durent ˆetre d´eplac´ees et une page
explicative fut mise `a la place [4]. Elle conclut par une question m´emorable (d’apr`es Job 1 21) :
Google giveth, and Google taketh away, blessed be Google ?
[Google avait donn´e, Google a repris, que le nom de Google soit b´eni ?]
Bien que le trafic internet ne soit pas toujours une b´en´ediction, la plupart des webmestres seraient
ravis d’accueillir des foules d’internautes sur leur site car la popularit´e peut potentiellement
se transformer en b´en´efice. Cet aspect rend l’´evaluation des pages web encore plus difficile : comme
l’approche et l’importance de Google sont mondialement connues, les liens s’utilisent sans doute
diff´eremment `a nos jours. Apr`es avoir compris l’algorithme de Google, les concepteurs de sites web
pourraient appliquer cette connaissance afin d’am´eliorer leur classement. . .
14 MICHAEL EISERMANN
6.4. Peut-on manipuler Google ? Pour des sites web commerciaux, l’optimisation de leur classement
est devenue un enjeu important. ´ Evidemment, le fournisseur d’un service commercial souhaite
que son site soit le plus visit´e possible et ceci passe par Google : des millions de clients potentiels
utilisent Google et suivent typiquement les liens en tˆete du classement. Comment am´eliorer son classement,
son importance calcul´ee par Google ? Voici ce qu’en dit l’entreprise Google :
Les m´ethodes complexes et automatiques utilis´ees par les recherches Google rendent
quasi impossible toute manipulation humaine des r´esultats. (. . .) Google ne pratique
pas la vente des positions dans ces r´esultats ; autrement dit, il n’est pas possible
d’acheter une valeur PageRank sup´erieure `a la r´ealit´e du Web.
Pourtant, afin d’am´eliorer son classement par Google, il suffit d’attirer des liens, de pr´ef´erence ceux
´emis par des pages importantes et il vaut mieux en ´emettre tr`es peu, de mani`ere bien choisie.
Exercice 23. La strat´egie la plus ´evidente (et la plus honnˆete) pour attirer des liens est d’offrir des
informations de qualit´e. Par exemple, si apr`es lecture vous trouvez que cet article le m´erite, faitesy
pointer un lien <a href=”http://www-fourier.ujf-grenoble.fr/˜eiserm/enseignement.html#google”>
Comment fonctionne Google ? </a> depuis votre page web. Vous ferez ainsi monter son classement
PageRank. `A v´erifier au bout de quelques semaines, apr`es mise `a jour de la base de donn´ees de Google.
Un grand merci `a tous ceux qui ont d´ej`a particip´e `a cette exp´erience pratique. Depuis fin 2007 le
pr´esent document arrive en tˆete du classement pour la requˆete « comment fonctionne Google ».
Ces strat´egies et astuces sont elles-mˆemes devenues un domaine tr`es actif, dit « search engine
optimization » (SEO). Ceci confirme en particulier que l’omnipr´esence de Google change l’utilisation
des liens par les auteurs. . . ce qui remet en question l’hypoth`ese `a la base mˆeme du mod`ele.
Exercice 24. Qu’en pensez-vous : que peut-on faire pour am´eliorer son classement ? Avec votre
impl´ementation exp´erimentale de l’algorithme PageRank, vous pouvez tester vos conjectures sur des
exemples concrets. Vous pouvez aussi regarder ce qu’en disent des experts : cherchez par exemple
« google PageRank algorithm » ou « search engine optimization » et vous verrez.
6.5. Comment ´evolue Google ? L’algorithme de base que nous venons de d´ecrire fut mis en oeuvre
en 1998 et reste, semble-t-il, le fondement de l’efficacit´e l´egendaire de Google. (D’ailleurs, la m´ethode
a ´et´e brevet´ee par l’universit´e de Stanford en 2001, ainsi qu’une version raffin´ee en 2004, et le nom
« PageRank » est une marque d´epos´ee de Google Inc. [3].)
La m´ethode actuellement utilis´ee a sans doute ´et´e adapt´ee et peaufin´ee au fil des ann´ees, afin de
rendre le classement encore plus utile, c’est-`a-dire plus proche des attentes des utilisateurs, et plus
robuste contre des tentatives de manipulations. Contrairement `a l’algorithme de base, toutes les modifications
ult´erieures restent un secret de l’entreprise Google.
Toujours est-il que les webmestres les plus inventifs arrivent souvent `a influencer le classement en
leur faveur pour se positionner sur les premi`eres pages des r´esultats. En r´eaction, Google est oblig´e
d’am´eliorer son algorithme pour rattraper les tricheurs, au moins les plus flagrants. Bref, c’est l’habituelle
course du gendarme et du voleur, mais typiquement Google s’en sort bien.
Effectivement, Google a tout int´erˆet `a maintenir la bonne qualit´e de ses r´esultats afin de d´efendre
sa popularit´e qui, rappelons-le, est la source de ses revenus. Si l’on veut y voir un aspect positif, on
pourrait dire que cette ´eternelle comp´etition fait ´evoluer les moteurs de recherche.
COMMENT FONCTIONNE GOOGLE? 15
6.6. Where next ? Il n’est pas difficile d’imaginer des variantes et possibles am´eliorations, mais il
est souvent d´elicat de les mettre en oeuvre concr`etement. `A titre d’exemple, reprenons le mod`ele
probabiliste de Google, formalis´e par l’application T(x) = ce +(1􀀀c)Ax. La question de base reste
l’´evaluation des liens : par d´efaut la construction de la matrice A traite tous les liens ´emanant d’une
page j comme ´equivalents, ind´ependamment de la requˆete, et cela donne d´ej`a de bons r´esultats.
Le mod`ele pourrait ˆetre am´elior´e si l’on comprenait mieux quels liens sont pertinents `a une requˆete
donn´ee, afin d’adapter la matrice A. Autant que l’on puisse dire, Google impl´emente partiellement
cette id´ee. ´ Evidemment le mod`ele du surfeur al´eatoire n’est qu’une premi`ere approximation. La prochaine
´etape serait donc de mod´eliser un surfeur « intelligent ».
Un autre sujet est la « personnalisation » : on pourrait par exemple remplacer e, l’´equiprobabilit´e
sur toutes les pages, par une autre distribution d, un « profil » d´ependant des pr´ef´erences de l’utilisateur.
Ainsi la marche al´eatoire serait l’it´eration de l’application T(x) = cd +(1􀀀c)Ax: Ici le profil
d = ( 1
n ; : : : ;1n
) veut dire « aucune pr´ef´erence ». Une distribution d concentr´ee sur des sites `a th`emes
scientifiques, par exemple, en serait un autre profil, plus sp´ecifique. La mesure invariante d´epend
´evidemment du profil sp´ecifi´e, et mettra plus de poids sur des pages proches du profil.
La difficult´e r´eside dans la construction de (quelques) profils raisonnables, c’est-`a-dire appr´eci´es
par les utilisateurs. De nouveau, un affinage it´eratif semble logique, bas´e sur des r´eactions des utilisateurs
cette fois-ci. L’aspect prometteur de cette approche est qu’elle prend en compte simultan´ement
les appr´eciations des auteurs et des lecteurs des pages web.
Vous voyez, il ne manque pas d’id´ees `a explorer ! Vue l’importance du sujet, ce domaine est devenu
extrˆemement actif (et lucratif) depuis une dizaine d’ann´ees et r´eunit parfois recherches fondamentales
et appliqu´ees en math´ematiques et informatique. Ne mentionnons ici que les travaux de Jon Kleinberg
[5] qui a d´evelopp´e des m´ethodes th´eoriques et algorithmiques plus raffin´ees, ce qui lui valut le prix
Nevanlinna en 2006. Mais cela serait une autre histoire. . .
Exercice 25. Trouvez une meilleure m´ethode pour extraire de l’information du web et devenez riche
et/ou c´el`ebre. Sachez `a ce propos que l’Institut Fourier accepte les dons.
Remerciements. Je tiens `a remercier mon coll`egue Tanguy Rivoal pour ses conseils linguistiques et
surtout son encouragement `a publier ces notes de cours sous forme d’article de vulgarisation. Une
version abr´eg´ee de cet article est paru dans Quadrature, no. 68, avril 2008.
R´E F´E RENCES
[1] S. Brin, L. Page : The Anatomy of a Large-Scale Hypertextual Web Search Engine, Stanford University, 1998.
(Pour trouver ce texte en ligne cherchez-le avec Google.)
[2] D.Vise, M. Malseed : Google story, Dunod, Paris, 2006.
[3] Wikipedia : PageRank, en.wikipedia.org/wiki/PageRank et fr.wikipedia.org/wiki/PageRank.
(La page francophone attend toujours une r´edaction digne du sujet.)
[4] The power of Google, local.wasp.uwa.edu.au/~pbourke/fractals/quatjulia/google.html
[5] J.M. Kleinberg : Authoritative sources in a hyperlinked environment,
www.cs.cornell.edu/home/kleinber/auth.pdf.
INSTITUT FOURIER, UNIVERSIT´E GRENOBLE I, FRANCE
URL: www-fourier.ujf-grenoble.fr/~eiserm
E-mail address: Michael.Eisermann@ujf-grenoble.fr