Tp_PageRank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Modélisation de l’algorithme d’un moteur de recherche évaluant la popularité d’un site : le PageRank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Google a cherché un modèle de hiérarchisation qui soit exploitable dans tous les domaines, utilisable pour tous les mots clés, adaptable a un très grand nombre de données, même évolutives, tout en étant automatisable et suffisamment efficace.\n",
    "C’est en répondant à ce cahier des charges que ce nouveau venu a réussi l’exploit, en quelques mois et malgré l’émergence de Bing ou encore Qwant, à obtenir le quasi-monopole de la rechercher thématique sur le web.\n",
    "L’idée à la base du modèle de Larry Page et Sergey Brin, fondateurs de Google, revient à attribuer à chaque page un nombre positif entre 0 et 1, appelé score (en anglais ”PageRank”) de la page, qui caractérisera la pertinence de cette page. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Le principe du surfeur aléatoire\n",
    "#### Après avoir fait la liste (sans classement) de tous les sites traitant la requête, le surfeur aléatoire en choisit au hasard un. Puis il s’intéresse aux liens hypertexte du site sur lequel il se trouve vers les autres sites qu’il a listé. Il en choisit alors un au hasard et répète cette opération sans s’arrêter en comptant pour chacun des sites combien de fois il l’a visité. Les sites sont alors affichés dans l’ordre décroissant de leur nombre de visites.\n",
    "Ainsi pour un certain mot clé rentré, il s’intéresse aux sites qui évoquent ce mot-clé mais également aux liens hypertextes qui permettent de passer d’un site à l’autre.\n",
    "Le problème de l’attribution du score peut être représenté par un graphe orienté : les quatre pages sont représentées par les quatre sommets d’un graphe dont les arêtes orientées représentent les références (liens) pouvant exister entre ces différentes pages.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Activité 1 Compréhension d'un algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://entbtz.fr/teleenseignement/snt/sch1.png\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analysez l’algorithme sous Python permettant de calculer la popularité des sites A, B, et C "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#appel de la bibliothèque random\n",
    "from random import *\n",
    "#définition d'une fonction PR pour PageRank n étant le nombre de tirage effectué\n",
    "def PR(n):\n",
    "    #déclaration de 3 variables nA étant le nombre de fois où le surfeur va passer par A\n",
    "    nA=0;\n",
    "    nB=0;\n",
    "    nC=0;\n",
    "    #choix aléatoire du point d'entrée dans le système et initialisation du surf\n",
    "    start=randint(1,3)\n",
    "    if start==1:\n",
    "        page=\"A\";\n",
    "        nA=1\n",
    "    if start==2:\n",
    "        page=\"B\";\n",
    "        nB=1\n",
    "    if start==3:\n",
    "        page=\"C\";\n",
    "        nB=1\n",
    "    # Pour n lien surfé\n",
    "    for i in range(n):\n",
    "        #si on se situe sur le site A\n",
    "        if page==\"A\":\n",
    "            #déclaration d'une variable alea déterminant aléatoirement la direction à prendre ensuite dans ce cas il n'y a que deux possibilités\n",
    "            alea=randint(1,2)\n",
    "            #la valeur de 1 détermine la direction pour aller vers B, 2 vers C\n",
    "            if alea==1:\n",
    "                page=\"B\"\n",
    "                #incrémentation de nB de 1 \"on est passé une autre fois sur B\"\n",
    "                nB=nB+1\n",
    "            if alea==2:\n",
    "                page=\"C\"\n",
    "                nC=nC+1\n",
    "        #si on se situe sur le site B\n",
    "        if page==\"B\":\n",
    "            #il n'y a ici qu'une seule possibilité c'est d'aller vers A\n",
    "            page=\"A\"\n",
    "            nA=nA+1\n",
    "        #si on se situe sur le site C\n",
    "        if page==\"C\":\n",
    "            #déclaration d'une variable alea déterminant aléatoirement la direction à prendre ensuite dans ce cas il n'y a que deux possibilités\n",
    "            alea=randint(1,2)\n",
    "            #la valeur de 1 détermine la direction pour aller vers A, 2 vers B\n",
    "            if alea==1:\n",
    "                page=\"A\"\n",
    "                nA=nA+1\n",
    "            if alea==2:\n",
    "                page=\"B\"\n",
    "                nB=nB+1\n",
    "    #calcul de la fréquence de passage sur chaque site fA, fB, fC            \n",
    "    fA=nA/(n+1)\n",
    "    fB=nB/(n+1)\n",
    "    fC=nC/(n+1)\n",
    "    #la fonction renvoie les valeurs des trois fréquences\n",
    "    print(\"le Pagerank du site A vaut:\",fA) \n",
    "    print(\"le Pagerank du site B vaut:\",fB) \n",
    "    print(\"le Pagerank du site C vaut:\",fC) \n",
    "#test de la focntion pour 100 tirages\n",
    "PR(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Comment s'appelle la fonction ici étudiée?"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "réponse:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A quoi le code randint(1,3)?"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "réponse:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Que représente fA?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "réponse:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Activité 2 Réaliser un algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://entbtz.fr/teleenseignement/snt/sch2.png\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Réaliser un algorithm permettant de calculer et d'afficher le pagerank des sites A, B, C et D en vous inspirant de l'agorithme étudié plus haut."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Taper votre code ici\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Activité 3 Analyse de cas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span><img src=\"http://entbtz.fr/teleenseignement/snt/r1.jpg\" align=\"left\"><h2>Un premier problème</h2><p>\n",
    "La technique du surfeur aléatoire ne marche pas pour le\n",
    "graphe suivant :<br>\n",
    "Pourquoi ?<br>\n",
    "Proposer une solution pour pallier à ce problème.<br>\n",
    "Faites alors une proposition de classement pour ce graphe après avoir calculé le PageRank.<br>\n",
    "Comparer vos résultats avec les autres groupes.</p></span>"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Ecrire votre réponse ici:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span><img src=\"http://entbtz.fr/teleenseignement/snt/r2.jpg\" align=\"left\"><h2>le puit</h2><p>\n",
    "Evaluer les PageRank du site 4 par rapoort au autres.<br>\n",
    "Quel problème moral est soulevé par ce graphe ?<br>\n",
    "Avez-vous une solution à proposer pour pallier à ce problème ?</p></span>"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Ecrire votre réponse ici:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span><img src=\"http://entbtz.fr/teleenseignement/snt/r3.jpg\" align=\"left\"><h2>la poche web :</h2><p>\n",
    "Estimer les PageRank des sites suivants.<br>\n",
    "Comparer avec les autres groupes.<br>\n",
    "Quel problème est soulevé par ce graphe ?<br>\n",
    "Avez-vous une solution à proposer pour pallier à ce problème ?</p></span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Ecrire votre réponse ici:\n",
    "    "
   ]
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}