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 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]
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 :
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 :
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.
/http%3A%2F%2Fstorage.canalblog.com%2F72%2F92%2F210892%2F113119539_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F00%2F91%2F210892%2F107069165_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F33%2F48%2F210892%2F101190494_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F83%2F38%2F210892%2F101168363_o.png)