Le page rank de Google

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.

  • Pour une page $k$, notons $\{i_1, i_2, \dots, i_p \}$ les pages ayant un lien vers la page $k$.
  • Notons $N(i)$ le nombre de liens partant de la page $i$.
  • La popularité de la page $k$ est donnée par la formule : $$pr(k) = \sum_{i \in \{i_1, i_2, \dots, i_p \} }\frac{pr(i)}{N(i)}$$

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 initialise $pr_0(k)=1$ pour tous les $k$ ,
  • on calcule $pr_{n+1}(k)$ par la formule $$pr_{n+1}(k) = \sum_{i \in \{i_1, i_2, \dots, i_p \} }\frac{pr_n(i)}{N(i)}$$

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]$

  • La page 5 a des liens vers les pages 1, 3, 7, 9. Ainsi $N(5) = 4$.
  • On cherche dans le tableau les pages citant la page 5, à savoir les pages 3 et 7.
  • A l'initialisation, on a $p_0(0) = 1$, $p_0(1) = 1$, \dots
  • On calcule alors $$p_1(5) = \frac{p_0 (3)}{N(3)} + \frac{p_0 (7)}{N(7)} = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$

Quelles sont les trois pages ayant le page rank le plus élevé ? Effectuer suffisamment d'itérations !

Algorithme : page Rank

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

In [1]:
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)  

[1.5, 1.0833333333333333, 0.6666666666666666, 1.6666666666666665, 1.3333333333333333, 0.5, 0.3333333333333333, 0.8333333333333333, 0.8333333333333333, 1.25]
[1.75, 1.2499999999999998, 0.8611111111111112, 1.5277777777777777, 0.861111111111111, 0.625, 0.4166666666666667, 0.9583333333333333, 0.5833333333333334, 1.1666666666666665]
In [ ]: