© 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 :
Le classement obtenu est en général : 2 - 4 - 1 - 3 mais peut peut varier suivant la simulation.
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.
Chaque numéro de sommet est suivi d'une liste contenant les sommets vers lesquels il pointe.
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.
On retrouve le classement : 2 - 4 - 1 - 3.
#Simulation du surfeur aléatoire pour le graphe G1
parcours(Liens_G1,100000)
{1: 23020, 2: 38465, 3: 7694, 4: 30821}
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
Liens_G2 = { 1:[5] , 2:[1,3,5] , 3:[1,6] , 4:[1,5] , 5:[2,3,4,6] , 6:[5] }
4.b A l'aide d'un appel à la fonction parcours, compléter le tableau.
Le tableau dépend de la simulation, mais permet d'établir le classement suivant pour les pages: 5 - 6 - 1 - 3 - 2 = 4
#Effectuer un appel à la fonction parcours
parcours(Liens_G2,100000)
{1: 14165, 2: 9610, 3: 12707, 4: 9451, 5: 38083, 6: 15984}
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
Liens_G3 = { 1:[3] , 2:[1,3,5] , 3:[1,6] , 4:[1,5] , 5:[2,3,4,6] , 6:[5] }
4.d À l'aide d'un appel à la fonction parcours, réaliser pour G3 un tableau similaire au précédent.
Le tableau dépend de la simulation, mais permet d'établir le classement suivant pour les pages: 3 - 5 - 6 - 1 - 2 = 4
#Effectuer un appel à la fonction parcours
parcours(Liens_G3,100000)
{1: 18110, 2: 6139, 3: 26194, 4: 6017, 5: 24288, 6: 19252}
4.e Vérifier que, par rapport au graphe G2, les notes des pages 1 et 3 ont augmenté. Expliquer ce phénomène.
La note de la page 3 a augmenté car elle est référencée par une page supplémentaire et a donc plus de chances d'être atteinte. Comme cette page 3 pointe sur la page 1 avec une probabilité 1/2, l'augmentation de sa note entraîne indirectement une augmentation de la note de la page 1.
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.
Si on supprime le lien de la page 5 vers la page 3, la page 5 ne pointera plus que vers la page 4, ce qui va augmenter la note de la page 4. Ceci est d'autant plus vraie que la page 5 est fortement référencée et aura donc elle-même une note élevée.
5.b Effectuer les saisies Python nécessaires pour vérifier votre réponse.
#Effectuer les saisies nécessaires
Liens_G={ 1:[5] , 2:[1,3,5] , 3:[2,4] , 4:[3,5] , 5:[3,4] }
Liens_G_modif={ 1:[5] , 2:[1,3,5] , 3:[2,4] , 4:[3,5] , 5:[4] }
N=100000
T1=parcours(Liens_G,N)
T2=parcours(Liens_G_modif,N)
Conclusion="Une simulation avec "+str(N)+" déplacements donne: \n -le tableau "+str(T1)+" pour le graphe G initial\n -le tableau "+str(T2)+" pour le graphe G modifié.\nLa note du sommet 4 est donc passée de "+str(T1[4]/N)+" à "+str(T2[4]/N)
print(Conclusion)
Une simulation avec 100000 déplacements donne: -le tableau {1: 4893, 2: 14969, 3: 30079, 4: 26763, 5: 23296} pour le graphe G initial -le tableau {1: 3700, 2: 11068, 3: 22217, 4: 37082, 5: 25933} pour le graphe G modifié. La note du sommet 4 est donc passée de 0.26763 à 0.37082
© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.