Partie W6 · exercices 31 à 41

PageRank : le surfeur aléatoire

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.

1234
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.

  1. Écris pour chaque page la liste des pages vers lesquelles elle pointe. Compare avec le dictionnaire liens.
  2. Combien de liens entrants reçoit chaque page ?
  3. 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.)

  1. Choisis une page de départ et simule 15 pas en notant les pages visitées.
  2. Compte les passages sur chaque page. Propose un classement des quatre pages.
  3. 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]}

def suivant(site):
    return random.choice(...)                 # à compléter : une page parmi les liens de `site`

site = 1
for i in range(5):
    site = suivant(site)
    print(site)
  1. Exécute le programme plusieurs fois. Quelles pages peuvent suivre la page 1 ? et la page 2 ?
  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]}

def suivant(site):
    return random.choice(liens[site])

nombre = 1000
site = 1
visites = {}
for page in liens:
    visites[page] = 0

for i in range(nombre):
    site = suivant(site)
    visites[site] = visites[site] + ...        # à compléter

for page in visites:
    print(page, visites[page], round(100 * visites[page] / ..., 1), "%")    # à compléter
  1. Exécute le programme avec nombre = 100, puis 1000, puis 10000. Note les pourcentages obtenus.
  2. Relance plusieurs fois avec nombre = 100, puis avec nombre = 10000. Les résultats changent-ils beaucoup ? Que peux-tu en conclure ?
  3. 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.

1234
Le graphe de l'exercice.
  1. Écris son dictionnaire liens.
  2. Dans ton programme, change uniquement liens et relance avec nombre = 10000. Quelles sont les parts des quatre pages ?
  3. 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é.

12345
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]}.

  1. Que risque-t-il d'arriver au surfeur quand il arrive en page 2 ?
  2. Lance ton programme avec ce dictionnaire, jusqu'à ce que le surfeur passe par la page 2. Que se passe-t-il ?
  3. 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
def suivant(site):
    if liens[site] == ...:                 # à compléter : la page n'a aucun lien sortant
        return random.choice(list(liens))
    return random.choice(liens[site])
  1. Que renvoie list(liens) ?
  2. 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.

54123
Deux groupes de pages, {2, 3} et {4, 5}, qui se renvoient les uns aux autres.
1234
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]}.

  1. 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 ?
  2. Pour le second graphe, quels scores obtiens-tu ? Pourquoi toutes les visites finissent-elles par aller sur la page 4 ?
  3. 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
def suivant(site):
    if liens[site] == [] or random.random() < ...:     # à compléter : la probabilité
        return random.choice(list(liens))
    return random.choice(liens[site])
  1. Complète la fonction puis estime les scores des deux graphes de l'exercice précédent avec nombre = 10000.
  2. 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 ?
  3. 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 %.

  1. Quelle page a le meilleur PageRank ? Pourquoi, à ton avis ?
  2. La page 6 (poisson) n'est pointée par aucune page. Quel est son score ?
  3. 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é

  1. Explique en deux phrases le principe du surfeur aléatoire.
  2. Une page contenant une information fausse peut-elle être très bien classée ? Explique.
  3. Pourquoi un moteur de recherche n'utilise-t-il pas uniquement le PageRank pour classer les résultats ?
  4. 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 ».

📝 réponses dans ton compte rendu, exercice 41