489
L’algorithme PageRank de Google
Michael Eiserman
Résumé de l’article
Le point fort de Google est qu’il trie intelligemment ses résultats par ordre de pertinence. Le pilier de son succès est une judicieuse modélisation mathématique. Le web est un graphe, qu’il faut exploiter.Plusieurs modèles sont possibles. Mais attention aux « trous noirs ». Pour y échapper, Google utilise un modèle raffiné basé sur le théorème du point fixe. Un moteur de recherche doit non seulement énumérer les résultats d’une requête, mais les classer par ordre d’importance. Estimer la pertinence des pages web est un profond défi de modélisation, que Google relève grâce au théorème du point fixe qui justifie l’algorithme itératif choisi. Le modèle PageRank définit une mesure de « popularité ». La deuxième partie de l’article présente les développements mathématiques : la reformulation matricielle, les matrices stochastiques, le modèle PageRank, le théorème du point fixe, et se termine par quelques approfondissements (chaînes de Markov et ergodicité) et quelques points de réflexion : le modèle est-il plausible, descriptif ou normatif ?
Plan de l’article
- Introduction
- Que fait un moteur de recherche ?
- Le web est un graphe !
- Comment exploiter ce graphe ?
- Premier modèle : comptage naïf
- Second modèle : comptage pondéré
- Troisième modèle : comptage récursif
- Promenade aléatoire
- La loi de transition
- Attention aux trous noirs
- Le modèle utilisé par Google
- Le théorème du point fixe
- Conclusion
- Références
Télécharger l’article en pdf dans son intégralité
<redacteur|auteur=500>