🎛️ Calcule le PageRank d'un mini-web de 6 pages
À chaque itération, chaque page redistribue son score à ses voisines. Au bout de quelques itérations, les scores se stabilisent : c'est le PageRank.
Itération
0
Page la + importante
C (0.167)
Somme des scores
1.000
Itération 0 : tous les scores commencent à 1/6 ≈ 0.167. Clique « +1 itération » pour voir les scores évoluer.
🌐 1998 : deux doctorants ont une idée bizarre
En 1998, le moteur de recherche dominant s'appelait AltaVista. Il classait les pages web par fréquence des mots-clés. Quelqu'un qui voulait apparaître en haut de la liste bourrait sa page de mots populaires. Les résultats étaient catastrophiques.
Deux doctorants de Stanford, Larry Page et Sergey Brin, ont proposé une idée radicalement différente : ne pas regarder le contenu de la page, mais qui pointe vers elle. Si beaucoup de pages importantes te citent, tu es importante. C'est tout.
L'idée centrale de PageRank
Le score d'une page = la somme des scores des pages qui pointent vers elle, divisée par leur
nombre de liens sortants.
Mais cette définition est circulaire : pour connaître le score de A, il faut connaître le score de B. Mais pour connaître le score de B, il faut connaître le score de A…
⚡ L'équation magique : un système linéaire
Formalisons. Notons N le nombre de pages, et Pi le score de la page i. Pour chaque page :
Pi = ∑j → i Pj / L(j)
où L(j) = nombre de liens sortants de la page j
Cette équation décrit chaque page en fonction des autres. C'est un système linéaire à N équations et N inconnues. En écriture matricielle :
P = M · P
Où P est le vecteur des scores et M est la matrice de transition du graphe du web. Le PageRank est donc un vecteur propre de M associé à la valeur propre 1.
🎯 Comment on le calcule en pratique ?
Inverser une matrice N × N quand N = 10 milliards (taille du web), c'est impossible directement. L'astuce : itérer.
- Initialise tous les scores à 1/N (pages a priori équivalentes).
- Applique M · P : chaque page redistribue son score à ses voisines.
- Recommence avec le nouveau vecteur P.
- Au bout d'une vingtaine d'itérations, P converge vers le PageRank.
C'est la méthode des puissances de l'algèbre linéaire. Elle converge parce que la matrice M a une structure particulière (matrice stochastique : ses colonnes somment à 1) qui garantit l'existence d'un vecteur propre dominant.
🎲 L'interprétation probabiliste : le « surfeur aléatoire »
Il existe une interprétation magnifique de PageRank. Imagine un internaute qui surfe au hasard :
- Il part d'une page quelconque.
- À chaque clic, il choisit un lien sortant au hasard avec probabilité 1/L(page).
- Il continue indéfiniment.
À long terme, la proportion de temps passée sur chaque page est exactement son PageRank. Le score d'une page = la probabilité d'y être à un moment donné si on surfe au hasard. Le PageRank est donc une distribution stationnaire d'une chaîne de Markov.
🛡️ Le facteur d'amortissement : éviter les pièges
Problème : si une page n'a aucun lien sortant (« cul-de-sac »), le surfeur reste coincé. Si un groupe de pages s'auto-pointe en boucle fermée, le surfeur tourne en rond.
Solution de Page & Brin : à chaque clic, avec probabilité 1 − d ≈ 15%, le surfeur téléporte aléatoirement sur n'importe quelle page du web. Le facteur d est appelé damping factor (généralement d = 0.85). La formule devient :
Pi = 1 − dN + d · ∑j → i Pj / L(j)
Cette modification garantit la convergence et empêche les « manipulations » du PageRank par les webmasters malveillants qui créeraient des fermes de liens.
📐 Comment ça tombe dans ton programme ?
Tu ne verras pas PageRank au BAC SM, mais la matière sous-jacente est dans ton programme :
- Matrices et déterminants (2BAC SM) : PageRank est un calcul matriciel.
- Vecteurs propres et valeurs propres (post-bac, prépa) : PageRank est le vecteur propre de la matrice de transition pour la valeur propre 1.
- Chaînes de Markov (universitaire) : la marche du surfeur aléatoire est une chaîne de Markov, et son PageRank est la mesure stationnaire.
- Probabilités conditionnelles : la probabilité de passer de la page A à la page B sachant qu'on est en A vaut 1/L(A).
🎓 L'héritage : PageRank a inspiré des dizaines d'algorithmes
- HITS (Kleinberg, 1999) : un cousin de PageRank avec deux scores par page (hub et autorité).
- SimRank : mesure de similarité entre deux pages basée sur PageRank.
- Personalized PageRank : variante où le surfeur préfère certaines pages selon l'utilisateur. Utilisé pour les recommandations.
- EigenTrust : extension de PageRank pour calculer la réputation dans les réseaux P2P.
- Centralité d'eigenvecteur en théorie des graphes : la généralisation académique de PageRank, utilisée en analyse de réseaux sociaux, bioinformatique, neurosciences.