In [3]:
import numpy as np
import matplotlib.pyplot as plt

PageRank

On programme un algorithme PageRank avec comme paramètres :

  • la matrice $G$ d'incidence du graphe des pages web ; $G_{ij}=\boldsymbol 1_{i\to j}$, qui vaut $1$ si la page $i$ a un lien vers la $j$. Notons $G_{Markov}$ la matrice de transition associée à la marche aléatoire uniforme sur ce graphe.
  • la loi de l'état initial $\mu$
  • le paramètre $s$ de mélange ; $1-s$ étant la probabilité de se téléporter uniformément sur une page du graphe.
  • err : le seuil de stabilité en dessous du quel on stoppe l'algorithme.

Rappel : la matrice de transition est donnée par $P= s G_{Markov} +(1-s)\mathbb 1/N$ où $N$ est le nombre de pages et $\mathbb 1$ est la matrice $N\times N$ qui ne contient que des $1$. $P$ satisfait la condition de Doeblin : $P_{xy} \geq (1-s)\nu_y$ avec $\nu_y=1/N$ donc, en utilisant que $\mu\mapsto \mu P$ est une $s$-contraction de l'espace de probabilité équipé de la norme $\ell^1$, on a $$ \|\mu P^n-\pi\|_{\ell^1}\leq 2 s^n $$ et de plus $$ \|\mu P^n-\pi\|_{\ell^1}\leq \frac{s}{1-s}\|\mu P^{n}-\mu P^{n-1}\|_{\ell^1} $$ ce qui nous donne une condition pratique pour l'arrêt de l'algorithme.

In [18]:
# PageRank (version calcul matriciel)

def pageRank(G, mu, s = .85, err = 1e-5):
    
    n = G.shape[0]

    # matrice de transition
    rsums = np.sum(G,axis=1) 
    GMarkov = (G.T/rsums).T # on normalise G en une matrice de transition
    P = s*GMarkov + (1-s)/n
    
    # On réitère la multiplication par P jusqu'à l'erreur fixée
    r = mu # loi de l'état initial 
    r0 = np.zeros(n) 
    while np.sum(np.abs(r-r0)) > err*(1-s)/s:
        r0 = r.copy()
        r = np.dot(r0,P)
    return list(r)
In [15]:
# un exemple 
G = np.array([[0,0,1,0,0,0,0],
              [0,1,1,0,0,0,0],
              [1,0,1,1,0,0,0],
              [0,0,0,1,1,0,0],
              [0,0,0,0,0,0,1],
              [0,0,0,0,0,1,1],
              [0,0,0,1,1,0,1]])
In [19]:
pageRank(G,[1,0,0,0,0,0,0])
Out[19]:
[0.054465098875891446,
 0.037267080745293724,
 0.11659909494076758,
 0.24312916534438261,
 0.21009263789706256,
 0.037267080745293724,
 0.3011798414513069]
In [20]:
# dépendance en la loi initiale ?
N = G.shape[0]
pageRank(G,np.ones(N)/N)
Out[20]:
[0.05446515497093738,
 0.03726708074710722,
 0.11659922411614093,
 0.24312916534256918,
 0.21009258180020324,
 0.03726708074710722,
 0.30117971227593365]

Pour un calcul en temps raisonnable on utilise la structure creuse ("sparse" en anglais) de la matrice $G$.

Notons que, si $N$ est le nombre de pages web et $\ell_i$ le nombre de pages que l'on peut attendre en partant de la page $i$, on a pour toute mesure de probabilité $\mu$ : $$ (\mu P)_j = \big(s\mu G_{Markov} + \frac{1-s}{N} \boldsymbol{1}\big)_j = s\sum_{i:\; i\to j} \frac{\mu_i}{\ell_i} + \frac{1-s}{N} $$ Si $L=[L[1],\ldots,L[N]]$ est la liste des liens sortants définie par $L[i]:=\{j :\; i\to j\}$, celle que l'on obtient en pratique, alors la somme ci-dessus a lieu sur les $i$ dans la liste $A[j]$ des liens entrants en $j$, i.e. $A[j]:=\{i :\; i\to j\}$

In [21]:
# construire la liste Ant des antécédants depuis L

def Ant(L):
    N = len(L)
    A = [[]] * N    # on pourrait aussi utiliser une boucle et .append
    for j in range(N):
        A[j] = [i for i in range(N) if j in L[i]]
    return(A)
In [22]:
L = [[1,2],[3],[0],[0,1,2]]
Ant(L)
Out[22]:
[[2, 3], [0, 3], [0, 3], [1]]
In [25]:
# PageRank (version calcul "sparse")

def pageRankSparse(L, mu, s = 0.85, err = 1e-5):
    
    N = len(L)
    r = mu   # loi de l'état initial 
    r0 = np.zeros(N)
    
    while np.sum(np.abs(r-r0)) > err*(1-s)/s:
        
        r0 = r.copy()
        r = (1-s)*np.ones(N)/N
        for j in range(N):
            for i in Ant(L)[j]: 
                r[j] += s*r0[i]/len(L[i]) 

    return list(r)
In [26]:
# cf. exemple 7x7 ci-dessus
""" G = np.array([[0,0,1,0,0,0,0],
                  [0,1,1,0,0,0,0],
                  [1,0,1,1,0,0,0],
                  [0,0,0,1,1,0,0],
                  [0,0,0,0,0,0,1],
                  [0,0,0,0,0,1,1],
                  [0,0,0,1,1,0,1]])"""

L=[[2],[1,2],[0,2,3],[3,4],[6],[5,6],[3,4,6]]  
#! ne pas oublier qu'on part de zéro...

pageRankSparse(L,np.ones(7)/7)
Out[26]:
[0.05446515497093744,
 0.03726708074710726,
 0.11659922411614107,
 0.2431291653425695,
 0.2100925818002035,
 0.03726708074710726,
 0.30117971227593404]