Cette activité s’inscrit dans la thématique Le Web du programme de SNT. Elle est proposée par Christophe Mieszczak, actuellement professeur de mathématiques et d’ISN au lycée Léonard de Vinci à Calais.
Le PageRank est l’algorithme d’analyse des liens hypertextes utilisé pour le classement des pages Web par le moteur de recherche Google. Le PageRank n’est qu’un indicateur parmi d’autres dans l’algorithme qui permet de classer les pages du Web dans les résultats de recherche. Ce système a été inventé par Larry Page, cofondateur de Google. Ce mot est une marque déposée.
Le principe de base est d’attribuer à chaque page une valeur proportionnelle au nombre de fois que passerait par cette page un utilisateur parcourant le Web en cliquant aléatoirement, sur un des liens apparaissant sur chaque page.
A chaque instant, des “robots”, appelés “spiders”, parcourent la toile, de lien en lien, et mettent ainsi sans cesse à jour le PageRank des pages du web.
On schématise une page web par un cercle et les liens entre les pages par des flèches. Trois pages A, B et C sont donc représentées de la façon suivante.
L’objectif est de déterminer la fréquence avec laquelle on visite chaque page lorsqu’on parcourt le graphe de façon aléatoire.
Au départ le nombre de visite de chaque page est nul.
On choisit une page de départ au hasard et on incrémente de 1 son nombre de visite (il passe donc à 1).
A l’aide d’une pièce de monaie équilibrée, nous allons nous promener sur ce graphe en respectant les règles ci-dessous:
A chaque nouvelle page atteinte, on augmente son nombre de visite(s) et on se déplace à nouveau.
Réalisez cette expérience 30 fois puis donnez un PageRank à nos trois pages, c’est à dire leurs fréquences de visite.
On réalise l’expérience en partant de la page C. Voici la liste des résultats obtenus : C, A, B, A, B, A, C, B, A, B, A, B, A, C, A, B, A, C, B, A, B, A, C, B, A, C, A, C, A, B. On compte le nombre d’apparitions de A, B et C : , et .
Et donc les PageRank associés sont : , et .
Créez un nouveau programme Python et appelez le pagerank.py
. Importez le module random
qui sera nécessaire pour cette activité en tapant from random import *
dans le script. Définissez ensuite une fonction nommée PR(n)
dont l’objectif sera de réaliser n déplacements aléatoires sur le graphe précédent puis de renvoyer les résultats attendus.
On note nA
, nB
et nC
les variables entières égales au nombre de visites des pages A, B et C.
Commencez, dans notre fonction, par les définir en les initialisant à 0.
On définit les 3 variables.
La page en cours de visite sera modélisée par la variable page
qui pourra prendre les valeurs "A"
ou "B"
ou "C"
. Pour démarrer il nous faut donc choisir au hasard entre A, B et C. Pour cela on va utiliser la fonction randint(a,b)
du module random
. Cette fonction génère un nombre aléatoire entre a et b.
Définir la variable start=randint(0,2)
qui choisit de façon équiprobable un nombre aléatoire entier dans {0,1,2} puis distinguer les cas suivants à l’aide d’un test “if” :
start
vaut 0 alors page
sera égal à "A"
et nA
à 1.start
vaut 1 alors page sera égal à "B"
et nB
à 1.page
sera égal à "C"
et nC
à 1.On distingue les trois cas avec
if
,elif
etelse
.
Il faut maintenant définir une boucle qui visitera n pages aléatoirement. A chaque “tour” de cette boucle :
page
est égal à "A"
d’où partent deux liens, on définit alea=randint(0,1)
:
alea
vaut 0 alors on passe à la page “B” et nB
augmente de 1nC
augmente de 1page
est égal à "B"
d’où part un seul lien alors on passe à la page “A” et nA
augmente de 1Ecrire cette boucle.
Il faut faire bien attention à l’indentation dans la disjonction des cas et des sous-cas.
for i in range(n):
if page=="A":
alea=randint(0,1)
if alea==0:
page="B"
nB=nB+1
else:
page="C"
nC=nC+1
elif page=="B":
page="A"
nA=nA+1
else:
alea=randint(0,1)
if alea==0:
page="A"
nA=nA+1
else:
page="B"
nB=nB+1
Une fois la boucle terminée, il faut renvoyer les résultats attendus, c’est-à-dire les fréquences de visite de “A”, “B” et “C” après n+1 parcours (en comptant le choix de départ).
Définir ainsi les variables fA
, fB
et fC
qui désignent les fréquences de visite des trois pages et terminer la fonction par return fA, fB, fC
.
Les fréquences sont définies de la manière suivante :
Testez votre algorithme avec 100 puis 1000 puis 10000 déplacements. Classez A, B et C par popularité.
Rendez-vous dans la console Python en sélectionnant les trois points à gauche du nom du script et en choisissant Exécuter le script. Tapez ensuite
PR(100)
,PR(1000)
etPR(10000)
et observez les résultats. On a ici ajouté les instructionsround(fA,2)
,round(fB,2)
etround(fC,2)
dans le script pour arrondir les fréquences à deux chiffres après la virgule.
Les résultats de la question 1 étaient finalement assez proches de ce que l’on obtient ici !
Voici un nouveau graphe qui contient cette fois quatre pages : A, B, C et D.
Observez le nouveau graphe représentant les liens entre les pages A, B, C et D et identifiez quel est le problème.
Si l’on se retrouve sur la page B, il n’y a aucun moyen de revenir sur les pages A, C ou D. De même, la page D ne mène à aucune autre page.
Pour pallier à ce problème, on décide que si la page visitée ne redirige pas vers une autre page, alors on choisit au hasard la page suivante parmi les autres.
Adapter la fonction PR(n)
pour calculer le PageRank des pages A, B, C et D. Testez ensuite votre algorithme avec 100 puis 1000 puis 10000 déplacements. Classez A, B, C et D par popularité.
Voici les résultats obtenus après avoir modifié la fonction :
Voici un nouveau graphe.
Observez le graphe et trouvez quel est le problème.
Aucune page ne mène vers la page D.
Pour pallier à ce problème on décide que, à chaque page visitée quelle qu’elle soit, on choisit une fois sur vingt la page suivante au hasard parmi toutes les pages.
Adapter la fonction PR(n)
pour calculer le PageRank des pages A, B, C et D. Testez ensuite votre algorithme avec 100 puis 1000 puis 10000 déplacements. Classez A, B, C et D par popularité.
Voici les résultats obtenus après avoir modifié la fonction :
On a ajouté une disjonction de cas en début de boucle pour tester si nA
, nB
, nC
ou nD
n’est pas multiple de 20 :
if nA%20==0 or nB%20==0 or nC%20==0 or nD%20==0:
alea=randint(0,3)
if alea==0:
page="A"
nA=nA+1
elif alea==1:
page="B"
nB=nB+1
elif alea==2:
page="C"
nC=nC+1
else:
page="D"
nD=nD+1