L'idée novatrice de Google, qui a fait son succès, a été de classer les pages internet en fonction de leur popularité (le page rank). Le page rank d'une page $k$ dépend du nombre d'autres pages ayant un lien vers cette page $k$ : une page contribue à la popularité d'une page $k$ en proportion de sa propre popularité et en proportion inverse du nombre total de pages qu'elle cite.
Cette formule n'est pas utilisable en pratique. En effet, pour calculer $pr(k)$, il faudrait d'abord calculer tous les $pr(i)$, mais certaines de ces $pr(i)$ dépendent de $pr(k)$ $\dots$
Pour obtenir une approximation de $pr(k)$, on construit une suite $pr_n(k)$ comme suit :
On admet que la suite $(pr_n (k))_n$ tend vers $pr(k)$ lorsque $n$ tend vers l’infini.
Exemple. Voici une liste de pages numérotées de 0 à 9 ainsi que les liens présents sur cette page.
page 0 : $[1, 2, 3]$
page 1 : $[2, 3, 4]$
page 2 : $[3, 4]$
page 3 : $[1, 5, 7, 9]$
page 4 : $[0]$
page 5 : $[1, 3, 7, 9]$
page 6 : $[4, 8]$
page 7 : $[1, 3, 5, 9]$
page 8 : $[0, 9]$
page 9 : $[6, 7, 8]$
Quelles sont les trois pages ayant le page rank le plus élevé ? Effectuer suffisamment d'itérations !
Rôle : calculer la popularité des pages web
Entrées : liste des liens qui partent des pages et nombre d'itérations
Sorties : scores de popularité des pages
Variables :
Constantes :
Début
$\qquad$L = [[1,2,3],[2,3,4],[3,4],[1,5,7,9],[0],[1,3,7,9],[4,8],[1,3,5,9],[0,9],[6,7,8]]
$\qquad$Pour i de 0 à 9:
$\qquad$$\qquad$N[i] $\leftarrow$ longueur(L[i])
$\qquad$nombre_iterations $\leftarrow$ 10
$\qquad$P0 = [1, ..., 1]
$\qquad$Pour j de 0 à nombre_iterations:
$\qquad$$\qquad$ P1 = [0,0,....0]
$\qquad$$\qquad$Pour i de 0 à 9 :
$\qquad$$\qquad$$\qquad$Pour k de 0 à 9:
$\qquad$$\qquad$$\qquad$$\qquad$Si i dans L[k], alors :
$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$P1[i] $\leftarrow$ P1[i] + $\dfrac{\text{P0}[k]}{\text{N[k]}}$
$\qquad$$\qquad$$\qquad$$\qquad$Finsi
$\qquad$$\qquad$$\qquad$Finpour
$\qquad$$\qquad$Finpour
$\qquad$$\qquad$P0 $\leftarrow$ P1
$\qquad$$\qquad$afficher P1
$\qquad$Finpour
Fin
L = [[1,2,3],[2,3,4],[3,4],[1,5,7,9],[0],[1,3,7,9],[4,8],[1,3,5,9],[0,9],[6,7,8]]
N = []
for i in range(len(L)):
N = N + [len(L[i])]
nombre_iterations = 2
P0 = [1]*len(L)
for j in range(nombre_iterations):
P1 = [0]*len(L)
for i in range(len(L)):
for k in range(len(L)):
if i in L[k]:
P1[i] = P1[i] + P0[k]/N[k]
P0 = P1
print(P1)