Les maths derrière Google : l'algorithme PageRank

Quand tu tapes quelques mots dans Google, le moteur te renvoie en une fraction de seconde une liste ordonnée de pages, des milliards de candidates triées de la plus pertinente à la moins utile. Comment une machine décide-t-elle qu'une page mérite d'apparaître en premier ? La réponse, imaginée à la fin des années 1990 par Larry Page et Sergueï Brin, repose sur une idée mathématique étonnamment simple : PageRank. Et le plus beau, c'est que tu possèdes déjà tous les outils pour la comprendre.

L'idée de départ : un lien, c'est un vote

Imagine le web comme une immense toile de pages reliées entre elles par des liens hypertextes. Lorsqu'une page A place un lien vers une page B, on peut interpréter ce geste comme un vote : A recommande B. Une première idée naïve consisterait à classer les pages selon leur nombre de liens reçus. Plus une page reçoit de votes, plus elle serait importante.

Mais cette idée a une faille évidente. Tous les votes ne se valent pas ! Un lien venant d'un grand site reconnu compte bien plus qu'un lien venant d'une page inconnue créée hier. PageRank corrige cela avec un principe récursif :

• L'importance d'une page dépend de l'importance des pages qui pointent vers elle.
• Une page qui a beaucoup de liens sortants partage son influence entre eux : chaque lien vaut donc moins.

Autrement dit, l'importance d'une page est une somme pondérée des importances de celles qui la citent. C'est un raisonnement circulaire : pour connaître l'importance de B, il faut connaître celle de A, mais l'importance de A dépend elle-même d'autres pages... Les mathématiques savent justement démêler ce genre de boucle.

La marche aléatoire du surfeur

Pour donner du sens à tout cela, Page et Brin ont introduit une image très parlante : le surfeur aléatoire. Imagine un internaute qui part d'une page au hasard, puis clique au hasard sur l'un des liens présents, arrive sur une nouvelle page, reclique sur un lien au hasard, et ainsi de suite indéfiniment.

La question devient alors probabiliste : après très longtemps, quelle est la probabilité que ce surfeur se trouve sur une page donnée ? Les pages où il passe le plus de temps sont, intuitivement, les plus « centrales » du web, celles vers lesquelles tous les chemins finissent par mener. Le PageRank d'une page n'est rien d'autre que cette probabilité de présence à long terme.

Si une page possède $n$ liens sortants, le surfeur choisit chacun avec la probabilité $\frac{1}{n}$. On répartit ainsi équitablement l'influence d'une page entre toutes ses destinations.

La matrice du web

C'est ici que l'algèbre entre en scène. On numérote les pages de $1$ à $N$ et on construit une grande matrice de transition $P$. Le coefficient situé à la ligne $j$ et la colonne $i$ indique la probabilité de passer de la page $i$ à la page $j$ en un clic. Si la page $i$ a $n$ liens sortants vers certaines pages, on inscrit $\frac{1}{n}$ pour chacune de ces destinations, et $0$ ailleurs.

Notons $\pi$ le vecteur qui contient les importances de toutes les pages. La condition d'équilibre que nous cherchions s'écrit alors de façon remarquablement compacte :

$$\pi =P\pi$$

Chaque ligne de cette égalité dit exactement ce que l'on voulait : l'importance d'une page est la somme pondérée des importances des pages qui pointent vers elle. En notant ${\pi }_j$ l'importance de la page $j$, cela revient à :

$${\pi }_j=\sum _{i\to j}\frac{{\pi }_i}{n_i}$$

où la somme porte sur toutes les pages $i$ qui pointent vers $j$, et $n_i$ est le nombre de liens sortants de $i$. Le vecteur $\pi$ cherché est ce qu'on appelle un état stationnaire : une fois atteint, il ne change plus quand on applique encore la matrice $P$.

Le lien avec les chaînes de Markov

Si ces idées te semblent familières, c'est normal : tu les rencontres en Maths Expertes sous le nom de chaînes de Markov ! Une chaîne de Markov décrit un système qui évolue d'état en état, où la prochaine étape ne dépend que de l'état présent, jamais du passé. Notre surfeur en est l'exemple parfait : la page qu'il visitera ensuite ne dépend que de la page où il se trouve maintenant.

En cours, tu apprends que sous de bonnes conditions, une chaîne de Markov converge vers une distribution stationnaire, un vecteur $\pi$ qui vérifie justement $\pi =P\pi$, et qui ne dépend plus de l'état de départ. PageRank n'est donc rien d'autre que la distribution stationnaire de la gigantesque chaîne de Markov qu'est le web tout entier. Le théorème abstrait du tableau gouverne des milliards de recherches chaque jour.

Un petit problème : les culs-de-sac

Le modèle a un défaut. Que se passe-t-il si le surfeur arrive sur une page sans aucun lien sortant ? Il reste coincé. Pour éviter cela, Google ajoute une astuce : avec une probabilité d'environ $0,15$, le surfeur ne suit pas de lien mais saute vers une page totalement au hasard, comme s'il tapait une nouvelle adresse. On appelle cela le facteur d'amortissement, souvent noté $d\approx 0,85$.

Cette petite correction garantit que la chaîne possède bien une unique distribution stationnaire, et donc que le classement est parfaitement défini. Sans elle, les mathématiques ne garantiraient ni l'existence ni l'unicité du vecteur $\pi$.

Pourquoi c'est génial

Ce qui rend PageRank si élégant, c'est qu'il transforme une question floue, « quelles sont les pages importantes du web ? », en un problème mathématique net et calculable : trouver le vecteur propre d'une matrice, ou la distribution stationnaire d'une chaîne de Markov. Pas besoin d'un humain pour juger chaque page : la structure des liens parle d'elle-même.

La prochaine fois que tu feras une recherche, souviens-toi qu'un théorème de probabilités, le même que celui de tes exercices sur les matrices et les chaînes de Markov, travaille en coulisses. Les maths que tu apprends ne sont pas qu'abstraites : elles ont, littéralement, organisé l'information du monde entier.