🎛️ PageRank en action
8 pages web, certaines très liées, d'autres isolées. Clique « Itérer » : à chaque étape, la « popularité » se redistribue selon les liens entrants. Les nœuds grossissent selon leur score PageRank.
Itération
0
Top page
—
Écart max
—
Initialisation : chaque page a la même importance 1/N. À chaque itération, l'importance « coule » le long des liens.
🏫 1996 : deux étudiants de Stanford
À l'automne 1996, Larry Page et Sergey Brin, doctorants en informatique à Stanford, travaillent sur un projet de thèse : améliorer la recherche sur le web. À l'époque, les moteurs (AltaVista, Lycos, Yahoo) classent les pages en comptant les occurrences des mots-clés. Résultat : spam massif, pages remplies de listes de mots invisibles, qualité médiocre.
Page a une intuition décisive : traiter le web comme un graphe. Chaque page est un sommet, chaque hyperlien est une arête orientée. Une page « importante » est une page vers laquelle pointent beaucoup d'autres pages importantes. C'est récursif — mais c'est précisément le genre de définition qu'on sait résoudre mathématiquement.
🎯 La formule de PageRank
Soit N pages web. Le PageRank PR(p) d'une page p est défini par :
PR(p) = (1−d)/N + d · Σ PR(q) / L(q)
• la somme porte sur toutes les pages q qui pointent vers p
• L(q) = nombre de liens sortants de q
• d = « facteur d'amortissement » ≈ 0,85 (probabilité de continuer à cliquer)
• (1−d)/N = probabilité de « téléportation » aléatoire
🚶 L'interprétation marche aléatoire : le « surfeur aléatoire »
Imagine un internaute qui part d'une page au hasard et clique uniformément sur les liens. Avec probabilité d = 0,85, il continue à cliquer. Avec probabilité 1−d = 0,15, il s'ennuie et se téléporte à une page totalement aléatoire (pour gérer les pages sans lien sortant et éviter de se coincer).
Le PageRank d'une page = la probabilité que ce surfeur s'y trouve à long terme. Mathématiquement, c'est le vecteur propre dominant d'une certaine matrice de transition.
🧮 Comment on le calcule : itération de la puissance
On ne diagonalise pas une matrice 50 milliards × 50 milliards. À la place, Google utilise la méthode de la puissance :
- Initialiser PR(p) = 1/N pour toute page.
- Pour chaque page, recalculer PR selon la formule.
- Recommencer jusqu'à ce que le vecteur PR ne change plus (convergence).
En pratique, 50 à 100 itérations suffisent pour converger à 10⁻⁶ près sur tout le web. Sur les fermes de serveurs de Google, c'est calculé en quelques heures (l'algorithme est massivement parallélisable, base du framework MapReduce inventé chez Google en 2004).
💰 1998-2024 : de l'algorithme à l'empire
- Janvier 1998 — Page et Brin publient leur article fondateur : « The Anatomy of a Large-Scale Hypertextual Web Search Engine ».
- 4 septembre 1998 — Google Inc. est fondée dans un garage à Menlo Park. Capital initial : 100 000 $ d'un cofondateur de Sun Microsystems.
- 2000 — Google indexe 1 milliard de pages, devient le moteur le plus populaire.
- 2004 — IPO. Capitalisation initiale : 23 milliards . Larry Page et Sergey Brin valent chacun ~130 milliards $. Au moment de l'écriture, ils sont au top 10 mondial des fortunes.
Le brevet de PageRank (n° 6 285 999) est détenu par Stanford. Google paye une licence exclusive. En 2005, Stanford a vendu ses actions Google pour environ 336 millions de dollars — un retour sur investissement académique sans précédent.
🌐 Au-delà de Google : PageRank partout
- Réseaux sociaux : Twitter (X) utilise une variante pour calculer l'influence des comptes. Facebook pour le News Feed.
- Bibliométrie : Eigenfactor (2007) classe les revues scientifiques selon PageRank des citations. Plus précis que l'impact factor classique.
- Biologie : GeneRank classe les gènes les plus « centraux » dans un réseau d'interactions protéiques. Aide à identifier des cibles thérapeutiques.
- Recommandation : Spotify, Netflix, Amazon — algorithmes inspirés par PageRank sur des graphes utilisateurs/contenus.
- Sport : classement des équipes (Football Index, NFL) par diffusion de score à travers les confrontations.
- Linguistique : TextRank (Mihalcea-Tarau 2004) — résumé automatique de textes en classant l'importance des phrases via PageRank sur un graphe de cooccurrences.
- Routage : optimisation de réseaux téléphoniques et de transport.
- Détection de fraude : repérer les comptes bancaires « centraux » dans des graphes de transactions suspectes.
🛡️ La guerre du SEO et de Google
Dès que PageRank devient connu, les spammeurs essaient de le manipuler : fermes de liens, échanges de liens, achat de domaines expirés. Google riposte en permanence :
- 2003 — Florida : premier filtre anti-spam massif.
- 2011 — Panda : pénalise les sites de contenu pauvre.
- 2012 — Penguin : pénalise les liens artificiels.
- 2015 — RankBrain : intégration du machine learning dans le ranking.
- 2019 — BERT : compréhension du langage naturel.
- 2023+ — SGE (Search Generative Experience) : intégration de Gemini dans la recherche.
PageRank original est aujourd'hui un signal parmi ~200 utilisés par Google. Mais il reste l'idée fondatrice autour de laquelle tout l'écosystème SEO et l'algorithme de Google se sont construits.
📐 Le lien avec ton programme
- Vecteurs et matrices : PageRank est le vecteur propre dominant d'une matrice stochastique. Programme algèbre linéaire post-bac.
- Probabilités et chaînes de Markov : interprétation comme marche aléatoire. Programme probabilités 2BAC SM (chaînes vues en prépa).
- Suites récurrentes : la méthode de la puissance est exactement une suite définie par récurrence v_{n+1} = M·v_n. Programme suites 2BAC SM.
- Théorème du point fixe : la convergence repose sur le théorème de Perron-Frobenius (matrices à entrées positives). Sophistiqué, mais l'idée du point fixe est accessible.
- Théorème de Perron-Frobenius (1907) : une matrice stochastique a une unique valeur propre dominante = 1, et le vecteur propre associé est PageRank.