Chargement de l'audio en cours
Plus

Plus

TP2. Algorithme de PageRank
P.219

Mode édition
Ajouter

Ajouter

Terminer

Terminer

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 les réponses

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 les réponses
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 les réponses