Comme chacun sait, les pages correspondant à une requête faite sur le moteur de recherche Google arrivent dans un ordre qui n’est pas aléatoire. C’est ce qui a rendu le moteur si célèbre. Cet ordre reflète une hiérarchie définie par le résultat de l’algorithme PageRank. Cet algorithme prend en entrée le web à un moment donné et produit une liste de « scores », un réel compris entre 0 et 1 pour chaque page du web. À chaque requête, les pages sont présentées par ordre décroissant de score.
L’idée de l’algorithme, c’est de marcher au hasard sur le web et de compter combien de fois on passe sur chaque page. Le \em credo, c’est que plus on revient souvent sur une page, plus elle est pertinente.
L’approche fréquentiste des probabilités suggère que les fréquences de passage sur chaque page après une longue marche sont les probabilités de s’y trouver. Pour cela, la théorie des graphes probabilistes, que l’on peut appeler plus pompeusement la théorie des chaînes de Markov finies et qui est fondée sur les probabilités et un peu d’algèbre linéaire, donne une façon concrète de calculer ces probabilités.
Références :
- Introduction à la théorie des graphes - Butinage graphique Jean-Manuel Mény, Gilles Aldon, Lionel Xavier, CRDP disponible à l’IREM
- Manuel Galejade
- Images des mathématiques
Commentaires