Choux romanesco, Vache qui rit et intégrales curvilignes

Comment qu'ça marche, Google ?!

une femme qui fait le point sur elle meme

L'histoire débute en 1995, avec la rencontre de deux étudiants fraîchement diplômés,  Larry Page et Sergey Brin. De leur rencontre naîtra le projet d'un moteur de recherche qui prendrait en compte la manière dont les pages internet sont liéss les unes aux autres. Le projet s'appelle BlackRub, et monopolisera pendant un an les serveurs de Stanford. Le nom "google.com" est enregistré en 1997, et la société Google est fondée en 1998 (sur les conseils avisés du fondateur de Yahoo!...)... Le nom "Google" fait référence au nombre 10^100, le "gogol", correspondant à un '1' suivi de cent '0' (Ce qui correspond en gros au nombre de pages qui seront, à terme, référencées par le moteur de recherche...) La société a aujourd'hui un chiffre d'affaires de trouze billons de dollars, et pourquoi ?... Parce qu'ils ont simplement utilisé un gros ordinateur pour résoudre un pauvre problème de valeur propre avec la méthode de la puissance...
Aujourd'hui, je vous dirai tout sur le secret le moins bien gardé de Google : le PageRank !

Un bon moteur de recherche se doit de fonctionner en deux temps : d'abord, il doit sélectionner les pages qui correspondent le mieux au(x) mot(s)-clé(s) donné(s), puis doit ensuite hiérarchiser les pages selon leur intérêt. Google a créé le buzz ramdam en donnant sa définition objective de ce qu'est l'intérêt d'une page web : c'est un nombre entre 0 et 1, intitulé le PageRank de la page (un habile jeu de mot entre "Larry Page" et "le rang d'une page").

faite moi gagner plusieurs million de dollars

Le PageRank
Basons nous sur un Internet rudimentaire qui ne serait composé que d'une dizaine de pages [N=10]. Une flèche entre une page A et une page B indique que la page A possède un lien qui pointe sur la page B :

Graphe
Graphe d'un mini-web [avec sa matrice associée (si la page i pointe vers la page j, la ligne j de la colonne i sera 1, 0 sinon)]
[On peut noter à ce point-là que la matrice possède beaucoup de 0, ce qui est loin d'être un détail]

Comment trier de manière objective toutes ces pages selon leur intérêt, sans devoir se taper la lecture de toutes les pages ? (Dans le cas d'une dizaine de pages, c'est faisable, mais pour un Web en possédant 11 fois plus (exponentiellement parlant), c'est un peu plus coton. Quand on regarde un peu le graphe, on peut dire que la page 5 est importante (elle est beaucoup citée), alors que la page 10 est moins importante (personne ne la cite...)

La première idée, toute bête serait que le score d'une page corresponde au nombre de liens qui pointe sur elle. Ce principe fonctionnerait bien sur Schtroumpternet, mais dans le monde réel, un individu Λ qui voudrait se donner beaucoup d'importance pourrait se créer un petit panel de pages toutes reliées les unes aux autres pour gonfler artificiellement son importance.

Deuxième idée : si une page émet beaucoup de liens, c'est qu'elle ne sait pas faire de choix (c'est le cas de la page 1) ; ses liens seront donc moins importants qu'une page qui en émet peu, comme la page 5 ou la page 3. On peut alors pondérer le poids des liens par le nombre de liens sortant d'une page. Le score d'une page serait alors la somme des poids des liens pointant sur cette page [ce qui se résume par la matrice Q qui suit]

Graphe2
Le même graphe, mais avec les liens pondérés

Cette deuxième idée est plus juste, mais possède toujours le même problème de l'individu Λ malveillant.

Pour être juste, il faudrait que les pages de Λ possèdent un poids très faible (puisque ces pages ne sont jamais citées par de vraies pages). L'idée est que le poids d'un lien dépende également du score de la page qui l'émet (tout en tenant compte du nombre de liens quelle émet). On traduit ceci en une définition récursive du poids ci de la page. Par exemple, le score de la page 5 serait alors c1/4+c2/2+c8/3. Les scores c1, c2 et c8 sont définis de la même façon, à partir des autres ci. Autrement dit, on se ramène à devoir résoudre le système linéaire suivant :

syst_me
Le système à résoudre !

On pourrait d'ores et déjà résoudre ce système à la main, et le problème serait terminé. Mais dans le cas du vrai web, on aurait un système avec plusieurs milliards d'inconnus et tout autant d'équations, ce qui est compliqué à faire...

[Autrement dit, il faut résoudre le problème c=Qc. Les gens cultivés diront qu'il faut retrouver un vecteur propre de Q correspondant à la valeur propre 1, ceux qui sont malins se diront, à raison, qu'il y a des solutions évidentes, du genre (0,0,0,0,0,1,1,0,0,0) ou (0,0,0,1,1,0,0,0,0,0,0). Il pourrait aussi arriver que le système n'ait même pas de solutions.
On pourrait résoudre tous ces problèmes de vecteurs propres (pour en assurer l'existence, la positivité et l'unicité à coefficient multiplicateur près) en modifiant légèrement la matrice et conclure par du Perron-Frobenius, mais on peut passer par une autre voie...]

tchin tchin en alsacien

Le surfeur aléatoire
Le score de pertinence d'une page peut se voir d'une autre manière : c'est la probabilité qu'un surfeur aléatoire s'arrête sur la page après un temps de surf assez long. Le surfeur aléatoire est un être abstrait qui passerait son temps sur Internet à cliquer au hasard sur les liens d'Internet. Ainsi, plus une page est importante, plus la probabilité du surfeur aléatoire de s'y arrêter est grande (et vice-versa). Le PageRank d'une page sera donc la probabilité que le surfeur aléatoire s'y arrête, après un grand nombre de clics. Cette vision des choses permet de faire quelques modifications sur le graphe qui rendront la solution unique.

Plaçons-le sur la page 1.
Après un clic, il se retrouve sur les pages 2, 3, 5 ou 6 avec une probabilité p=1/4
Un clic plus tard, il se retrouve sur la page 1 (p=1/8), 5 (p=1/8), 4 (p=1/4), 3 (p=1/8), 8 (p=1/8) ou 7 (p=1/4)
Et ainsi de suite.
[Ces probabilités se calculent facilement en posant u0=(1,0,0,0,0,0,0,0,0,0), et en calculant un+1=Q.un (avec la matrice Q au-dessus).]

On fait face alors à deux problèmes :
- Le surfeur aléatoire peut tomber dans un puits : une page internet qui n'a pas de lien sortant ! C'est ici le cas de la page 9. Pour pallier à ce problème, on va partir du principe que quand le surfeur aléatoire tombe sur une telle page, il se téléportera aléatoirement sur n'importe quelle autre page. Cela reviendrait à ajouter sur le graphe des liens sortants de la page 9 vers toutes les autres pages, avec un poids 1/10.
[Matriciellement, cela revient à considérer la matrice P correspondant à la matrice Q où les colonnes nulles sont transformées en matrices n'ayant que le coefficient 1/N]

- Un autre problème, plus vicieux, peut apparaître : le surfeur aléatoire peut être bloqué dans une portion du web, sans pouvoir s'y échapper. C'est le cas par exemple des pages {3,4} ou des pages {6,7}. Pour résoudre ce problème, on décide qu'à tout moment, le surfeur aléatoire peut sauter aléatoirement sur une autre page, avec une probabilité de, disons, α=15% (le coefficient d'échappement).
[Matriciellement, on va considérer la matrice A=(1-α)P+α/N*{1}, où {1} est la matrice NxN composée seulement de 1]

On peut alors revenir à nos calculs de probabilités, en tenant compte de ces sauts aléatoires. Les calculs donnent alors :

Surfeur_al_atoire
Probabilité d'arrêt du surfeur aléatoire en fonction du nombre de clics

On remarque (comme par hasard...) que ces valeurs stagnent après un grand nombre d'itérations. Ce sont en fait, à quelques incertitudes près, les solutions du système que l'on voulait résoudre un peu plus haut ! Les nombres que l'on trouve à l'issu de ce processus sont les scores de pertinence des pages. La méthode que l'on a utilisée ne consiste qu'en des multiplications matrices-vecteurs, ce qui est tout de même bien plus réalisable que la résolution explicite d'un système linéaire.

En regardant les chiffres de plus près, on peut enfin classer nos pages par ordre d'importance : les deux plus importantes sont les pages 3 et 4, suivi des pages 6 et 7. La page 10 arrive bonne dernière, mais on s'y attendait (personne ne la cite, la pauvre...)

calculer l'aire du fractal de l'etoile de david

Et dans la pratique...
Dans la pratique, le calcul du PageRank des pages peut donc se faire en calculant la suite (un) définie un peu plus haut, pour n assez grand, ce qui consiste à faire un grand nombre de multiplications matrice-vecteur.
Quand on regarde la gueule de la matrice A, on s'aperçoit très vite que cette technique est suicidaire : la matrice ne possède aucun coefficient nul, les temps de calculs seront exorbitants. On peut heureusement modifier l'algorithme, en se ramenant à des multiplications par la matrice Q (c'est une matrice creuse - avec plein de 0 - ce qui diminue très nettement le nombre d'opérations à faire). Cela nécessite tout de même de bons ordinateurs, mais Google n'en est pas à un investissement près...

L'époque où Larry Page et Sergey Brin signaient leur thèse -qui n'aura jamais été terminée- décrivant le PageRank appartient à la préhistoire d'Internet.  Aujourd'hui, la formule est toujours cachée au fond d'un tiroir fermé à triple tour dans un bureau secret au dernier sous-sol du Googleplex, seul le principe est à peu près connu. On peut néanmoins connaître le PageRank d'une page donnée, mais ce n'est qu'une valeur entière approchée du logarithme du score, ou quelque chose comme ça. Bref, un nombre entre 0 et 10 (ça devrait être un nombre entre 0 et 1, c'est une probabilité)... À titre d'exemple, le PageRank de ce blog est de 5, celui du c@fé des sciences est de 5 et celui du forum des fans de Michel Sardou est de 3...

Bon, en fait, tout ça, c'est essentiellement sur le plan théorique. Dans la pratique, tout un tas d'autres éléments sont utilisés pour classer les pages, de l'ancienneté du nom de domaine à la localisation du serveur web... Des éléments qui changent en permanence pour toujours coller au mieux aux recherches de vidéos rigolotes avec des chats pour les utilisateurs que nous sommes.

geometrie c quoi le non d'un angle qui mesur 31°
Je ne sais pas si je suis plus étonné par le fait que l'on puisse tomber sur mon blog en tapant ceci ou par le fait que l'on puisse sérieusement se demander quelle est la particularité de l'angle 31°...


Sources :
Démocratie et notoriété sur Internet, JP Delahaye - Pour la Science, novembre 2005, article réédité dans Dossier Pour la Science, Janvier Mars 2010.

Posté par El Jj à 20:16 - Commentaires [14] - Permalien [#]
Tags : , , , , ,

Commentaires sur Comment qu'ça marche, Google ?!

    Merci pour l'article, c'est très intéressant!

    Posté par Klaus, 11 avril 2010 à 21:44 | | Répondre
  • Super interessant

    Merci pour ce billet intéressant !

    Je ne savais pas que l'on pouvait voir le pagerank de n'importe quelle page, c'est plutôt instructif (j'ai donc appris que mon blog est aussi à '5').

    Benjamin

    Posté par benjamin bradu, 11 avril 2010 à 23:46 | | Répondre
  • Ques acco un angle de 31° ?

    En tapant "angle 31°" on tombe sur la 547ème position des recherches via Gougole, si m'suis pas gourré dans mes calculs, au beau milieu des canapés d'angle et de trucs comme ça;
    mais en tapant "particularité angle 31°", ce que je cherche à savoir, hé bien on tombe numbeurre ouone sur Gougole.
    Pas mal !

    Du coup j'ai oublié de regarder cette singulière particularité dont je me fiche d'ailleurs éperdument !

    Mais je vais me renseigner ...

    Posté par Bernard, 12 avril 2010 à 13:48 | | Répondre
  • Passionnant !

    Passionnante analyse. Chapeau bas pour les calculs !

    Dans le même genre, voici un article sur lequel je suis tombé via le forum de WRI (comme pour celui-ci) et qui émet une analyse aussi poussée sur LA question "Comment google fonctionne-t-il?" : http://www.ratmort.fr/blog/le-fonctionnement-de-google

    Posté par FAO, 12 avril 2010 à 14:16 | | Répondre
  • And now...

    Malheureusement pour ton article (en fait nan...) et pour nous pauvres webmasters (surtout...), Google a annoncé vendredi qu'un nouveau paramètre entrait dans son algorithme de classement... le temps de chargement des pages !!

    D'un autre cote, en tant qu'internaute, ce n'est vraiment pas bete car cela va permettre de moins voir de gadgets inutiles sur les sites réputés et peut-etre qu'on va voir disparaitre les pubs qui mettent trois plombes à charger...

    Qui vivra verra !

    source : http://googlewebmastercentral.blogspot.com/2010/04/using-site-speed-in-web-search-ranking.html

    Posté par Nicolas, 12 avril 2010 à 15:41 | | Répondre
  • Et le contenu ?

    Très intéressant ! Mais une autre question clé me tracasse : "Avant de les classer, comment Google trouve-t-il les pages qui contiennent le(s) mot(s) recherchés ?". Vu les péta et les péta octets de données à mettre à jour et indexer en permanence, il doit y avoir là aussi des structures de données et des algorithmes pas piqués des zannetons ...

    Posté par Yogi, 12 avril 2010 à 21:15 | | Répondre
  • @G

    chaque page est identifiée par un titre (title) et des mots-clés (keywords) et une description (description), tu peux visualiser ces infos dans l'entête de toute page en visualisant son code source.

    je pense que pour faire la recherche: "Albert Einstein"

    le moteur va trouver toutes les pages contenant le mot "Albert".

    après parmi ces pages, il va trouver ceux contenant le mot "Einstein".

    Ensuite il va faire le classement de ces dernières selon leurs importance.

    Posté par HousNi, 13 avril 2010 à 00:33 | | Répondre
  • Il y a de grandes chances que la réponse cherchée à la question de géométrie soit "aigu"

    Posté par Tuk', 13 avril 2010 à 07:47 | | Répondre
  • Nicolas > Même pas peur, ma page est très rapide à charger !

    HousNi, je ne pense pas que les choses soient si simples. Tout ce que l'on sait, c'est que google passe son temps à visiter internet pour indexer le contenu. J'ai pas trouvé beaucoup d'informations là-dessus...

    Posté par El Jj, 13 avril 2010 à 12:31 | | Répondre
  • Indexation by Google

    @Yogi : en fait, Google dispose de nombreux robots d'indexation (crawlers) appelés GoogleBots. Il s'agit de programmes qui parcourent le web de lien en lien en récupérant les infos sur les pages parcourues, les pages via laquelle il y est parvenu et celles vers lesquelles il s'est dirigé...

    Une fois qu'il a répertorié des pages, il y retourne de temps à autre (on peut "choisir" d'ailleurs la fréquence que l'on aimerait dans un fichier "robots.txt" ou une balise meta). A ses débuts, il était utile de signaler à Google la création d'un nouveau site via un formulaire afin que les GoogleBots le visitent mais vu le nombre gigantesque de pages qu'il connait maintenant, le site est vite repéré (un lien par-ci par-là, et zou repéré...).

    On peut enfin voir comment son site est vu par les GoogleBots dans l'espace Webmasters de Google : http://www.google.com/support/webmasters/

    Quand à la taille de la base, en effet le nombre doit être très élevé mais, je pense, beaucoup moins que les revenus de la firme...

    Je dis ça, je dis rien...

    @@G : Google ne fait pas que se servir des balises meta. Il se fait aussi une idée du thème via le contenu de la page elle-même il me semble, ou parfois du texte des liens qui pointent vers elle... C'est comme ça qu'en 2005 lorsqu'on cherchait "Nicolas Sarkozy" le deuxième résultat était Iznogood. De nombreux internautes avaient pointaient un lien vers Iznogood en utilisant le texte "Nicolas Sarkozy"...

    Posté par Nicolas, 13 avril 2010 à 13:24 | | Répondre
  • @Housni, Nicolas : Merci de ces pistes, mais pour trouver toutes les pages qui contiennent "Albert" ou "Sarkozy", je doute que Google garde une copie de chaque page (encore que, le cache ...), et je doute surtout qu'il les parcoure toutes à chaque recherche. Il doit donc avoir un arbre de recherche qui "résume" le contenu de chaque page, arbre mis à jour en permanence et accessible simultanément dans le monde entier. Ce qui me semble non trivial.

    Posté par Yogi, 13 avril 2010 à 20:03 | | Répondre
  • comment marche google

    je croyais que le secret de comment marche google c'était ceci :

    http://blueballfixed.ytmnd.com/

    Posté par Robyn Slinger, 14 avril 2010 à 21:53 | | Répondre
  • Sinon, on peut regarder cet intéressant article de vulgarisation (publié dans Quadrature il y a deux ans à peu près) :
    http://www.igt.uni-stuttgart.de/eiserm/enseignement/google.pdf

    Posté par Tuk', 16 avril 2010 à 13:53 | | Répondre
  • Google ne risque pas de référencer 10^100 pages puisque le nombre d'atomes dans l'univers (observable, c'est-à-dire dans un rayon de 13 milliards d'années lumières) est de l'ordre de 10^80. Sur la Terre il y a de l'ordre de 10^50 atomes.

    Posté par JLT, 24 avril 2010 à 21:17 | | Répondre
Nouveau commentaire
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.