Comment classer les pages ? Un graphe, des liens et beaucoup de hasard
Quand tu cherches un mot, des centaines de pages peuvent convenir. Laquelle montrer en premier ? Au début des années 2000, les créateurs de Google ont eu une idée : une page est importante si beaucoup de pages importantes pointent vers elle. Ce principe s'appelle le PageRank, du nom de son inventeur Larry Page. Ce n'est qu'un critère parmi d'autres dans le classement d'un moteur de recherche.
CoursLe Web est un graphe orienté
Dans le thème Localisation, un graphe relie des sommets par des arêtes, sans direction. Pour le Web, les liens ont un sens : la page a peut contenir un lien vers la page b sans que b en ait un vers a. On dessine donc une flèche de a vers b.
Les pages sont les sommets ; les liens sont les arcs (des flèches).
Les liens sortants d'une page sont ceux qui partent d'elle ; les liens entrants sont ceux qui arrivent sur elle.
Pour décrire le graphe en Python, on utilise un dictionnaire : la clé est une page, la valeur est la liste des pages vers lesquelles elle pointe.
Un graphe de quatre pages. La flèche de 1 vers 2 signifie que la page 1 contient un lien vers la page 2. Il n'y a pas de flèche de 2 vers 4 : la page 2 n'a pas de lien vers la page 4.
liens.py
liens = {1: [2, 3], 2: [3], 3: [1, 2], 4: [2, 3]}
EX 31Je découvre🌶️prise en main
Exercice 31 — Lire un graphe orienté
Observe le graphe ci-dessus.
Écris pour chaque page la liste des pages vers lesquelles elle pointe. Compare avec le dictionnaire liens.
Combien de liens entrants reçoit chaque page ?
Quelle page ne reçoit aucun lien ? Peut-on y arriver en cliquant sur des liens ?
Indice
Un lien entrant sur la page 3 est une flèche qui arrive sur 3.
📝 réponses dans ton compte rendu, exercice 31
CoursLe surfeur aléatoire
Pour mesurer l'importance des pages, on imagine un surfeur aléatoire : il choisit une page au hasard, puis, toujours au hasard, il suit l'un des liens de la page où il se trouve vers une autre page. Il répète cela sans arrêt, en comptant combien de fois il passe sur chaque page.
Le score d'une page
Le score d'une page est la part des visites qu'elle reçoit : score (en %) = nombre de visites ÷ nombre total de pas × 100. Plus le surfeur marche longtemps, plus ces scores se stabilisent : c'est une estimation du PageRank.
Pour t'entraîner sans programmer, tu peux regarder le surfeur marcher dans l'outil Surfeur aléatoire.
EX 32Je m'entraîne🌶️🌶️application
Exercice 32 — Le surfeur à la main
Pour le graphe ci-dessus, simule un surfeur avec une pièce : à chaque page qui a deux liens, pile choisit le premier lien de la liste, face choisit le second. (Une page avec un seul lien ne laisse pas le choix.)
Choisis une page de départ et simule 15 pas en notant les pages visitées.
Compte les passages sur chaque page. Propose un classement des quatre pages.
Compare ton classement avec celui de deux camarades. Ce classement est-il toujours le même ?
Indice
Note la suite des pages, par exemple : 1, 3, 2, 3, 1…
📝 réponses dans ton compte rendu, exercice 32
CoursLe surfeur en Python
On écrit une fonction qui fait faire un pas au surfeur : à partir de la page où il est, elle renvoie une page choisie au hasard parmi ses liens sortants. La fonction random.choice(liste) choisit un élément au hasard dans une liste.
EX 33Je programme🌶️🌶️application
Exercice 33 — Un pas du surfeur
Copie le programme (ou ouvre pagerank_depart.py de Web.zip) et complète la ligne indiquée. Enregistre-le sous le nom demandé.
pagerank.py
import random
liens = {1: [2, 3], 2: [3], 3: [1, 2], 4: [2, 3]}
defsuivant(site):
return random.choice(...) # à compléter : une page parmi les liens de `site`
site = 1for i inrange(5):
site = suivant(site)
print(site)
Exécute le programme plusieurs fois. Quelles pages peuvent suivre la page 1 ? et la page 2 ?
Que fait la boucle for i in range(5) ?
Indice
liens[site] est la liste des pages vers lesquelles pointe site.
💾 NOM_Prenom_ex33.py
EX 34Je programme🌶️🌶️🌶️plusieurs étapes
Exercice 34 — Compter les visites
On complète le programme pour compter les visites. Le dictionnaire visites associe à chaque page son nombre de passages. Complète les deux lignes indiquées.
pagerank.py
import random
liens = {1: [2, 3], 2: [3], 3: [1, 2], 4: [2, 3]}
defsuivant(site):
return random.choice(liens[site])
nombre = 1000
site = 1
visites = {}
for page in liens:
visites[page] = 0for i inrange(nombre):
site = suivant(site)
visites[site] = visites[site] + ... # à compléterfor page in visites:
print(page, visites[page], round(100 * visites[page] / ..., 1), "%") # à compléter
Exécute le programme avec nombre = 100, puis 1000, puis 10000. Note les pourcentages obtenus.
Relance plusieurs fois avec nombre = 100, puis avec nombre = 10000. Les résultats changent-ils beaucoup ? Que peux-tu en conclure ?
Quelle page obtient le meilleur score ? Quelle page a un score voisin de 0 ? Explique pourquoi.
Indice 1
Chaque visite ajoute 1 au compteur de la page.
Indice 2
Le pourcentage se calcule par rapport au nombre total de pas, c'est-à-dire nombre.
💾 NOM_Prenom_ex34.py
EX 35Je m'entraîne🌶️🌶️🌶️plusieurs étapes
Exercice 35 — Un autre graphe
Voici un autre graphe de quatre pages.
Le graphe de l'exercice.
Écris son dictionnaire liens.
Dans ton programme, change uniquement liens et relance avec nombre = 10000. Quelles sont les parts des quatre pages ?
Quelle page est la mieux classée ? Retrouve-t-on le même résultat dans l'outil Surfeur aléatoire ?
Indice 1
Page 1 : 2, 3 et 4. Page 2 : 1 et 4. Page 3 : 1 et 4. Page 4 : 2.
Indice 2
Il suffit de changer la première ligne du programme : tout le reste fonctionne pour n'importe quel graphe.
💾 NOM_Prenom_ex35.py
CoursQuand le surfeur est coincé
Le Web réel est plein de pages sans lien sortant, ou de groupes de pages qui se renvoient les uns aux autres sans jamais mener ailleurs. Le surfeur aléatoire peut alors rester bloqué.
Un graphe avec une page sans lien sortant.
EX 36Je comprends🌶️🌶️application
Exercice 36 — Le surfeur est coincé
Dans ce graphe, la page 2 n'a aucun lien sortant : liens = {1: [2, 3], 2: [], 3: [4, 5], 4: [3], 5: [3, 4, 2]}.
Que risque-t-il d'arriver au surfeur quand il arrive en page 2 ?
Lance ton programme avec ce dictionnaire, jusqu'à ce que le surfeur passe par la page 2. Que se passe-t-il ?
Que vaut liens[2] ? Pourquoi random.choice ne peut-il pas fonctionner ?
Indice
Une liste vide ne contient aucun élément à choisir.
📝 réponses dans ton compte rendu, exercice 36
EX 37Je programme🌶️🌶️🌶️plusieurs étapes
Exercice 37 — Se téléporter quand on est bloqué
Pour résoudre le problème, on décide que si le surfeur est bloqué, il se téléporte sur une page choisie au hasard parmi toutes les pages. Voici la nouvelle fonction. Complète-la, puis estime les scores du graphe de la page 2 sans lien.
pagerank.py
defsuivant(site):
if liens[site] == ...: # à compléter : la page n'a aucun lien sortantreturn random.choice(list(liens))
return random.choice(liens[site])
Que renvoie list(liens) ?
Lance le programme avec nombre = 10000. Quels scores obtiens-tu ?
Indice
Une page sans lien sortant a pour liste [] : on peut la comparer avec [].
💾 NOM_Prenom_ex37.py
CoursLes pièges
Se téléporter seulement quand on est bloqué ne suffit pas : certains groupes de pages forment un piège dont on ne sort plus, même si chaque page a des liens sortants.
Deux groupes de pages, {2, 3} et {4, 5}, qui se renvoient les uns aux autres.La page 4 ne renvoie que vers elle-même.
EX 38Je comprends🌶️🌶️🌶️plusieurs étapes
Exercice 38 — Les pièges
Estime les scores de ces deux graphes avec le programme de l'exercice précédent (téléportation seulement si bloqué) et nombre = 10000.
Graphe de la première figure (page 1 vers 2, 3, 4 et 5 ; 2 ↔ 3 ; 4 ↔ 5) : liens = {1: [2, 3, 4, 5], 2: [3], 3: [2], 4: [5], 5: [4]}.
Graphe de la seconde figure : liens = {1: [2, 3], 2: [1, 3], 3: [1, 4], 4: [4]}.
Pour le premier graphe, lance le programme plusieurs fois, avec la page 1 pour départ. Que remarques-tu sur les scores des pages 2 et 3, et ceux des pages 4 et 5 ?
Pour le second graphe, quels scores obtiens-tu ? Pourquoi toutes les visites finissent-elles par aller sur la page 4 ?
Pourquoi la téléportation « seulement si bloqué » ne règle-t-elle pas ces deux problèmes ?
Indice 1
Dans le premier graphe, quand le surfeur quitte la page 1, il entre dans l'un des deux groupes. Peut-il en ressortir ?
Indice 2
La page 4 a bien un lien sortant : vers elle-même.
💾 NOM_Prenom_ex38.py
CoursLe surfeur raisonnable
Pour sortir des pièges, l'algorithme évolue : à chaque pas, avec une petite probabilité (15 % dans la version d'origine de Google), le surfeur se téléporte sur une page quelconque, au lieu de suivre un lien. C'est le surfeur raisonnable : il lui arrive de taper une nouvelle adresse au lieu de cliquer. Pour tirer un événement avec une probabilité de 15 %, on utilise random.random(), qui renvoie un nombre au hasard entre 0 et 1 : le nombre est inférieur à 0,15 dans 15 % des cas.
EX 39Je programme🌶️🌶️🌶️🌶️défi
Exercice 39 — Le surfeur raisonnable
Modifie la fonction suivant pour que le surfeur se téléporte si la page n'a aucun lien, ou avec une probabilité de 0,15 à chaque pas.
pagerank.py
defsuivant(site):
if liens[site] == [] or random.random() < ...: # à compléter : la probabilitéreturn random.choice(list(liens))
return random.choice(liens[site])
Complète la fonction puis estime les scores des deux graphes de l'exercice précédent avec nombre = 10000.
Que deviennent les scores des pages qui étaient piégées ? Et celui de la page 1 du premier graphe, qui ne recevait aucun lien ?
Pourquoi un surfeur qui se téléporte de temps en temps donne-t-il un classement plus fiable ?
Indice
15 % se note 0.15 en Python.
💾 NOM_Prenom_ex39.py
EX 40Je m'entraîne🌶️🌶️🌶️plusieurs étapes
Exercice 40 — Que vaut le mini-Web ?
Dans l'outil Surfeur aléatoire, choisis le graphe « mini-Web » (les six pages de la partie W5) et règle la téléportation sur 15 %.
Quelle page a le meilleur PageRank ? Pourquoi, à ton avis ?
La page 6 (poisson) n'est pointée par aucune page. Quel est son score ?
Ajoute un lien de la page 4 vers la page 6. Que devient son score ? Que se passe-t-il si, à la place, les pages 1, 2 et 3 pointent chacune vers la page 6 ?
Indice
Dans l'outil, tu peux modifier les liens dans la zone de texte, puis relancer le calcul.
📝 réponses dans ton compte rendu, exercice 40
CoursCe que PageRank ne dit pas
Le PageRank mesure la popularité d'une page à partir des liens, pas la vérité de son contenu. Des personnes qui veulent faire monter leurs pages dans les résultats (on parle de référencement) créent parfois de faux liens ; les moteurs luttent contre ces manipulations.
EX 41Je synthétise🌶️🌶️🌶️plusieurs étapes
Exercice 41 — Popularité et vérité
Explique en deux phrases le principe du surfeur aléatoire.
Une page contenant une information fausse peut-elle être très bien classée ? Explique.
Pourquoi un moteur de recherche n'utilise-t-il pas uniquement le PageRank pour classer les résultats ?
Que ferais-tu, avant de faire confiance à un résultat, pour vérifier une information ?
Indice
Pense à la différence entre « très consultée » et « exacte ».