{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": true }, "source": [ "

Table of Contents

\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction au fonctionnement de PageRank\n", "\n", "Pour des explications plus précises sur le fonctionnement de l’algorithme de Page Rank de Google, vous pouvez vous référencer aux articles suivant : \n", "\n", "* L'article original de Page et al. : [lien](http://ilpubs.stanford.edu:8090/422/)\n", "* Une explication sous forme d'exercice du fonctionnement de l’algorithme de Page Rank : [lien](https://www.ime.usp.br/~map2121/2014/map2121/programas/google.pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Définition du problème\n", "\n", "**Motivation.** l’algorithme de PageRank initial s'intéresse au problème suivant : imaginons une personne recherchant une information sur le réseau en utilisant uniquement quelques mots clés (\"`Ensimag`\"). Il existe plusieurs milliers de pages contenant ces termes : la question est donc dans quel ordre doit-t-on renvoyer ces résultats." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Plateforme de recherche.** L'idée est de construire une plateforme à 2 niveaux. Le premier niveau est hors ligne c'est-à-dire que sa construction est indépendante de toute les requêtes pouvant être effectuées. La seconde phase dépend elle de la recherche de l'utilisateur.\n", "\n", "La méthode hors ligne pré-calcul un classement pour toutes les pages du web en utilisant uniquement des extractions de celui-ci.\n", "\n", "La méthode en ligne filtre la liste ordonnée et produit une sous-liste ordonnée par rapport au classement global." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Idée principale.** L'algorithme de PageRank est la phase hors-ligne. Étant donné qu'il est irréaliste de s’appuyer sur l'ensemble des pages, il utilise un modèle probabiliste pour simuler le comportement d'un utilisateur sur le web qui ne fera pas de requêtes.\n", "\n", "Supposons qu'il existe $n$ pages, représentées par un l'ensemble des noeuds $V = \\{1, 2, \\ldots, n\\}$. De plus les pages sont liées entre elles. On notera donc $E$ l'ensemble des arêtes, c'est-à-dire les paires $(i,j)$ indiquant que la page $i$ pointe vers la page $j$. \n", "Nous avons donc une représentation sous forme de graphe orienté.\n", "\n", "Soit un utilisateur quelconque visitant les pages du graphe par une marche aléatoire, c'est-à-dire qu'il ne peut visiter qu'une seule page à la fois et qu'elle est choisie de manière aléatoire dans la liste des pages atteignable.\n", "\n", "1. A chaque instant $t \\geq 0$, l'utilisateur visite une page. Le choix de la page à l'instant $t+1$ dépends uniquement de la page visitée à l'instant $t$.\n", "2. A $t=0$, l'utilisateur commence sur une page aléatoire.\n", "3. On suppose que l'utilisateur se trouve sur la page $i$ à l'instant $t$. L'utilisateur choisira de suivre le lien de $i$ vers $j$ avec la probabilité $\\alpha$.\n", "4. A l'instant $t$, l'utilisateur peut également décider de se rendre sur une page $j$ avec la probabilité $1-\\alpha$, la page $i$ n'ayant pas forcément de lien vers la page $j$.\n", "\n", "En laissant l'utilisateur naviguer suffisamment longtemps sur le réseau, il peut éventuellement parcourir plusieurs fois les mêmes pages, rester dans une zone spécifique du réseau au se rendre de manière aléatoire dans une autre zone du réseau.\n", "La question que nous cherchons à résoudre est quelle est la probabilité de se trouver sur une certaine page au bout d'un temps infiniment long.\n", "Si la distribution de probabilité peut-être calculée, alors l'algorithme de PageRank doit nous permettre d'identifier sur quelle page l'utilisateur est le plus susceptible de se rendre." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous voulons pondérer les liens depuis différentes pages de deux manières :\n", "1. Les pages qui dirigent vers $i$ et possèdent un rang élevé doivent avoir un poids plus élevé.\n", "2. Les pages qui dirigent vers $i$ et possèdent de nombreux liens en général doivent un poids plus faible." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quelques aspects mathématiques\n", "\n", "Nous allons maintenant reformuler le comportement d'un utilisateur sous la forme d'un problème d'algèbre linéaire." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Matrice d'adjacence.** La première étape consiste à représenter le graphe sous forme d'une matrice $A \\equiv (g_{ij})$, avec le coefficient $(i, j)$ , $a_{ij}$, vaut $1$ si il existe un lien $i \\rightarrow j$, et $0$ autrement." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Matrice de masse.** La seconde matrice d'intérêt s'appelle la matrice de masse, c'est-à-dire le poids relatif de chacune des pages. Elle est diagonale et on la note $M$, avec $m_{ii} = m_i = \\sum_{k=1}^n a_{ki}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Vecteur d'état.** Soit $x(t)$ un vecteur représentant les probabilités d'un utilisateur de se rendre sur une page à chaque instant $t$. On a \n", "\n", "$$x(t) \\equiv \\left(\\begin{array}{c} x_1(t) \\\\ x_2(t) \\\\ \\vdots \\\\ x_n(t) \\end{array}\\right),$$\n", "\n", "avec $x_i(t)$ la probabilité que l'utilisateur se trouve sur la page $i$ à l'instant $t$. L'utilisateur étant toujours présent sur une page, nous avons: $\\sum_{i=1}^{n} x_i(t) = 1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Navigation__\n", "A $t=0$, on suppose que l'utilisateur se trouve de façon équiprobable sur n'importe quelle page. Alors, $x_i(0) = \\frac{1}{n}$.\n", "\n", "On fait ensuite l'hypothèse que l'utilisateur se trouve sur la page $i$ à l'instant $t$. Quelle page sera visitée à l'instant $t+1$? Nous allons examiner les deux scénarios possible.\n", "\n", "### Scenario 1\n", "L'utilisateur décide de suivre un lien depuis la page $i$. Quel est le lien qui sera choisi?\n", "\n", "Si on suppose que le choix est uniforme parmi les liens possible, alors la probabilité de choisir un lien est $\\frac{1}{d_i}$ avec $d_i$ le nombre de liens sortant du noeud $i$. $d_i$ s'appelle le degré du noeud $i$.\n", "\n", "Ainsi, la probabilité de se rendre sur une page $j$ depuis la page $i$ s'écrit\n", "$p_{ij} = \\frac{a_{ij}}{m_i}$. \n", "\n", "Si la page $i$ n'a pas de lien sortant, un modèle consiste à dire que la le seul lien possible est avec la page $i$ est avec elle même, ce qui induit une probabilité $p_{ii} = 1$.\n", "\n", "La probabilité de se rendre sur la page $i$ est donc\n", "\\begin{align*}\n", "p_i = \\sum_{j\\to i} p_{ij} = \\sum_{j\\to i} \\dfrac{p_j}{m_j} = \\sum_{j=1}^n \\dfrac{a_{ij}}{m_j}p_j.\n", "\\end{align*}\n", "\n", "\n", "Cette définition correspond à ce qui est attendu.\n", "\n", "Étant donné tous les coefficients de $a_{ij}$, en incluant les auto-référencement, nous obtenons les expressions suivantes :\n", "\n", "\\begin{align*}\n", " p = A M^{-1} p.\n", "\\end{align*}\n", "\n", "Nous avons donc que $p$ est vecteur propre de la matrice $AM^{-1}$ associé à la valeur propre $1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Est-ce que 1 est toujours valeur propre ?__\n", "Afin de répondre à cette question, nous allons utilisé les chaîne de Markov. On considère la chaîne de Markov comme un processus aléatoire qui permet de passer d'un état à un autre." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Une chaîne de Markov possède une matrice de transition $P = P_{ij}$ qui permet d'aller de $i$ vers $j$. Après une itération, le vecteur initial $x(0)$ devient $x(1) = P^T x(0)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On considère la chaîne de Markov associé au parcours de page web avec la matrice de transition $P = (A M^{-1})$.\n", "\n", "D'après la définition, on a ainsi que la somme de chaque ligne de la matrice $P = (p_{ij})$ vaut $1$.\n", "\n", "On appelle distribution stationnaire d'une chaîne de Markov un vecteur de probabilité $p$ tel que $p = P p$, c'est-à-dire un vecteur qui reste inchangé par la chaîne de Markov.\n", "\n", "Si la chaîne de Markov est fortement connectée, c'est-à-dire que tous les états peuvent être depuis n'importe quel autre état, alors la distribution stationnaire $p$ existe et est unique. \n", "\n", "De plus, la distribution stationnaire est la proportion de visite que chaque état reçoit dans la chaîne de Markov après un temps très long :\n", "\n", "\\begin{equation}\n", "p_i = \\lim_{t \\to \\infty} \\dfrac{{nombre\\; de\\; visites}}{t}.\n", "\\end{equation}\n", "\n", "Ou encore, le nombre de fois que nous visitons une page si nous restons de manière infinie sur le réseau." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exemples__\n", "On considère le graph orienté complet de 4 noeuds. La matrice d’adjacence est\n", "\\begin{align}\n", "A = \\begin{bmatrix}\n", "1 & 1& 1& 1\\\\\n", "1 & 1& 1& 1\\\\\n", "1 & 1& 1& 1\\\\\n", "1 & 1& 1& 1\n", "\\end{bmatrix}\n", "\\end{align}\n", "\n", "La matrice de masse s'écrit\n", "\\begin{align}\n", "M = \\begin{bmatrix}\n", "4 & 0& 0& 0\\\\\n", "0 & 4& 0& 0\\\\\n", "0 & 0& 4& 0\\\\\n", "0 & 0& 0& 4\n", "\\end{bmatrix}\n", "\\end{align}\n", "\n", "On obtient donc la matrice de passage $P$\n", "\\begin{align}\n", "P = \\dfrac{1}{4}\\begin{bmatrix}\n", "1 & 1& 1& 1\\\\\n", "1 & 1& 1& 1\\\\\n", "1 & 1& 1& 1\\\\\n", "1 & 1& 1& 1\n", "\\end{bmatrix}\n", "\\end{align}\n", "On obtient les valeurs propres $1$ avec la multiplicité $0$ et $0$ avec la multiplicité $1$. Le vecteur propre associé à $1$ est $p = (1, 1, 1 ,1)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__\n", "1. Soit le graph ayant de 5 noeuds bi-partites cycliques de 3 composantes connectées et 2 composantes connectées.\n", "La matrice d’adjacence est\n", "\\begin{align}\n", "A = \\begin{bmatrix}\n", "0 & 0 & 1 & 0 & 0 \\\\\n", "1 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & 1 & 0\n", "\\end{bmatrix}\n", "\\end{align}\n", "\n", "La matrice de masse s'écrit\n", "\\begin{align}\n", "M = \\begin{bmatrix}\n", "1 & 0 & 0 & 0 & 0\\\\\n", "0 & 1 & 0 & 0 & 0\\\\\n", "0 & 0 & 1 & 0 & 0\\\\\n", "0 & 0 & 0 & 1 & 0\\\\\n", "0 & 0 & 0 & 0 & 1 \n", "\\end{bmatrix}\n", "\\end{align}\n", "\n", "On obtient donc la matrice de passage $P$\n", "\\begin{align}\n", "P = \\begin{bmatrix}\n", "0 & 0 & 1 & 0 & 0 \\\\\n", "1 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & 1 & 0\n", "\\end{bmatrix}\n", "\\end{align}\n", "\n", "Les vecteurs propres de $A$ associés à la valeur propre $1$ sont $p_1 = (1,1,1,0,0)$ et $p_2=(0,0,0,1,1)$.\n", "Les classements proposés par cette matrice sont complètement opposés.\n", "\n", "Nous devons donc considérer un autre scénario." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Scenario 2.\n", "Si l'utilisateur choisit de naviguer aléatoirement, on peut supposer un saut aléatoire entre chacune des pages. La probabilité de choisir une page $j$ depuis une page $i$ est donc $\\frac{1}{n}$.\n", "\n", "La représentation matricielle de ce scénario conduit à une matrice uniforme composée uniquement des éléments $\\dfrac{1}{n}$. Il ne prend pas en compte les liens entre les pages. Il considère simplement l'existence ou on d'une page. Il est modélisé par un graphe orienté complet.\n", "\n", "Le principal défaut, c'est que cette matrice ne propose par d’ordonnancement des pages, mais quelque soit la structure du réseau, il y aura toujours une unique solution. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Construction du modèle\n", "Nous avons donc deux scenarii : \n", "1. le _scenario 1_ qui prends en compte la structure du réseau, mais qui ne permet pas toujours d'obtenir unicité de la solution.\n", "2. le _scenario 2_ qui ne prends pas en compte la structure du réseau, mais qui propose toujours une unique solution.\n", "\n", "\n", "\n", "Pour calculer la probabilité de se rendre sur une page $i$ à partir d'une page $j$, nous allons donc combiner ces deux scenarii en pondérant le poids de chaque des scenarii par un paramètre $0<\\alpha <1$.\n", "\n", "$$x_i(t+1) = \\left[\\alpha \\cdot \\sum_{j=1}^{n} p_{ji} x_j(t)\\right] + \\left[(1-\\alpha) \\cdot \\frac{1}{n}\\right].$$\n", "\n", "ou, sous forme matricielle\n", "\n", "$$x(t+1) = \\alpha P^T x(t) + \\frac{1 - \\alpha}{n} u.$$\n", "\n", "En utilisant la définition de $P$, $P^T = A^T D^{-1}$, on a \n", "\n", "$$\n", "x(t+1) = \\alpha A^T M^{-1} x(t) + \\frac{1 - \\alpha}{n} u.\n", "$$\n", "\n", "L'algorithme PageRank consiste donc à itérer cette équation jusqu'à stabilisation de la solution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La chaîne de Markov correspondante se décrit par\n", "\\begin{align*}\n", "p_{ij} = \\begin{cases}\n", "\\dfrac{(1-\\alpha)}{n} + \\dfrac{\\alpha}{m_i} &\\; si\\; i\\to j\\\\\n", "\\dfrac{1-\\alpha}{n} &\\; autrement\n", "\\end{cases}\n", "\\end{align*}\n", "\n", "Autrement dit, la chaîne se déplace vers une page liée avec la probabilité $\\dfrac{(1-\\alpha)}{n} + \\dfrac{\\alpha}{m_i}$ et vers une page non liée avec la probabilité $\\dfrac{(1-\\alpha)}{n}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut vérifier que la chaîne de Markov est fortement connectée, en vérifiant que la matrice de transition $P = (p_{ij})$ est stochastique. Ce qui signifie que la chaîne est fortement connectée et donc que $1$ est valeur propre." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exemple__\n", "Appliquer l'algorithme pour modifié pour le réseau du second exercice." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Convergence de l'algorithme\n", "\n", "Est-ce qu'il y a nécessairement stabilisation de la solution?\n", "\n", "La formule de passage de $x(t+1)$ à $x(t)$ peut s'écrire \n", "\n", "$$x(t+1) = \\hat{G} x(t),$$\n", "\n", "avec\n", "\n", "$$\\hat{G} \\equiv \\alpha P^T + \\frac{1-\\alpha}{n} uu^T.$$\n", "\n", "La stabilisation de la solution revient donc à se demander si le problème admet un point fixe, c'est-à-dire si $x = \\hat{G} x$.\n", "\n", "Comme $P^T$, la matrice $\\hat{G}$ possède les propriétés suivantes:\n", "\n", "* Tous les coefficients sont compris entre $0$ et $1$.\n", "* La somme de chaque colonne vaut $1$.\n", "\n", "En appliquant le théorème de Perron-Frobenius, on conclut que $x = \\hat{G} x$ admet une unique solution non nulle à un facteur multiplicatif prêt. Cette solution est le vecteur propre associée à la valeur propre $1$ de la matrice $\\hat{G}$." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.12" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": true, "autocomplete": false, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": true, "user_envs_cfg": false }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": true, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 1 }