© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Elaboré par Larry Page et Sergey Brin, l’algorithme de Pagerank a permis à Google, nouvel arrivant, de prendre en quelque mois le monopole des moteurs de recherche thématique.
L’idée est d'attribuer à chaque page une « note » ou « score » ou « Pagerank » entre 0 et 1 qui caractérise la pertinence de cette page, en respectant les règles suivantes :
Le but de l'activité est de présenter une version simplifiée du PageRank : L'algorithme du surfeur aléatoire.
Pour modéliser les interconnexions entre différentes pages, on utilise un graphe orienté dans lequel :
Question 1 :
Le graphe G1 ci-dessous correspond à une situation de 4 pages. Par exemple, la page 2 propose des liens vers les pages 1 et 4.
Recopier le tableau et suivre les instructions suivantes pour le remplir :
En langage Python, on modélise le graphe G1 précédent à l'aide de la structure Liens_G1 donnée ci-dessous.
Question 2 : Expliquer brièvement comment les informations du graphe sont codées dans Liens_G1.
La fonction parcours(Liens,n) fournie permet, lorsqu’on a défini une liste de liens, de simuler un parcours dans le graphe, avec n visites de pages, en comptant le nombre de fois que chaque sommet est visité.
Attention : Penser à exécuter la zone ci-dessous (et les suivantes) avec SHIFT+Entrée.
#Structure permettant de modéliser le graphe G1
Liens_G1 = { 1:[2,3,4] , 2:[1,4] , 3:[1,4] , 4:[2] }
#Cette instruction permet d'utiliser des fonctions de choix aléatoires
from random import*
def parcours(Liens,n):
"""
Cette fonction simule un parcours de n pages
Les pages sont numérotés 1,2,...
Les arêtes sont définies par les Liens
"""
#On choisit un sommet de départ au hasard
Sommet=randint(1,len(Liens))
# Initialisation des compteurs du nombre de passages pour chaque sommet
# 1:0 2:0 ...
Passages = {S:0 for S in Liens}
#On répète n fois:
for k in range(n):
#on change de sommet
Sommet = choice(Liens[Sommet])
#on incrémente le compteur du sommet visité (augmente de 1)
Passages[Sommet] += 1
#La fonction renvoie les compteurs
return Passages
Question 3 :
Exécuter l'appel à la fonction parcours ci-dessous. A l'aide du résultat, proposer un classement des 4 pages du graphe G1, et comparer avec la réponse à la question 1.
#Simulation du surfeur aléatoire pour le graphe G1
parcours(Liens_G1,100000)
Question 4 :
On considère le graphe G2 ci-dessous, qui modélise les liens entre 6 pages.
4.a Définir une structure Liens_G2 correspondant à ce graphe.
#Créer une structure permettant de modéliser le graphe G2
4.b A l'aide d'un appel à la fonction parcours, compléter le tableau.
#Effectuer un appel à la fonction parcours
On considère le graphe G3 obtenu en remplaçant, sur le graphe G2, le lien de la page 1 vers la page 5 par un lien de la page 1 vers la page 3.
4.c Tracer le graphe G3 et créer la structure Liens_G3 correspondante.
#Créer une structure permettant de modéliser le graphe G2
4.d À l'aide d'un appel à la fonction parcours, réaliser pour G3 un tableau similaire au précédent.
#Effectuer un appel à la fonction parcours
4.e Vérifier que, par rapport au graphe G2, les notes des pages 1 et 3 ont augmenté. Expliquer ce phénomène.
Question 5 :
On considère le graphe G ci-dessous, qui modélise les liens entre 5 pages.
5.a Si on supprime le lien de la page 5 vers la page 3, pensez-vous que la note de la page 4 va augmenter ou diminuer ? Justifier brièvement la réponse.
5.b Effectuer les saisies Python nécessaires pour vérifier votre réponse.
#Effectuer les saisies nécessaires
© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.