RUFFIE Christian & ROUX Tom
Dans ce projet, nous étudierons l'algorithme du Page Rank de Larry Page.
Nous commencerons par le voir comme une chaîne de Markov avant d'explorer la partie algèbre linéaire.
#Liste des importations
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.cm as cm
L'idée la plus naturelle pour représenter la navigation de page en page d'un utilisateur sur le web est à travers une chaîne de Markov.
En effet, il passe d'une page à une autre grâce aux liens cliquables disponibles sur la page où il se trouve. La page où il ira ensuite dépend donc uniquement de la page où il se trouve en ce moment (savoir sur quelle page il était avant n'a aucune importance) et des liens disponibles sur la page actuelle.
Ainsi, les chaînes de Markov peuvent être définies comme des suites par récurrence où $M$ est la matrice de transition d'un état $x_n$ à un état $x_{n+1}$ : $$ x_{n+1} = Mx_n$$ avec $x_0$ l'état initial qui est la page où se trouve notre utilisateur au tout début.
Naturellement, nous voulons voir quelle sera la limite de cette suite afin de déterminer avec quelle probabilité chaque page sera visitée. En mettant la probabilité que chaque page soit visitée dans un vecteur, nous obtenons ce que nous appelerons le vecteur de score.
C'est ce vecteur de score qui sert à classer les pages par ordre de pertinence décroissant lorsque nous faisons une recherche Google. La page avec la plus grande probabilité (le plus grand score) apparaîtra donc en premier.
En réalité, Google couple cet algorithme du Page Rank avec d'autres algorithmes (par exemple le fait d'accorder plus d'importance aux liens venant d'une page reconnue comme fiable) afin d'avoir un classement plus juste.
Les chaînes de Markov sont représentables par des graphes orientés de façon assez intuitive :
G = nx.DiGraph()
[G.add_node(k) for k in [1,2,3,4]]
G.add_edges_from([(1,3), (3,1), (1,4), (4,1),
(1,2), (2,3), (2,4), (4,3) ])
pos = nx.circular_layout(G)
color_map = list(nx.pagerank(G).values())
nx.draw(G,
pos=pos,
width=2.0,
connectionstyle = 'arc3, rad = 0.1',
node_color = 'lightsteelblue',
node_size = 2500,
with_labels = True)
plt.show()
La matrice de transition de notre chaîne se trouve en prennant $ M = \begin{pmatrix} P(1,1) & P(1,2) & P(1,3) & P(1,4)\\ P(2,1) & P(2,2) & P(2,3) & P(2,4)\\ P(3,1) & P(3,2) & P(3,3) & P(3,4)\\ P(4,1) & P(4,2) & P(4,3) & P(4,4)\\ \end{pmatrix}$
avec $P(i,j)$ la probabilité de passer de l'état $i$ à l'état $j$
Voyons maintenant un premier exemple en reprennant le graphe précédent et $x_0 = (\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})^T$.
Cela correspond à commencer au hasard avec une probabilité uniforme sur l'une des 4 pages disponibles.
La matrice de transition de cette chaîne est d'après la définition précédente : $$M = \begin{pmatrix} 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ 1 & 0 & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{2} & 0\\ \end{pmatrix}$$
Calculons les différentes valeurs de $x_n$ :
M = np.array(nx.adjacency_matrix(G).todense())
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
n = G.number_of_nodes()
scores = np.ones(n) / n
listScores = [scores]
for _ in range(10):
scores = scores @ M
listScores.append(scores)
listScores = np.array(listScores)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itérations")
plt.ylabel("Score")
plt.show()
Notre suite $(x_n)_{n\in \mathbb{N}}$ semble donc converger vers notre vecteur de score.
Notons que cela ne dépend pas du vecteur initial :
M = np.array(nx.adjacency_matrix(G).todense())
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
n = G.number_of_nodes()
scores = np.array([0.2,0,0.2,0.6])
listScores = [scores]
for _ in range(10):
scores = scores @ M
listScores.append(scores)
listScores = np.array(listScores)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itérations")
plt.ylabel("Score")
plt.show()
Le vecteur trouvé est bien le même
Le problème de cette méthode est qu'elle ne marche pas toujours comme par exemple dans le cas suivant :
G = nx.DiGraph()
[G.add_node(k) for k in [0,1,2,3]]
G.add_edges_from([(0,1), (0,2), (1,2),
(1,3), (2,3)])
pos = nx.circular_layout(G)
color_map = list(nx.pagerank(G).values())
nx.draw(G,
pos=pos,
width=2.0,
node_color = 'lightsteelblue',
node_size = 2500,
with_labels = True)
plt.show()
G.add_edges_from([(3,3)])
M = np.array(nx.adjacency_matrix(G).todense())
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
n = G.number_of_nodes()
scores = np.ones(n) / n
listScores = [scores]
for _ in range(5):
scores = scores @ M
listScores.append(scores)
listScores = np.array(listScores)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itérations")
plt.ylabel("Score")
plt.show()
Pour obtenir ce graphe, nous avons rajouté un lien allant de 3 vers lui-même afin de représenter le fait que les utilisateurs se retrouvent bloqués sur cette page et ainsi mettre en évidence un résultat aberrant.
Le résultat trouvé possède bien les propriétés du vecteur score mais il représente très mal la réalité.
Le problème est évidemment lié au fait que 3 ne renvoie vers rien et viens donc absorber tous les utilisateur rendant impossible un classement juste des différentes pages.
Regardons maintenant mathématiquement quel est le problème en enlevant ce lien de 3 vers lui même :
G.remove_edges_from([(3,3)])
M = np.array(nx.adjacency_matrix(G).todense())
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
n = G.number_of_nodes()
scores = np.ones(n) / n
listScores = [scores]
for _ in range(5):
scores = scores @ M
listScores.append(scores)
listScores = np.array(listScores)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itérations")
plt.ylabel("Score")
plt.show()
La solution de ce problème est le vecteur nul qui ne peut-être vecteur propre d'aucune valeur propre. De plus, la somme des coefficients du vecteur nul n'est évidemment pas égale à 1, nous avons donc un gros problème.
Voyons maintenant un deuxième cas problématique :
G = nx.DiGraph()
[G.add_node(k) for k in [1,2,3,4,5]]
G.add_edges_from([(1,2), (2,1), (3,4),
(4,3), (5,3), (5,4), (3,5)])
pos = nx.circular_layout(G)
color_map = list(nx.pagerank(G).values())
nx.draw(G,
pos=pos,
width=2.0,
connectionstyle = 'arc3, rad = 0.1',
node_color = 'lightsteelblue',
node_size = 2500,
with_labels = True)
plt.show()
M = np.array(nx.adjacency_matrix(G).todense())
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
n = G.number_of_nodes()
scores = np.ones(n) / n
listScores = [scores]
for _ in range(10):
scores = scores @ M
listScores.append(scores)
listScores = np.array(listScores)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itérations")
plt.ylabel("Score")
plt.show()
Le problème ici n'est pas que notre vecteur de score est faux, c'est qu'il n'est pas unique.
En changeant la condition de départ, on voit que l'algorithme ne converge plus du tout :
M = np.array(nx.adjacency_matrix(G).todense())
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
n = G.number_of_nodes()
scores = np.array([0.2,0.4,0,0.2,0])
listScores = [scores]
for _ in range(10):
scores = scores @ M
listScores.append(scores)
listScores = np.array(listScores)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itérations")
plt.ylabel("Score")
plt.show()
Dans notre premier cas, notre chaîne possède deux propriétés qui permettent de prouver l'existence et l'unicité de notre limite.
En effet nous avions une chaîne qui était irréductible et apériodique.
Elle représente le fait qu'en partant de n'importe quel état, on peut arriver à n'importe quel autre état. Losque l'on se place dans un réseau avec des noeuds pendants (des pages qui ne renvoient vers aucune autre), nous perdons cette propriété.
Elle représente le fait qu'il n'existe pas un état qui se reproduit de manière périodique. Cette propriété n'est donc pas vérifiée dans l'exemple des sous-webs.
Voyons maintenant cela avec le Théorème de Perron-Frobénius :
Soit $M$ une matrice primitive. Alors elle admet une valeur propre réelle $r > 0$ telle que :
Dans notre cas, $M$ est une matrice de transition d'une chaîne de Markov. Elle est donc stochastique ce qui signifie que la somme des éléments de chaque ligne ou colonne vaut 1.
Cela nous donne donc $$||M||_\infty \leq 1$$ puisque tous les éléments de $M$ sont positifs et ils ne peuvent éxceder 1 puisque la somme sur les lignes ou les colonnes doit valoir 1.
Nous avons de plus la propriété suivante : $$ \rho (M) \leq ||M||$$ avec $\rho (M)$ le rayon spectral de $M$ c'est-à-dire sa valeur propre dominante.
Ce qui nous donne en choisissant la norme infinie $$ \rho (M) \leq 1 $$
Supposons $M$ ligne-stochastique de taille $n \times n$ et $x$ un vecteur rempli de 1.
Alors $Mx = x$ donc $M$ admet 1 comme valeur propre.
Le même raisonnement se fait avec une matrice colonne-stochastique :
$M^Tx = x$ donc $M^T$ admet 1 comme valeur propre donc $M$ aussi.
Cela nous donne donc $$1 \leq \rho (M) \leq 1 $$
puisque $\rho (M)$ est la plus grande valeur propre de $M$
d'où $$\rho (M) = 1$$
En choisisant la norme 1 pour notre vecteur de Perron-Frobénius, on obtient un vecteur dont la somme des coefficients (tous positifs) vaut 1.
Nous avons donc trouvé le vecteur score que nous voulions et qui a toutes les propriétés souhaitées :
Cependant une matrice stochastique n'est pas forcément primitive, et c'est cela qui provoque les deux problèmes vus précedemment. Cela signifie qu'une chaîne de Markov n'est pas forcément irréductible.
C'est pour cela que si notre chaîne n'est pas irréductible, l'existence et l'unicité de la limite ne sont pas garanties. C'est le cas dans nos deux exemples problématiques.
Voyons maintenant comment transformer notre chaîne de Markov en une chaîne irréductible.
Pour cela il faut pouvoir atteindre n'importe quel état quelque soit notre point de départ.
Supposons que l'utilisateur clique sur un lien disponible sur sa page avec une probabilité $\alpha$ ou qu'il aille sur une autre page de façon aléatoire avec une probabilité $(1 - \alpha)$.
Cela rend atteignable n'importe qu'elle page quelque soit le point de départ. De plus, cela est plus fidèle au comportement d'un utilisateur.
Nous choisirons la loi de probabilité uniforme pour la nouvelle page choisie.
Notons $M$ notre matrice de transition de taille $n \times n$ et $R$ de taille $n \times n$ la matrice qui représente le choix d'une nouvelle page de façon uniforme.
Notre nouvelle matrice de transition est donc la suivante : $$ G = \alpha M + (1-\alpha)R$$
Les matrices $M$ et $R$ sont stochastiques ($R$ est même bistochastique)
Ce qui nous donne donc la fonction suivante :
def rapportScoreIteration(G, alpha=0.85, trace=True, iter=100, epsilon=1.0e-6):
n = G.number_of_nodes()
s = np.ones(n) / n
listScores = [s]
M = (1 - alpha) * np.array(nx.adjacency_matrix(G).todense()) + alpha*s
M = np.array([line/np.sum(line) if np.sum(line) > 0 else np.zeros(len(line)) for line in M])
print(np.linalg.eigh(M))
for _ in range(iter):
listScores.append((1 - alpha)*listScores[-1] @ M + alpha*s)
diff = np.linalg.norm(np.array(listScores[-1]) - listScores[-2])
if (diff < epsilon) : break # si le nouveau score est à peine différend de l'ancien
listScores = np.array(listScores)
if trace :
print("Matrice de transition M:\n",M)
plt.figure()
plt.plot(listScores)
plt.legend(G.nodes)
plt.xlabel("Itération")
plt.ylabel("Score")
plt.show()
print("Liste finale des scores :\n", listScores[-1])
return listScores
La matrice $G$ est donc également stochastique (ligne-stochastique si $M$ est ligne-stochastique et colonne-stochastique si $M$ est colonne-stochastique).
Nous avons donc maintenant une matrice primitive c'est-à-dire une matrice dont tous les coefficients sont strictement positifs à une certaine puissance de $G$.
Ici, la propriété est vérifiée à la puissance 1
Les hypothèses du théorème de Perron-Frobénius sont donc vérifiées et comme $G$ est stochastique, notre vecteur de Perron-Frobénius est notre vecteur de score.
Exemple :
G = nx.DiGraph()
[G.add_node(k) for k in [1,2,3,4,5,6]]
G.add_edges_from([(1,2), (2,1), (3,4),
(4,3), (5,3), (5,4),
(3,5), (6,1), (5,6),
(3,5), (6,2),(5,2)])
pos = nx.circular_layout(G)
color_map = list(nx.pagerank(G).values())
nx.draw(G,
pos=pos,
width=2.0,
connectionstyle = 'arc3, rad = 0.1',
node_color = 'lightsteelblue',
node_size = 2500,
with_labels = True)
plt.show()
print("Paramètre alpha = 0.15.")
_ = rapportScoreIteration(G, alpha=0.15)
print("Paramètre alpha = 0.85.")
_ = rapportScoreIteration(G, alpha=0.85)
Paramètre alpha = 0.15.
(array([-0.88569114, -0.85586527, -0.36218247, -0.07785137, 0.98597442,
1.3046851 ]), array([[ 6.72177084e-01, 1.95890506e-02, 3.91871947e-01,
1.19497695e-01, -2.05684124e-01, 5.81072246e-01],
[-7.09599342e-01, -6.71116459e-03, 2.82985229e-01,
-1.56870643e-01, -1.69523055e-01, 6.02492016e-01],
[-4.08921729e-02, 7.09076190e-01, 3.38781906e-02,
2.21733178e-01, 6.41903298e-01, 1.82169178e-01],
[-1.56882210e-02, -7.04791889e-01, 5.05665600e-02,
2.24475722e-01, 6.43571840e-01, 1.89449814e-01],
[ 2.05971706e-01, 6.44253251e-04, -2.21840963e-01,
-8.91248098e-01, 2.77279208e-01, 1.92756053e-01],
[ 1.74386499e-02, -7.08263677e-03, -8.44652364e-01,
2.59294769e-01, -1.60772070e-01, 4.39461805e-01]]))
Matrice de transition M:
[[0.025 0.875 0.025 0.025 0.025 0.025 ]
[0.875 0.025 0.025 0.025 0.025 0.025 ]
[0.01351351 0.01351351 0.01351351 0.47297297 0.47297297 0.01351351]
[0.025 0.025 0.875 0.025 0.025 0.025 ]
[0.00704225 0.24647887 0.24647887 0.24647887 0.00704225 0.24647887]
[0.47297297 0.47297297 0.01351351 0.01351351 0.01351351 0.01351351]]
Liste finale des scores :
[0.2739873 0.28603359 0.15199022 0.12269873 0.10194979 0.06334038]
Paramètre alpha = 0.85.
(array([-0.18907611, -0.16144831, -0.11113281, -0.03460718, 0.23539212,
1.02995026]), array([[-0.52892704, 0.18733033, 0.46051989, -0.33485277, 0.42581874,
-0.42381244],
[ 0.68017594, -0.02168912, 0.2964392 , 0.34392197, 0.35040948,
-0.45600982],
[ 0.21327422, 0.68363947, -0.13000752, -0.2742117 , -0.49560784,
-0.38656182],
[ 0.04089899, -0.68715103, 0.16805817, -0.31666991, -0.48215304,
-0.40639365],
[-0.45672137, 0.02313155, -0.06164777, 0.75714871, -0.28093398,
-0.36724923],
[-0.04294001, -0.15608459, -0.80690723, -0.14437882, 0.37265132,
-0.40370809]]))
Matrice de transition M:
[[0.14166667 0.29166667 0.14166667 0.14166667 0.14166667 0.14166667]
[0.29166667 0.14166667 0.14166667 0.14166667 0.14166667 0.14166667]
[0.12318841 0.12318841 0.12318841 0.25362319 0.25362319 0.12318841]
[0.14166667 0.14166667 0.29166667 0.14166667 0.14166667 0.14166667]
[0.09770115 0.20114943 0.20114943 0.20114943 0.09770115 0.20114943]
[0.25362319 0.25362319 0.12318841 0.12318841 0.12318841 0.12318841]]
Liste finale des scores : [0.16795048 0.17044218 0.16721664 0.16673669 0.16418894 0.16346506]
On remarque que plus le paramètre $\alpha$ est grand, plus l'algorithme converge vite. Cependant, la valeur des scores est moins atténuée. La valeur la plus courante pour $\alpha$ est 0.85 par le biais de plusieurs études.
def pageRank(G, alpha=0.85, iter=1000, epsilon=1.0e-6): #retourne les rangs d'un réseau G de networkx
n = G.number_of_nodes()
scores = np.ones(n) / n #initialisation des scores
for _ in range(iter):
newScores = list()
for page in G.nodes(): # pour chaque page du réseau
ins = np.array(list(G.in_edges(page))) # liste des pages qui redirigent vers notre page
if len(ins) > 0: ins = ins[:,0]
sum = np.sum([scores[k]/len(G.out_edges(k)) for k in ins])
newScores.append((1 - alpha)/n + alpha*sum) # calcul du nouveau score
diff = np.linalg.norm(np.array(newScores) - scores)
if (diff < epsilon) : return newScores # si le nouveau score est à peine différend de l'ancien
scores = newScores
return scores
def dessineGraphe(G):
pr = pageRank(G)
nx.draw(G,
node_color = pr,
cmap = cm.get_cmap("Oranges"),
pos = nx.spring_layout(G),
connectionstyle = 'arc3, rad = 0.2',
node_size = [v * 20000 for v in pr],
with_labels = True)
plt.show()
nbrOfNodes = 10
nbrOfConnection = 15
G = nx.gnm_random_graph(nbrOfNodes,nbrOfConnection,directed = True)
print(pageRank(G))
dessineGraphe(G)
[0.027378929910343658, 0.03323944469167414, 0.08586489786232072, 0.058087156502110396, 0.06437424826338287, 0.05799730451236146, 0.02912681415860347, 0.044875512771851186, 0.08337005914950481, 0.02912681415860347]
nbrOfNodes = 10
nbrOfConnection = 17
G = nx.gnm_random_graph(nbrOfNodes,nbrOfConnection,directed = True)
print(pageRank(G))
dessineGraphe(G)
[0.015000000000000003, 0.2529323830299598, 0.2363672070792285, 0.015000000000000003, 0.08683441443851889, 0.08451107581002223, 0.024460666437650297, 0.22537346996861896, 0.015000000000000003, 0.04452078323600138]
nbrOfNodes = 30
nbrOfConnection = 50
G = nx.gnm_random_graph(nbrOfNodes,nbrOfConnection,directed = True)
dessineGraphe(G)
"Le théorème de Perron-Frobenius, les chaines
de Markov et un célèbre moteur de recherche" par Bachir Bekka, Février 2007 :
https://agreg-maths.univ-rennes1.fr/documentation/docs/Perron-Frobenius.pdf
"THE $25,000,000,000∗ EIGENVECTOR, THE LINEAR ALGEBRA BEHIND GOOGLE" par Kurt Bryan et Tanya Leise :
https://www.math.arizona.edu/~glickenstein/math443f08/bryanleise.pdf
"L’algorithme PageRank de Google" par Frédéric Paccaut :
https://contrib.eduscol.education.fr/educnet/maths/animation/interlocuteurs/documents/2013-2014/google-paccaut-140127.pdf
"Chaînes de Markov" :
https://www.imo.universite-paris-saclay.fr/~pierre-loic.meliot/agreg/markov.pdf
"Matrices stochastiques et théorèmes de Perron-Frobenius" :
http://www.i2m.univ-amu.fr/~priziac.f/cma-CM15.pdf
"NORMES ET CONDITIONNEMENT D’UNE MATRICE" par R. Herbi, 15 septembre 2015 :
https://www.i2m.univ-amu.fr/perso/thierry.gallouet/licence.d/anum.d/anum-tg2.pdf
"Google's PageRank Algorithm" :
https://youtube.com/playlist?list=PLH7W8KdUX6P2n4XwDiKsEU6sBhQj5cAqa
"PageRank" :
https://youtu.be/GLsodToSO4I
"PageRank: A Trillion Dollar Algorithm" :
https://youtu.be/JGQe4kiPnrU