{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "da51a270",
   "metadata": {},
   "source": [
    "# TP - PageRank\n",
    "\n",
    "Le but de cette séance est d’implémenter l’algorithme de puissance itérée \n",
    "pour pouvoir ensuite calculer la centralité de vecteur propre dans le cas \n",
    "des graphes non orientés et également dans le des graphes orientés (Page Rank).\n",
    "Nous utiliserons le module `networkx` de Python.\n",
    " \n",
    "Pour l'ensemble des graphes que nous allons manipuler dans ce TP, il faut \n",
    "que les sommets soient obligatoirement numéroté de $0$ à $n-1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa58658e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "import time\n",
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1899515",
   "metadata": {},
   "source": [
    "## Quelques fonctions utiles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "959dce47",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Return the adjacency matrix of G as list of lists\n",
    "def adjacencyMatrix(G):\n",
    "    return nx.to_numpy_array(G, nodelist=range(len(G))) \n",
    "\n",
    "# Return the matrix product of A and B\n",
    "def multMatrix(A,B):\n",
    "    return A.dot(B)\n",
    "\n",
    "# Return the same graph as G whose vertices are relabeled from 0 to n-1\n",
    "# and the mapping (old:new) names\n",
    "def relabelGraph(G):\n",
    "    mapping = dict(zip(G, range(0, len(G))))\n",
    "    return nx.relabel_nodes(G, mapping), mapping \n",
    "\n",
    "# Return original name of the vertex from new name\n",
    "def getOriginalName(mapping, v):\n",
    "    return [k for k,u in mapping.items() if u == v][0]\n",
    "\n",
    "# Draw the graph G. If a centrality measure is given in C, label the vertices. \n",
    "# Different layouts can be used: neato (default), fdp, patchwork, circo, ... \n",
    "# List of layout : https://graphviz.org/docs/layouts/\n",
    "def drawGraph(G,C=None,prog=\"neato\"):\n",
    "    pos=nx.nx_agraph.pygraphviz_layout(G,prog=prog) # Position of vertices\n",
    "    node_size=[300 for _ in G] # default size of nodes\n",
    "    with_labels=True\n",
    "    if C is not None: # if a centrality measure is given, label the vertices\n",
    "        C = C.round(6)\n",
    "        with_labels=False\n",
    "        labels_nodes = {v:C[v][0] for v in G}\n",
    "        max_C=max(C)[0]\n",
    "        node_size=[math.exp(labels_nodes[v]*7/max_C) for v in labels_nodes] # size the vertices depending on the centrality measure\n",
    "        nx.draw_networkx_labels(G,pos,labels_nodes,font_size=12,font_color=\"black\") # draw labels\n",
    "    nx.draw(G,pos=pos,node_size=node_size,with_labels = with_labels) # draw graph\n",
    "    plt.show() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f09fc42f",
   "metadata": {},
   "source": [
    "## Quelques graphes pour faire des tests\n",
    "\n",
    "1. Un premier exemple de graphe non orienté à 4 sommets :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58fda754",
   "metadata": {},
   "outputs": [],
   "source": [
    "G1=nx.Graph()\n",
    "G1.add_edge(0,1); G1.add_edge(3,0); G1.add_edge(1,2); G1.add_edge(2,0)\n",
    "print(\"Matrice d'adjacence du graphe G1: \\n\", adjacencyMatrix(G1))\n",
    "drawGraph(G1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48036dd4",
   "metadata": {},
   "source": [
    "2. Un deuxième exemple de graphe généré aléatoirement sur le modèle Erdös-Rényi :\n",
    "\n",
    "Rappel : Le graphe aléatoire $G_{n,p}$ construit sur le modèle Erdos-Rényi est un graphe à $n$ sommets dans lequel il existe une arête entre chaque paire de sommets avec une probabilité $p$.\n",
    "\n",
    "Dans l'exemple suivant : $n=20$ et $p=\\frac15$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "486ce256",
   "metadata": {},
   "outputs": [],
   "source": [
    "n=20; p=1/5\n",
    "oriented=False\n",
    "G2 = nx.generators.random_graphs.fast_gnp_random_graph(n,p,directed=oriented)\n",
    "drawGraph(G2,prog=\"neato\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0796d25d",
   "metadata": {},
   "source": [
    "3. Un plus gros graphe : `Gcit`\n",
    "\n",
    "Il s'agit d'un graphe de citations qui contient 27770 sommets et de 352807 arcs. Chaque sommet représente un article scientifique et les arcs représentent les citations : si l'article A cite l'article B, alors il y aura un arc de A vers B."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1470acae",
   "metadata": {},
   "outputs": [],
   "source": [
    "file_name=\"cit-HepTh.txt\"\n",
    "Gcit = nx.DiGraph()\n",
    "with open(file_name, 'r') as data:\n",
    "        for line in data:\n",
    "            p = line.split(\" \")       \n",
    "            Gcit.add_edge(int(p[0]),int(p[1]))\n",
    "Gcit,mappingGcit = relabelGraph(Gcit) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4317f31",
   "metadata": {},
   "source": [
    "# Exercice 1 : Implémentation de l'algorithme de puissance itérée\n",
    "\n",
    "1. Complétez la fonction `powerIteration` ci-dessous. Cette fonction implémente l’algorithme de puissance itérée ; elle prend en paramètre une matrice $A$, un nombre d'itérations maximum et un réel epsilon permettant de décider de l’arrêt. Cette fonction retourne un vecteur-colonne.  \n",
    "  À chaque étape de calcul (y compris à l'étape initiale), faites en sorte que la somme des valeurs du vecteur-colonne soit égale à 1.  \n",
    "  Pour info : un vecteur-colonne peut être obtenu avec `np.ndarray(shape=(n,1))` où $n$ est la taille du vecteur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5bea1d79-34e2-40f2-b5a1-74b773d27a34",
   "metadata": {},
   "outputs": [],
   "source": [
    "def powerIteration(A, max_iterations=100, epsilon=1e-6):\n",
    "    n = A.shape[0] # nombre de lignes de A = nombre de sommets du graphe\n",
    "\n",
    "    # 1. Initialiser un vecteur-colonne C de taille n avec des valeurs uniformes (1/n)\n",
    "    C = # TODO\n",
    "\n",
    "    for i in range(max_iterations):\n",
    "        # 2. Conserver une copie du vecteur C de l'itération précédente.\n",
    "        C_prec = # TODO\n",
    "\n",
    "        # 3. Appliquer une itération de la méthode de la puissance\n",
    "        C = # TODO\n",
    "\n",
    "        # 4. Normaliser le vecteur C pour que la somme de ses composantes soit égale à 1.\n",
    "        # TODO\n",
    "        \n",
    "        # 5. Calculer la différence maximale en valeur absolue entre C et C_prec.\n",
    "        # Si cette différence est inférieure à epsilon, arrêter la boucle.\n",
    "        if # TODO :\n",
    "            return C\n",
    "        \n",
    "    return C"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30cd7b93-5ac9-4fa3-bce1-8d7562980a49",
   "metadata": {},
   "source": [
    "2. *Normalisation* : Pourquoi l'étape de normalisation\n",
    "à **chaque** itération est-elle cruciale ? Que risquerait-il de se\n",
    "passer si on ne normalisait pas, ou seulement à la fin ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b47660d9-dd11-40e6-b167-cd231da1043d",
   "metadata": {},
   "source": [
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0667be0f-51a8-4f23-93be-bfce9ada5b05",
   "metadata": {},
   "source": [
    "3. *Critère d'arrêt* : Vous avez utilisé la plus grande différence en valeur absolue entre les composantes de `C` et `C_prec`. Une autre approche consiste à utiliser la somme des différences.  \n",
    "Selon vous, lequel de ces deux critères est le plus strict ? Justifiez votre réponse."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0da76a34-3bef-4059-a72c-20ff068db376",
   "metadata": {},
   "source": [
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ec1b348-65d3-43c6-a020-0584cb2850d0",
   "metadata": {},
   "source": [
    "4. *Test* : Testez votre fonction sur une matrice simple comme `A =\n",
    "np.array([[0.5, 0.5], [0.5, 0.5]])`. Quel est le vecteur propre\n",
    "attendu ? Votre fonction le trouve-t-elle ?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bdb0961a-1696-44ce-8b14-4e50bbd6254d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29c0292a-3037-4d40-b2ac-bdb6bbb29a4d",
   "metadata": {},
   "source": [
    "# "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cce4400f-a956-442f-a6a8-d4cf9741fcab",
   "metadata": {},
   "source": [
    "# Exercice 2 : Centralité de vecteur propre (cas non orienté)\n",
    "\n",
    "1. *Testez* : Utilisez la fonction `powerIteration` écrite à l'exercice 1 pour calculer la centralité de vecteur propre **dans le cas non orienté** (utilisez le graphe `G1` défini plus haut). Vous fixerez un réel epsilon permettant d’indiquer la précision du calcul.\n",
    "Faites appel à la fonction `drawGraph` pour voir le résultat de vos calculs s’afficher sur les sommets du graphe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cef690b8-75e6-4d9a-9212-b864064c19b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ff48f37-196e-4b82-8908-dd69e81a35b3",
   "metadata": {},
   "source": [
    "2. *Expérimentation* : Modifiez votre fonction powerItération pour qu'elle\n",
    "retourne aussi le nombre d'itérations. Faites varier epsilon (1e-3,\n",
    "1e-6, 1e-9) et observez l'impact sur le nombre d'itérations. Quel\n",
    "compromis cela met-il en évidence ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa530fb2-ccfa-45c3-992f-e424fbab2ec7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbd0606f-f03c-4e18-993e-888c7da7ca4e",
   "metadata": {},
   "source": [
    "# Exercice 3 : Page Rank (cas orienté)\n",
    "\n",
    "1. Écrire une fonction `matrixPageRank` permettant de construire la matrice de passage du \n",
    "Page Rank qui nous permettra de calculer la centralité de vecteur propre dans \n",
    "le **cas orienté** . Cette fonction prend en paramètre un graphe orienté et un réel alpha \n",
    "correspondant au facteur de zap (dumping factor). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8dc676c2-06e6-4973-a75f-aef1395d05f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrixPageRank(G,alpha=0.85):\n",
    "  # TODO: Implémenter la construction de la matrice P comme vu en cours\n",
    "    pass  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "472cdfea-9660-4203-afc5-765f0e9f16d5",
   "metadata": {},
   "source": [
    "2. Utilisez la fonction `matrixPageRank` pour calculer la matrice de passage du graphe disponible sur Moodle (que vous devez construire auparavant), puis calculez la valeur du Page Rank de chaque sommet à l'aide de la fonction `powerIteration`.  \n",
    "\n",
    "La valeur du Page Rank de chaque sommet est la suivante (arrondie à 2 décimales) :\n",
    "\n",
    "`[[0.33]\n",
    " [0.32]\n",
    " [0.31]\n",
    " [0.04]]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27e088c4-00e5-4822-871e-68fa26753afb",
   "metadata": {},
   "outputs": [],
   "source": [
    "#TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76971896-0a30-4332-aa2e-b4ee214f8c48",
   "metadata": {},
   "source": [
    "3. Testez votre fonction sur le graphe de citations scientifiques\n",
    "`GCit`. Quel noeud est le plus important ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b3f6547-be39-4b51-8236-004729755656",
   "metadata": {},
   "outputs": [],
   "source": [
    "#TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a656c55c-117c-435a-9521-742b78a91edb",
   "metadata": {},
   "source": [
    "4. *Rôle de $\\alpha$* : Recalculez le PageRank de $G3$ pour $\\alpha = 1$ et\n",
    "$\\alpha = 0$. Que se passe-t-il pour $\\alpha = 1$ ? Le résultat\n",
    "est-il celui attendu ? Que représente le PageRank quand $\\alpha =\n",
    "0$ ? Le résultat est-il logique ? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f4d2d322-884f-4893-900a-d41c96f175eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "#TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "410bff16-0cf8-4f34-9100-4dc5af4e73b0",
   "metadata": {},
   "source": [
    "# Exercice 4\n",
    "\n",
    "La construction de la matrice de passage $P$ dans matrixPageRank\n",
    "est coûteuse, notamment à cause des produits matriciels. L'objectif\n",
    "est de construire cette matrice $P$ de manière plus efficace, en travaillant ligne par ligne.\n",
    "\n",
    "Pour un sommet $v$ donné, la ligne $v$ de la matrice $P$ dépend de deux cas :  \n",
    "\n",
    "a. Si $v$ n'est pas un puits ($d^+(v) > 0$) : la ligne $v$ de $P$ est\n",
    "$\\alpha * (\\frac{1}{d^+(v)}) A_v + \\frac{(1-\\alpha)}{n} u'$, où $A_v$ est la ligne\n",
    "$v$ de la matrice d'adjacence et $u'$ un vecteur ligne de 1.  \n",
    "\n",
    "b. Si $v$ est un puits ($d^+(v) = 0$) : la ligne $v$ de $P$ est $\\frac{u'}{n}$.\n",
    "\n",
    "1. Écrivez une nouvelle fonction matrixPageRankFast(G, alpha=0.85)\n",
    "qui implémente cette approche."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71e528c6-7a2d-4172-bad7-b8d16da4b814",
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrixPageRankFast(G,alpha=0.85):\n",
    "    # TODO: Implémenter la construction optimisée de la matrice P\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a60a659b-3115-4bf0-b2f5-39d83c0dac51",
   "metadata": {},
   "source": [
    "2. *Validation* : Utilisez `np.allclose(P_slow, P_fast)` pour vérifier que votre nouvelle fonction produit bien la même matrice que matrixPageRank sur un petit graphe comme $G3$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "106c14c1-aed3-42dd-a948-257fd6965afe",
   "metadata": {},
   "outputs": [],
   "source": [
    "#TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7005a627-e570-4507-a257-f0be5526044f",
   "metadata": {},
   "source": [
    "3. *Performance* : Utilisez le module time pour comparer le temps d'exécution de `matrixPageRank(Gcit)` et `matrixPageRankFast(Gcit)`. Calculez le gain de performance (ex: \"la version rapide est X fois plus rapide\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b70dbe88-2155-454b-a99e-3b34f54bcc4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "#TODO"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Aucun(e)",
  "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.10.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}