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 à t=0t=0 sur le site aa. Chaque minute, il choisit un site vers lequel il se dirige. Chaque lien possible est équiprobable : ainsi, à t=1t=1, il a une probabilité égale à 0,50{,}5 d’être en bb et une probabilité égale à 0,50{,}5 d’être en dd.

Algorithme de PageRank

Question préliminaire :

1. Quelle est la probabilité d’être en cc au temps t=2t=2 ?


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


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 P\mathrm{P} 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 P2\mathrm{P}^2 ?


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 P3\mathrm{P}^3.
Calculer ensuite P4\mathrm{P}^4 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
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.