Des nombres de Fibonacci aux graphes probabilistes et à Google
par
Le calcul des nombres de Fibonacci par la formule de Binet, qui en donne une expression en fonction de l’indice et du nombre d’or, peut être fait en diagonalisant une matrice 2×2. Le même type de calcul donne des expressions explicites des suites de probabilités dans lesgraphes probabilistes à deux états que l’on voit en terminale ES, ainsi bien sûr que l’expression de l’état stable.
Dans ce texte, on développe à l’identique les deux calculs pour montrer leur similitude. Puis on étend —sans preuves— les deux problèmes aux suites satisfaisant une récurrence linéaire et à (une version simple de) l’algorithme PageRank utilisé par Google pour hiérarchiser les pages Internet.
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