{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Le page rank de Google\n",
    "\n",
    "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.\n",
    "<ul>\n",
    "<li> Pour une page $k$, notons $\\{i_1, i_2, \\dots, i_p \\}$ les pages ayant un lien vers la page $k$.</li> \n",
    "<li>  Notons $N(i)$ le nombre de liens partant de la page $i$.</li> \n",
    "<li>  La popularité de la page $k$ est donnée par la formule :\n",
    "$$pr(k) = \\sum_{i \\in \\{i_1, i_2, \\dots, i_p \\} }\\frac{pr(i)}{N(i)}$$</li> \n",
    "</ul>\n",
    "\n",
    "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$\n",
    "\n",
    "Pour obtenir une approximation de $pr(k)$, on construit une suite $pr_n(k)$ comme suit :\n",
    "\n",
    "<ul>\n",
    "<li> on  initialise $pr_0(k)=1$ pour tous les $k$ , </li> \n",
    "<li> on calcule $pr_{n+1}(k)$ par la formule\n",
    "$$pr_{n+1}(k) = \\sum_{i \\in \\{i_1, i_2, \\dots, i_p \\} }\\frac{pr_n(i)}{N(i)}$$</li> \n",
    "</ul>\n",
    "\n",
    "On admet que la suite $(pr_n (k))_n$ tend vers $pr(k)$ lorsque $n$ tend vers l’infini.\n",
    "\n",
    "<br>\n",
    "<br>\n",
    "\n",
    "Exemple. Voici une liste de pages numérotées de 0 à 9 ainsi que les liens présents sur cette page.\n",
    "\n",
    "page 0 : $[1, 2, 3]$\n",
    "\n",
    "page 1 : $[2, 3, 4]$\n",
    "\n",
    "page 2 : $[3, 4]$\n",
    "\n",
    "page 3 : $[1, 5, 7, 9]$\n",
    "\n",
    "page 4 : $[0]$\n",
    "\n",
    "page 5 : $[1, 3, 7, 9]$\n",
    "\n",
    "page 6 : $[4, 8]$\n",
    "\n",
    "page 7 : $[1, 3, 5, 9]$\n",
    "\n",
    "page 8 : $[0, 9]$\n",
    "\n",
    "page 9 : $[6, 7, 8]$\n",
    "\n",
    "\n",
    "<ul>\n",
    "<li> La page 5 a des liens vers les pages 1, 3, 7, 9. Ainsi $N(5) = 4$.</li> \n",
    "<li> On cherche dans le tableau les pages citant la page 5, à savoir les pages 3 et 7.</li> \n",
    "<li> A l'initialisation, on a $p_0(0) = 1$,  $p_0(1) = 1$, \\dots </li> \n",
    "<li> On calcule alors\n",
    "$$p_1(5) = \\frac{p_0 (3)}{N(3)} + \\frac{p_0 (7)}{N(7)} = \\frac{1}{4} + \\frac{1}{4} = \\frac{1}{2}$$</li> \n",
    "</ul>\n",
    "\n",
    "Quelles sont les trois pages ayant le *page rank* le plus élevé ? Effectuer  suffisamment d'itérations ! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithme : page Rank\n",
    "\n",
    "Rôle : calculer la popularité des pages web\n",
    "\n",
    "**Entrées** : \n",
    "\n",
    "**Sorties** : \n",
    "\n",
    "**Variables** : \t\n",
    "\n",
    "**Constantes** : \t\n",
    "\n",
    "**Début**\n",
    "\t\n",
    "$\\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]]\n",
    "    \n",
    "$\\qquad$Pour i de 0 à 9:\n",
    "    \n",
    "$\\qquad$$\\qquad$N[i] $\\leftarrow$ longueur(L[I])\n",
    "        \n",
    "        \n",
    "$\\qquad$nombre_iterations $\\leftarrow$ 10\n",
    "    \n",
    "    \n",
    "    \n",
    "$\\qquad$P0 = [1, ..., 1]\n",
    "    \n",
    "$\\qquad$Pour j de 0 à nombre_iterations:\n",
    "    \n",
    "$\\qquad$$\\qquad$ P1 = [0,0,....0]\n",
    "        \n",
    " $\\qquad$$\\qquad$Pour i de 0 à 9 :\n",
    "        \n",
    "$\\qquad$$\\qquad$$\\qquad$Pour k de 0 à 9:\n",
    "            \n",
    "$\\qquad$$\\qquad$$\\qquad$$\\qquad$Si i dans L[k], alors :\n",
    "\n",
    "$\\qquad$$\\qquad$$\\qquad$$\\qquad$$\\qquad$P1[i] $\\leftarrow$ P1[i] + $\\dfrac{\\text{P0}[k]}{\\text{N[k]}}$\n",
    "                   \n",
    "$\\qquad$$\\qquad$$\\qquad$$\\qquad$Finsi\n",
    "                \n",
    "$\\qquad$$\\qquad$$\\qquad$Finpour\n",
    "            \n",
    "$\\qquad$$\\qquad$Finpour\n",
    "        \n",
    "$\\qquad$$\\qquad$P0 $\\leftarrow$ P1\n",
    "        \n",
    "$\\qquad$$\\qquad$afficher P1\n",
    "        \n",
    "$\\qquad$Finpour\n",
    "    \n",
    "\t\n",
    "**Fin**\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}