Comment classer les pages du web par importance en ne regardant que les liens entre elles ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En apprenant comment fonctionne un moteur de recherche, j'ai été surpris de découvrir que l'idée fondatrice de Google, en 1998, était un calcul de probabilités : imaginer un internaute qui clique au hasard. J'ai voulu refaire ce calcul sur un tout petit web de trois pages, pour comprendre pourquoi une page citée par des pages importantes devient importante.

L'enjeu et les notions du programme

Modéliser une navigation aléatoire par une marche sur un graphe et calculer sa distribution stable par un système d'équations.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Le web est un graphe orienté : les pages sont des sommets, les liens des arcs. Problématique : peut-on mesurer l'importance d'une page uniquement à partir de cette structure ?

2. 2. Mathématiques : l'internaute aléatoire

   4 min

   Petit web : A pointe vers B et C, B vers C, C vers A. Un internaute clique sur un lien au hasard, de façon équiprobable parmi les liens de la page. On cherche la proportion de temps $a,b,c$a,b,c passée sur chaque page à long terme.

   Par la formule des probabilités totales, une distribution stable vérifie : $b=\frac{a}{2}$b=a/2 (seul A pointe vers B, avec probabilité $\frac{1}{2}$1/2), $c=\frac{a}{2}+b$c=a/2+b, $a=c$a=c. Avec $a+b+c=1$a+b+c=1 : $a+\frac{a}{2}+a=1$a+a/2+a=1, donc $a=0,4$a=0,4, $b=0,2$b=0,2, $c=0,4$c=0,4.

   C est aussi importante que A, alors qu'elle reçoit deux liens : elle n'en reçoit que de A et B, et B pèse peu. L'importance d'une page dépend de l'importance de celles qui la citent.

   Amortissement : avec une probabilité $0,15$0,15, l'internaute saute sur une page au hasard. On résout $x=\frac{0,15}{3}+0,85\times (\dots )$x=0,15/3+0,85×(…) et on trouve environ $(0,39;0,21;0,40)$(0,39;0,21;0,40).

3. 3. NSI : calculer sur des milliards de pages

   3 min

   Sur le vrai web, on ne résout pas le système directement : on itère. On part de la distribution uniforme et on applique la règle de transition, encore et encore : la suite des distributions converge vers la distribution stable. Quelques dizaines d'itérations suffisent.

   L'amortissement règle deux problèmes : les pages sans lien sortant (où l'internaute serait bloqué) et les groupes de pages qui ne pointent que les unes vers les autres. Il garantit l'existence d'une unique distribution stable. En Python, quelques lignes avec un dictionnaire de listes d'adjacence suffisent à le programmer.

4. 4. Conclusion

   1,5 min

   Le PageRank classe les pages par la proportion de temps qu'y passerait un internaute aléatoire : sur notre exemple, A et C dominent avec 40 %. L'importance se calcule à partir des liens, de façon récursive. J'ouvre sur les manipulations de ce classement par des « fermes de liens ».

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Croire que le PageRank compte seulement le nombre de liens reçus.
• Oublier la condition a + b + c = 1.
• Confondre lien entrant et lien sortant.

Revoir les notions

• Probabilités conditionnelles (Première spé maths) →
• Graphes et marches aléatoires (Terminale maths expertes) →

Autres questions : graphes et réseaux

• Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?
• Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
• Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?
• Combien de créneaux faut-il au minimum pour organiser des examens sans qu'aucun élève n'en ait deux en même temps ?

Toutes les questions maths-nsi →