Chargement de l'audio en cours
Plus

Plus

TP2. Algorithme de PageRank
P.219

TP INFO


2
Algorithme de PageRank




Énoncé

On considère le graphe orienté ci‑contre. Un internaute est placé initialement à sur le site . Chaque minute, il choisit un site vers lequel il se dirige. Chaque lien possible est équiprobable : ainsi, à , il a une probabilité égale à d’être en et une probabilité égale à d’être en .

Algorithme de PageRank

Question préliminaire :

1. Quelle est la probabilité d’être en au temps  ?


2. Quelle est la probabilité d’être en au temps  ?


En assimilant les probabilités aux fréquences obtenues au bout d’un temps très long, on attribue une pondération à chaque sommet du graphe qui permet de classer les sites.
Voir la correction

Objectif

Découvrir un algorithme PageRank à l’aide d’une des deux méthodes.
MÉTHODE DE RÉSOLUTION 1
TABLEUR

1. Écrire la matrice de transition associée au graphe probabiliste.


2. a. Recopier la feuille de calcul suivante.

aths expertes - chapitre 7 - Suites et matrices - TP2. Algorithme de PageRank

b. Quelle formule faut‑il écrire dans la cellule F6 et étirer sur la plage F6:J10 pour obtenir  ?


c. Compléter les cellules de la plage F11:J15 en s’inspirant du contenu des cellules de la plage F6:J10 afin d’obtenir .
Calculer ensuite sur la plage F16:J20.


3. En déduire une estimation de la probabilité, au bout d’un temps très long, d’être sur chacun des sites.


4. Cette probabilité dépend‑elle du choix du site de départ ?
Voir la correction
MÉTHODE DE RÉSOLUTION 2
PYTHON

Le programme suivant permet de déterminer les pondérations de chaque site.

1. Compléter la fonction promenade qui simule les 1 000 premières minutes de la navigation du surfeur.

import random
def promenade():
# Simule les 1000 premières minutes de la marche aléatoire et renvoie le sommet sur lequel est le surfeur à la fin.
	sommet = "a"
	for pas in range(...):
		alea = random.random()
		if sommet == "a":
			if alea < 0.5:
				sommet = "b"
			else:
				...
			elif ...
			elif ...
			elif ...
			else:
				...
	return sommet

2. Simuler, avec la fonction PR à compléter ci‑dessous, la navigation de 1 000 surfeurs, et en déduire une estimation de la probabilité d’être sur chacun des sites au bout d’un temps très long.

def PR():
	effectifs = 5*[0]
	surfeurs = ...
	for k in ...:
		sommetfinal = promenade()
		if sommetfinal == "a":
			effectifs[0] = effectifs[0] + 1/surfeurs
		elif ...
		elif ...
		elif ...
		else:
			...
	return effectifs


3. Modifier le programme pour vérifier que le choix du site initial ne modifie pas les probabilités obtenues dans la question précédente.
Voir la correction
Utilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.