COMMENT FONCTIONNE GOOGLE. QUE FAIT UN MOTEUR DE RECHERCHE? Contrairement à une base de données...

COMMENT FONCTIONNE GOOGLE

QUE FAIT UN MOTEUR DE RECHERCHE?

Contrairement à une base de données

structurée dont on peut facilement extraire

des informations, le WEB est une

immense collection de textes de toutes

natures qui évolue en permanence.

Le moteur de recherche copie préalablement les pages sur des milliers d’ordinateurs (60 000 pour Google!) et les trie par ordre alphabétique (selon les mots clé). Lors d’une requête relative à un mot clé, le moteur répond par la liste des pages

contenant ce mot clé. Mais il y en a des dizaines de milliers en général.

LE CLASSEMENT PAR ORDRE DE PERTINENCE

C’est ici qu’intervient l’innovation de Larry PAGE (fondateur avec Serguei BRIN de Google) connue sous le nom de PAGERANK.

L’idée est de répondre à la requête en

citant les pages par ordre de pertinence.

Le WEB est un graphe

Le Web a une structure due au fait que les pages se citent mutuellement. c’est le principe de l’hypertexte : les pages se citent mutuellement par les fameux liens. On va donc partir de l’idée que plus une page

est citée, plus elle est pertinente. On verra à la fin que ce principe a des limites.

Voilà en miniature comment se présente le

graphe:

Si on note les pages du Web 1,.., NP P on écrira j i si la page jP cite la page iP .

On peut présenter le graphe sous la forme plus lisible :

Mise en place d’un degré de pertinence

1) Comptage « naïf »

Il est clair qu’une page importante reçoit de nombreux liens.

Naïvement, on peut croire que si une page reçoit beaucoup de liens, elle est importante et on définit son importance par:

/

1ij j i

Dans notre exemple, on trouve : Cela n’est pas exactement ce qu’on attend, et de plus, c’est très facile à manipuler. 2)Comptage pondéré Nous allons pondérer le « vote » de jP par le

nombre total de liens émis par la page soit :

1

ijj i n

1 9

5 7

4

3

Dans notre exemple, on trouve 3) Comptage récursif On pondère le vote par l’importance soit :

1

i jjj i n

Dans notre exemple, cela donne : (2,1,1,1,3,1,1,2,1,2,1,1,1). La page 5P est bien la plus importante.

1 9

5 7

2

3 4,

2 3

Le modèle du surfeur aléatoire On suppose que le surfeur est sur une page donnée à l’instant 0 et qu’il évolue de page en page en cliquant sur les liens au hasard. En supposant qu’il part de 7P , cela donne les probabilités suivantes :

En partant de 1P :

On obtient une chaine de MARKOV dont la matrice de transition est :

Formellement, si l’on note nX la position du surfeur au bout de n clics, on aura :

1 11

( ) ( ) ( )n

N

n n nX ii

P X k P X k P X i

où 11

( )n nX i

i

P X kn si la page iP pointe sur kP

et 0 sinon.

Avec les notations habituelles, 0

nnU A U

Examinons le graphe suivant :

On peut avoir l’intuition que le surfeur va finir par se retrouver coincé sur la page 13P .

C’est pourquoi Google utilise une astuce : À chaque page, avec une probabilité p le surfeur peut renoncer à suivre les liens et abandonner sa page actuelle pour une autre page choisie au hasard parmi les N pages du Web. Le temps d’attente du premier « saut » suit une loi géométrique de paramètre p. Avec 0,15p , le surfeur suit 6 liens en moyenne.

Le modèle final

1 11

( ) (1 ) ( ) ( )n

N

n n nX ii

pP X k p P X k P X i

N

Et matriciellement : 1 (1 )n nU pV p AU

Où

1/

1/

1/

N

N

V

N

Comme pour les suites arithmético-géométriques, on cherche le point fixe tel que : (1 )pV p A Soit : ((1 ) )p A I pV . Les valeurs propres de A étant dans 1,1 , cette équation a une solution unique car les valeurs propres de (1 )p A I sont non nulles.

Finalement, la suite nU vérifie : 1 (1 ) ( )n nU p A U D’où : 0(1 ) ( )n n

nU p A U Il ne reste plus qu’à montrer que nU converge vers le point fixe qui est la solution du problème de Google !

Avec p=0,15, on obtient assez rapidement la limite à 0,01 près

En guise de conclusion

Au départ Google se voulait un outil descriptif.

Si une page est importante, elle doit apparaître en tête du classement.

Mais le succès de Google l’a transformé en outil normatif: si une page apparaît en tête, alors elle est considérée par la communauté comme importante!