import numpy as np
import matplotlib.pyplot as plt
On programme un algorithme PageRank avec comme paramètres :
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.
# 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)
# 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]])
pageRank(G,[1,0,0,0,0,0,0])
# dépendance en la loi initiale ?
N = G.shape[0]
pageRank(G,np.ones(N)/N)
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\}$
# 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)
L = [[1,2],[3],[0],[0,1,2]]
Ant(L)
# 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)
# 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)