132 - Machine learning et Théorie des graphes avec NetworkX.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Module 1 : Introduction à la théorie des graphes\n",
    "\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline \n",
    "\n",
    "G = nx.read_gml('lesmis.gml')     #import graphe networkx.classes.graph.Graph\n",
    "\n",
    "pos = nx.fruchterman_reingold_layout(G)     # fct graphe sur l objet G\n",
    "\n",
    "plt.figure(figsize = (20, 10))     #  cree une figure\n",
    "nx.draw_networkx_nodes(G, pos)     #  place les points a leur position\n",
    "nx.draw_networkx_edges(G, pos, edge_color = \"#75DFC1\")     #liens des points\n",
    "nx.draw_networkx_labels(G, pos)     # place les labels sur le graphe\n",
    "plt.show();         #\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "dict1 = dict(G.degree())   #l argument degree permet de get le nombre de link\n",
    "for pers in sorted(dict1, key=dict1.get)[-5:-1]:\n",
    "    print(pers,  \"est connecté à\", G.degree(pers), \"autres personnages\")\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "#méthodes qui permet d'identifier des communautés \n",
    "    \n",
    "#faire tourner la méthode de Louvain sur le graphe\n",
    "from community.community_louvain import best_partition\n",
    "best_part = best_partition(G)   #fonction best part (G)\n",
    "\n",
    "# afficher le résultat de l'algorithme de Louvain\n",
    "plt.figure(figsize=(20,10))     #figure\n",
    "plt.axis('off')      #axe invisible\n",
    "\n",
    "pos = nx.fruchterman_reingold_layout(G)  # fct graphe sur l objet G\n",
    "node_cluster = list(best_part.values())  # fonction best part (G) value: color\n",
    "\n",
    "nx.draw_networkx_nodes(G, pos, node_color = node_cluster)   #point\n",
    "nx.draw_networkx_edges(G, pos, alpha = 0.5)   #link\n",
    "nx.draw_networkx_labels(G, pos)   #label\n",
    "plt.show()\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "#qualité de notre partitionnement \n",
    "\n",
    "from networkx.algorithms.community.quality import coverage\n",
    "\n",
    "# Définir la séquence de la meilleure partition\n",
    "sequence = [list() for _ in range(6)]\n",
    "sorted_best_partition = sorted(best_part.items(), key=lambda t: t[1])\n",
    "for e in sorted_best_partition:\n",
    "    sequence[e[1]].append(e[0])\n",
    "\n",
    "# Mesurer la qualité de la méthode de Louvain\n",
    "print(\"Ce partitionnement obtient un score de couverture de :\", coverage(G, sequence))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#module 2 : Premiers pas \n",
    "\n",
    "import networkx as nx\n",
    "import pandas as pd\n",
    "%matplotlib inline\n",
    "\n",
    "df = pd.read_csv ('edgelist.csv')\n",
    "df.head()\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "G = nx.from_pandas_edgelist(df)   #networkx.classes.graph.Graph depuis 1 df \n",
    "nx.draw_networkx(G)  #trace le graphe\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "G = nx.Graph()   # Créer un graphe vide\n",
    "\n",
    "# Ajout de noeuds\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "H = nx.path_graph(12)  #creation d un graph avec des points\n",
    "G.add_nodes_from(H)   #ajout de ces noeuds\n",
    "\n",
    "# Ajout d'arêtes \n",
    "#-----------------------------------------------------------------------\n",
    "G.add_edges_from([(0, 1), (1, 2), (2, 3),    #liens entre les noeuds\n",
    "                  (3, 4), (7, 8), (8, 9),    #\n",
    "                  (9, 10), (10, 11)])\n",
    "\n",
    "\n",
    "#fct et attribut\n",
    "G.number_of_nodes()\n",
    "G.number_of_edges()\n",
    "G.nodes\n",
    "\n",
    "\n",
    "\n",
    "# Suppression d'un noeud ou d'une arête\n",
    "#-----------------------------------------------------------------------\n",
    "G.remove_nodes_from([5, 6, 7])\n",
    "\n",
    "list(G.nodes)   #verification de la suppression des nodes \n",
    "\n",
    "\n",
    "\n",
    "#Degré d'un noeud\n",
    "#-----------------------------------------------------------------------\n",
    "# Calculer le degré du sommet 1 du graphe G\n",
    "G.degree[1]    #degree = 2 le noeud est connecte a deux noeuds\n",
    "\n",
    "\n",
    "#Matrice d'adjacence\n",
    "#-----------------------------------------------------------------------\n",
    "# Calculer la matrice d'adjacence du graphe G\n",
    "A = nx.adjacency_matrix(G)\n",
    "\n",
    "# Convertir et afficher la matrice d'adjacence du graphe G\n",
    "A.todense()\n",
    "#A noter que la matrice d'adjacence d'un graphe non orienté est toujours symétrique\n",
    "\n",
    "\n",
    "#Visualisation des graphes\n",
    "#-----------------------------------------------------------------------\n",
    "nx.draw_networkx(G)\n",
    "\n",
    "\n",
    "#personnaliser la représentation graphique d'un graphe\n",
    "#-----------------------------------------------------------------------\n",
    "# Définir les paramètres de la représentation graphique du graphe G\n",
    "options = {\n",
    "    'node_color': '#75DFC1',\n",
    "    'edge_color': '#009999',\n",
    "    'node_size': 500,\n",
    "    'width': 2,\n",
    "    'with_labels': True,\n",
    "    'font_weight': 'bold'\n",
    "}\n",
    "\n",
    "# Afficher le graphe G \n",
    "nx.draw_circular(G, **options)\n",
    "#La méthode du dictionnaire d'options est très pratique \n",
    "#pour passer les mêmes options en parmaètre de plusieurs graphes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#module 3 : Algorithmes fondamentaux : Kruskal et Dijkstra\n",
    "\n",
    "\n",
    "#Importez le package NetworkX sous le nom nx\n",
    "import networkx as nx\n",
    "import matplotlib\n",
    "\n",
    "##\n",
    "G = nx.Graph()\n",
    "\n",
    "G.add_nodes_from(range(1, 32))\n",
    "\n",
    "G.add_edges_from([(1, 3), (2, 9), (2, 10), (10, 19), (10, 20), (10, 3), (20, 11), (20, 21), (21, 22),\\\n",
    "                  (11, 12), (3, 4), (3, 13), (13, 23), (23, 24), (14, 5), (5, 15), (15, 26), (15, 25),\\\n",
    "                  (15, 6), (6, 7), (7, 8), (7, 16), (17, 18), (17, 32), (32, 31), (16, 28), (16, 30),\\\n",
    "                  (30, 29), (28, 27), (17, 8), (16, 32), (28, 6), (28, 26), (6, 27), (1, 5), (1, 4),\\\n",
    "                  (3, 12), (3, 11), (4, 12), (5, 11), (3, 5), (4, 5)])\n",
    "##\n",
    "#Affichez le graphe généré\n",
    "nx.draw_spring(G, with_labels=True)\n",
    "\n",
    "# ---------------------------------------------------------------\n",
    "\n",
    "nx.is_connected(G)   #détermine si le graphe  GG  est connexe\n",
    "\n",
    "print(nx.is_tree(G))     #détermine si le graphe G est un arbre\n",
    "\n",
    "print(nx.find_cycle(G))     # identifiez une liste d'arrêtes formant un cycle dans ce graphe\n",
    "\n",
    "\n",
    "#Calcul des nodes et des arretes\n",
    "# ---------------------------------------------------------------\n",
    "# Calculer la taille du graphe G\n",
    "order = nx.number_of_nodes(G)\n",
    "print(\"Le graphe a :\",order, \"noeuds\")\n",
    "\n",
    "# Calculer l'ordre du graphe G\n",
    "size = nx.number_of_edges(G)\n",
    "print(\"Le graphe a :\", size, \"arêtes\")\n",
    "\n",
    "# Calculer la degré moyen du graphe G\n",
    "average_degree = 2 * size / order\n",
    "print(\"Soit une moyenne de\" , average_degree, \"arêtes par noeuds\")\n",
    "\n",
    "# Algotrithme de Kruskal\n",
    "# ---------------------------------------------------------------\n",
    "#il cherche à optimiser une solution localement en espérant \n",
    "# onverger vers l'optimum global.\n",
    "#tracez un graphe a partir d un fichier texte\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "G = nx.read_weighted_edgelist('fibre_optique.txt')\n",
    "V = nx.number_of_edges(G)     #nombre arrete \n",
    "print(\"Ce graphe a\", V, \"arêtes\")\n",
    "\n",
    "pos = nx.fruchterman_reingold_layout(G)   # fonction applique a g\n",
    "\n",
    "plt.figure(figsize = (20, 10))\n",
    "nx.draw_networkx_nodes(G, pos)    #point sur la figure\n",
    "nx.draw_networkx_edges(G, pos, alpha = 0.3)    #lien sur la figure\n",
    "\n",
    "labels = nx.get_edge_attributes(G,'weight')  # definition du label\n",
    "\n",
    "nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)    #label des axes\n",
    "nx.draw_networkx_labels(G,pos)       #label des points\n",
    "plt.show()\n",
    "\n",
    "\n",
    "\n",
    "mst = nx.tree.minimum_spanning_tree(G)   #permet de trouver l'arbre couvrant\n",
    "\n",
    "plt.figure(figsize = (20, 10))   #creation d une figure\n",
    "nx.draw_networkx_nodes(mst, pos)   #dessine les points\n",
    "nx.draw_networkx_edges(mst, pos, alpha = 0.3)   #dessine les links\n",
    "labels = nx.get_edge_attributes(mst,'weight')   #\n",
    "nx.draw_networkx_edge_labels(mst,pos,edge_labels=labels)   #dessin les labels links\n",
    "nx.draw_networkx_labels(mst,pos)   #dessine les labels\n",
    "plt.show()\n",
    "\n",
    "print(\"L'arbre couvrant de poids minimal a\", nx.number_of_edges(mst), \"arêtes\")\n",
    "\n",
    "# Insérez votre code ici\n",
    "\n",
    "print(\"Le coût de construction de tous les canaux de fibre est de\", G.size(weight = 'weight'), \"k€\")\n",
    "print(\"Le coût de construction du réseau obtenu par Kruskal est de\", mst.size(weight = 'weight'), \"k€\")\n",
    "\n",
    "\n",
    "\n",
    "# Algorithme de Dijkstra\n",
    "# ---------------------------------------------------------------\n",
    "\n",
    "#La fonction shortest_path du package NetworkX permet de calculer le plus court chemin \n",
    "#entre deux points d'un graphe.\n",
    "\n",
    "#affichez le plus court chemin entre la ville n°9 et la ville n°34\n",
    "print(\"Le plus court chemin entre la ville 9 et la ville 34 est :\",nx.shortest_path(G, source = '9', target = '34', weight = 'weight'))\n",
    "\n",
    "#affichez le plus court chezmin depuis la ville n°12 vers toutes les autres villes.\n",
    "print(\"La ville 12 est accessible par les chemins :\",nx.shortest_path(G, source = '12', weight = 'weight'))\n",
    "\n",
    "#Calculer la longueur du chemin entre les villes 9 et 34\n",
    "nx.shortest_path_length(G, source = '9', target = '34', weight = 'weight')\n",
    "\n",
    "#Comparez le plus court chemin moyen entre le graphe du réseau complet et \n",
    "#l'arbre couvrant minimum calculé plus tôt\n",
    "print(\"Temps de parcours moyen dans le véritable réseau :\\t\", nx.average_shortest_path_length(G, weight = 'weight'))\n",
    "print(\"Temps de parcours moyen dans le réseau réduit :\\t\\t\", nx.average_shortest_path_length(mst, weight = 'weight'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Théorie des graphes et analyse des réseaux sociaux \n",
    "# Détection de communautés \n",
    "\n",
    "# --------------------------------------------------------------------------\n",
    "# une communaute : \n",
    "\n",
    "# Une communauté est formée par un ensemble d'individus qui interagissent \n",
    "# plus souvent entre eux qu'avec les autres. Il s'agit donc de groupes \n",
    "# d'individus qui ont formés des liens plus forts ou qui ont \n",
    "# des affinités communes.\n",
    "\n",
    "# --------------------------------------------------------------------------\n",
    "#Detection de communaute : \n",
    "\n",
    "# La détection de communautés a pour rôle de mettre en évidence ces groupes \n",
    "# qui se sont formés implicitement, qui ne résultent pas d'un choix explicite.\n",
    "# Dans une entreprise, à titre d'exemple, les employés forment des communautés \n",
    "# explicites (les services), mais certains vont collaborer plus souvent avec \n",
    "# d'autres et former des communautés implicites.\n",
    "\n",
    "#La détection de communautés permet d'identifier des profils types, d'effectuer \n",
    "#des actions ciblées, de mieux ajuster les recommandations, réorganisation, \n",
    "#d'identifier les acteurs centraux ou influents, etc.\n",
    "\n",
    "# --------------------------------------------------------------------------\n",
    "#Représentation d'un réseau social\n",
    "\n",
    "# Un réseau social peut être représenté par un graphe  G(V,E) où  \n",
    "# V  représente l'ensemble des sommets (vertices en anglais)   \n",
    "# E  l'ensemble des arêtes (edges en anglais). \n",
    "# On rappelle qu'un graphe peut être représenté à l'aide de sa matrice adjacence  (Aij)(Aij) .\n",
    "\n",
    "# Au sens du graphe, une communauté est constitué par un ensemble de nœuds \n",
    "# qui sont fortement liés entre eux, et faiblement liés avec les nœuds situés \n",
    "# en dehors de la communauté.\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# Fixer la graine, afin d'avoir des valeurs reproductibles\n",
    "np.random.seed(1)\n",
    "\n",
    "# Générer le réseau de karaté de Zachary\n",
    "z = nx.karate_club_graph()\n",
    "\n",
    "# Listes des noeuds de chaque communautés\n",
    "mr_hi_node = [0]\n",
    "mr_hi_group = [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 16, 17, 19, 21]\n",
    "john_a_node = [33]\n",
    "john_a_group = [9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]\n",
    "\n",
    "# Positionner les noeuds en utilisant l'algorithme Fruchterman-Reingold\n",
    "# Il permet un positionnement idéal des points sur un graphique pour un eviualisation claire.\n",
    "pos = nx.fruchterman_reingold_layout(z)\n",
    "\n",
    "# Afficher les deux communautés du réseau de Karaté\n",
    "plt.figure(figsize = (20, 10))\n",
    "\n",
    "nx.draw_networkx_nodes(z, pos, node_size = 400, #point group Mr Hi\n",
    "                       nodelist = mr_hi_group, \n",
    "                       node_color = \"#272839\")\n",
    "\n",
    "nx.draw_networkx_nodes(z, pos,              #point Mr Hi\n",
    "                       node_size = 800, \n",
    "                       nodelist = mr_hi_node, \n",
    "                       node_color = \"#272839\")\n",
    "\n",
    "nx.draw_networkx_nodes(z, pos, node_size = 800,    #point john\n",
    "                       nodelist = john_a_node, \n",
    "                       node_color = \"#75DFC1\")\n",
    "\n",
    "nx.draw_networkx_nodes(z, pos, node_size = 400,    #point group john\n",
    "                       nodelist = john_a_group, \n",
    "                       node_color = \"#75DFC1\")\n",
    "\n",
    "nx.draw_networkx_edges(z, pos, alpha = 0.3, edge_color = \"#48dbc8\")\n",
    "nx.draw_networkx_labels(z, pos, {0:\"Hi\", 33:\"John\"}, font_color = \"white\")\n",
    "plt.show()\n",
    "\n",
    "#----------------------------------------------------------------------\n",
    "# Nombre de sommets et d'arêtes\n",
    "print(\"Nombre d'arêtes \\t:\", z.size())  #nombre d'arêtes du réseau z\n",
    "print(\"Nombre de sommets \\t:\", z.order())  #nombre de sommets du réseau z\n",
    "\n",
    "# Vérifier que le réseau est connexe\n",
    "is_connected = nx.is_connected(z)\n",
    "print(\"Le réseau de Karaté est\", (1 - is_connected) * \"non\", 'connexe')\n",
    "\n",
    "# Affecter respectivement aux variables A, diameter \n",
    "# density la matrice d'adjacence\n",
    "A = nx.adjacency_matrix(z)\n",
    "diameter = nx.diameter(z)\n",
    "density = nx.density(z)\n",
    "\n",
    "#-----------------------------------------------------------------------\n",
    "# Calculer la longueur de plus court chemin entre tous les sommets du graphe z\n",
    "path_length = dict(nx.all_pairs_shortest_path_length(z))\n",
    "\n",
    "# Définir la matrice distances\n",
    "n = len( z.nodes() )\n",
    "distances = np.zeros((n, n))\n",
    "for u in path_length.keys() :\n",
    "    for v in path_length[u].keys() :\n",
    "        distances[u][v] = path_length[u][v]\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "from scipy.cluster.hierarchy import linkage\n",
    "\n",
    "hclust = linkage(distances, method = 'ward')\n",
    "\n",
    "\n",
    "from scipy.cluster.hierarchy import dendrogram\n",
    "\n",
    " \n",
    "# Initialisaion de la figrue\n",
    "plt.figure(figsize=(20, 10))\n",
    "# Affichage du dendrogramme\n",
    "plt.title(\"Dendrogramme CAH\")\n",
    "dendrogram(hclust, color_threshold = 17)\n",
    "plt.show()\n",
    "\n",
    "\n",
    "#Approche Agglomérative basée sur la maximisation de la modularité\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "# grouper les sommets\n",
    "\n",
    "# Importer la classe community_louvain\n",
    "from community.community_louvain import best_partition\n",
    "\n",
    "# Calculer et afficher la meilleure répartition des groupes\n",
    "best_part = best_partition(z)\n",
    "print('La meilleure répartition est:\\n', best_part)\n",
    "\n",
    "\n",
    "\n",
    "# Afficher les différents groupes de la meilleure répartition du réseau z\n",
    "plt.figure(figsize=(10,10))\n",
    "plt.axis('off')\n",
    "pos = nx.fruchterman_reingold_layout(z)\n",
    "node_cluster = list(best_part.values())\n",
    "nx.draw_networkx_nodes(z, pos, node_color = node_cluster)\n",
    "nx.draw_networkx_edges(z, pos, alpha = 0.5)\n",
    "nx.draw_networkx_labels(z, pos, {0:\"Hi\", 33:\"John\"}, font_color = \"white\")\n",
    "plt.show()\n",
    "\n",
    "\n",
    "\n",
    "#Approche divisive, algorithme de Girvan-Newman\n",
    "#-----------------------------------------------------------------------\n",
    "# identifier les arêtes qui font le lien entre des communautés \n",
    "#Approche divisive, algorithme de Girvan-Newman\n",
    "from networkx.algorithms.community import girvan_newman\n",
    "communities_generator = nx.algorithms.community.girvan_newman(z)\n",
    "\n",
    "community = next(communities_generator)\n",
    "community   #premier partitionnement créé par l'algorithme de Girvan-Newman\n",
    "\n",
    "\n",
    "\n",
    "#Évaluation de l'approche agglomérative\n",
    "#-----------------------------------------------------------------------\n",
    "\n",
    "from networkx.algorithms.community.quality import performance\n",
    "\n",
    "performance(z,community)\n",
    "\n",
    "\n",
    "\n",
    "# Calculer un itérateur \n",
    "communities_generator = nx.algorithms.community.girvan_newman(z)\n",
    "\n",
    "#On initialise les variables nécessaires à la boucle\n",
    "best_score = 0\n",
    "scores = []\n",
    "\n",
    "# Mesure de la performance de chaque partitionnement\n",
    "for partition in communities_generator :\n",
    "    cur_score = performance(z, partition)\n",
    "    \n",
    "    if(cur_score >= best_score) :\n",
    "        best_partition = partition\n",
    "        best_score = cur_score\n",
    "        \n",
    "    scores.append(cur_score)\n",
    "\n",
    "# Tracer les performances de chaque partitionnement\n",
    "plt.plot(range(len(scores)), scores);\n",
    "print(best_partition)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Algorithme PageRank\n",
    "\n",
    "\n",
    "# Lecture du fichier 'polblogs.gml'\n",
    "Gr = nx.read_gml('polblogs.gml')\n",
    "# Affichage du nombre de noeuds\n",
    "print('Il y a ',nx.number_of_nodes(Gr),' noeuds.', sep = '')\n",
    "# Affichage du nombre d'arêtes\n",
    "print('Il y a ',nx.number_of_edges(Gr),' arêtes.', sep = '')\n",
    "\n",
    "\n",
    "# Création de la liste L grâce à la méthode adj\n",
    "L = list(Gr.adj['alternateworlds.blogspot.com'])\n",
    "# Remplacement de G par son sous-graphe du voisinage de \"alternateworlds.blogspot.com\"\n",
    "G = Gr.subgraph(L)\n",
    "\n",
    "\n",
    "# On définit le nouveau nombre de noeuds de G\n",
    "N = nx.number_of_nodes(G)\n",
    "# Création du dictionnaire par compréhension\n",
    "dic = dict((L[i], i) for i in range(N))\n",
    "\n",
    "\n",
    "\n",
    "# Création des options du graphe à l'aide de Matplotlib en précisant labels': dic\n",
    "plt.figure(figsize = (10, 4))\n",
    "options = {\n",
    "    'node_color': '#FF0000',\n",
    "    'edge_color': '#000000',\n",
    "    'node_size': 700,\n",
    "    'width': 3,\n",
    "    'with_labels': True,\n",
    "    'font_weight': 'bold',\n",
    "    'labels': dic\n",
    "}\n",
    "# Affichage du graphe\n",
    "nx.draw_circular(G, **options)\n",
    "plt.show()\n",
    "\n",
    "\n",
    "\n",
    "# Algorithme Simplifié\n",
    "\n",
    "def PageRankSimple(G, dic, pagerank_old):\n",
    "    N = nx.number_of_nodes(G)\n",
    "    # Création de l'itération+1\n",
    "    pagerank_new = np.ones(N)\n",
    "    # On applique l'algorithme à tous les noeuds de G\n",
    "    for site in G.nodes():\n",
    "        somme = 0\n",
    "        # on fait la somme où on attribue à chaque page pointant vers notre page son ancienne probablité divisée par le nombre\n",
    "        # de pages total\n",
    "        for voisin in G.predecessors(site):\n",
    "            somme += pagerank_old[dic[voisin]]/G.out_degree(voisin)\n",
    "        # Traitement des noeuds qui n'ont pas de liens sortants\n",
    "        for s in G.nodes():\n",
    "            if G.out_degree(s) == 0:\n",
    "                somme += pagerank_old[dic[s]]/N\n",
    "        # On stock les valeurs dans le nouveau vecteur des poids\n",
    "        pagerank_new[dic[site]] = somme\n",
    "    # On actualise les anciennes valeurs des poids\n",
    "    return(pagerank_new)\n",
    "\n",
    "\n",
    "\n",
    "# Initialisation des poids\n",
    "pagerank_old = np.ones(N)/N\n",
    "for compteur in range(3):\n",
    "    # On applique l'algorithme à G, son dictionnaire et le vecteur des poids à actualiser\n",
    "    pagerank_new = PageRankSimple(G, dic, pagerank_old)\n",
    "    # Le nouveau vecteur des poids devient maintenant l'ancien\n",
    "    pagerank_old = pagerank_new\n",
    "    print('La somme des poids vaut ', np.sum(pagerank_new),', ce qui vaut bien approximativement 1.'\\\n",
    "if np.isclose(1,np.sum(pagerank_new)) else \"La somme n'est pas proche de 1.\", sep = '')\n",
    "\n",
    "\n",
    "    \n",
    "    \n",
    "print('Les 4 plus gros sites Web ont pour indices: ', np.argsort(pagerank_new)[-4:], ' ce qui correspond aux sites\\\n",
    " Web suivants:', sep = '')\n",
    "for i in np.argsort(pagerank_new)[-4:]:\n",
    "    print(list(dic.items())[i][0])\n",
    "# Graphiquement on peut remarquer la même chose\n",
    "\n",
    "\n",
    "#Algorithme Facteur Amortissement\n",
    "#---------------------------------------------------------------------\n",
    "\n",
    "#'algorithme PageRank avec un facteur d'amortissement.\n",
    "def PageRankFA(G, dic, pagerank_old, d = 0.85):\n",
    "    N = nx.number_of_nodes(G)\n",
    "    # Création de l'itération+1\n",
    "    pagerank_new = np.ones(N)\n",
    "    # On applique l'algorithme à tous les noeuds de G\n",
    "    for site in G.nodes():\n",
    "        somme = 0\n",
    "        # Calcul de la somme\n",
    "        for voisin in G.predecessors(site):\n",
    "            somme += pagerank_old[dic[voisin]]/G.out_degree(voisin)\n",
    "        # Traitement des noeuds qui n'ont pas de liens sortants\n",
    "        for s in G.nodes():\n",
    "            if G.out_degree(s) == 0:\n",
    "                somme += pagerank_old[dic[s]]/N\n",
    "        # On stock les valeurs dans le nouveau vecteur des poids\n",
    "        pagerank_new[dic[site]] = (1-d)/N+d*somme\n",
    "    # On actualise les anciennes valeurs des poids\n",
    "    return(pagerank_new)\n",
    "\n",
    "\n",
    "# Initialisation des poids\n",
    "pagerank_old = np.ones(N)/N\n",
    "for compteur in range(3):\n",
    "    # On applique l'algorithme à G, son dictionnaire et le vecteur des poids à actualiser\n",
    "    pagerank_new = PageRankFA(G, dic, pagerank_old)\n",
    "    # Le nouveau vecteur des poids devient maintenant l'ancien\n",
    "    pagerank_old = pagerank_new\n",
    "    print('La somme des poids vaut ', np.sum(pagerank_new),', ce qui vaut bien approximativement 1.'\\\n",
    "if np.isclose(1,np.sum(pagerank_new)) else \"La somme n'est pas proche de 1.\", sep = '')\n",
    "\n",
    "\n",
    "print('Les 4 plus gros sites Web ont pour indices: ',np.argsort(pagerank_new)[-4:],' ce qui correspond aux sites\\\n",
    "Web suivants:', sep = '')\n",
    "for i in np.argsort(pagerank_new)[-4:]:\n",
    "    print(list(dic.items())[i][0])\n",
    "# On obtient bien la même chose que précédemment\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#Application à tout le graphe\n",
    "#---------------------------------------------------------------------\n",
    "L = list(Gr.nodes())\n",
    "N = len(L)\n",
    "# Création d'un dictionnaire pour toute la base\n",
    "dic = dict((L[i], i) for i in range(N))\n",
    "# Initialisation de la matrice M\n",
    "M = np.zeros((N,N))\n",
    "# Remplissage de la matrice par colonne\n",
    "for j in range(N):\n",
    "    # Liste des pages sur lesquelles la colonne pointe\n",
    "    liste = list(Gr.successors(L[j]))\n",
    "    Nl = len(liste)\n",
    "    # Remplissage de chacune des cases de ces pages par la formule définit précédemment\n",
    "    for i in range(Nl):\n",
    "        M[dic[liste[i]], j] = 1/Nl\n",
    "# Traitement des colonnes nulles\n",
    "for j in range (N):\n",
    "    if np.sum(M[:,j]) == 0:\n",
    "        M[:,j] = np.ones(N)/N\n",
    "\n",
    "\n",
    "iter = int(round(np.log(N)))\n",
    "# Déclaration du facteur d'amortissement\n",
    "d = 0.85\n",
    "# Initialisation des poids\n",
    "pagerank_old = np.ones(N)/N\n",
    "# Initialisation du nouveau vecteur des poids\n",
    "pagerank_new = np.ones(N)\n",
    "# Création du vecteur constant\n",
    "vconst = np.ones(N)*(1-d)/N\n",
    "for _i in range(iter):\n",
    "    pagerank_new = d*np.matmul(M,pagerank_old)+(1-d)/N\n",
    "    pagerank_old = pagerank_new\n",
    "np.sum(pagerank_new)\n",
    "print('La somme des poids vaut ', np.sum(pagerank_new),', ce qui vaut bien approximativement 1.'\\\n",
    "if np.isclose(1,np.sum(pagerank_new)) else \"La somme n'est pas proche de 1.\", sep = '')\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "print('Les 10 plus gros sites Web ont pour indices: ',np.argsort(pagerank_new)[-10:],' ce qui correspond aux sites\\\n",
    " Web suivants:', sep = '')\n",
    "L = list(Gr.nodes())\n",
    "dic = dict((L[i], i) for i in range(N))\n",
    "for i in np.argsort(pagerank_new)[-10:]:\n",
    "    print(list(dic.items())[i][0])\n",
    "# On obtient bien la même chose que précédemment\n",
    "\n",
    "\n",
    "\n",
    "#Idée Algorithmique\n",
    "#---------------------------------------------------------------------\n",
    "\n",
    "\n",
    "def marche_aléatoire(G = Gr, pas = 10, init = None):\n",
    "    N = nx.number_of_nodes(G)\n",
    "    # Création de la liste des noeuds\n",
    "    L = list(G.nodes())\n",
    "    # On va définir la fonction par récursivité, pour ça il faut distinguer les cas où on est déjà au milieu\n",
    "    # de la marche aléatorie du cas où on est au début du graphe\n",
    "    if init == None:\n",
    "        # Si on n'a pas initialisé la marche aléatoire, on choisit un noeud au hasard du graphe\n",
    "        X = randint(0,N-1)\n",
    "        Start = L[X]\n",
    "    else:\n",
    "        # Sinon on utilise le noeud renseigné\n",
    "        Start = init\n",
    "    # On utilise l'algorithme avec facteur d'amortissement\n",
    "    d = 0.85\n",
    "    Stop = randint(1,100)\n",
    "    if Stop > 85:\n",
    "        return(Start)\n",
    "    # On définit les successeurs du noeud initial pour savoir où aller\n",
    "    V = list(G.successors(Start))\n",
    "    # Si il n'y a pas de voisin, on recommence la marche en choisissant au hasard un nouveau noeud du graphe,\n",
    "    # on perd donc un pas\n",
    "    if len(V) == 0:\n",
    "        return(marche_aléatoire(G = Gr , pas = pas-1, init = None))\n",
    "    else:\n",
    "        # On choisit un voisin au hasard dans les successeurs du noeud initial\n",
    "        Y = randint(0, len(V)-1)\n",
    "        if pas == 1:\n",
    "            # Si le pas vaut 1 on retourne ce voisin, on aura fait une marche aléatoire de taille 1\n",
    "            return(V[Y])\n",
    "        else:\n",
    "            # Sinon on réapplique notre fonction avec comme noeud initial, le voisin précédemment choisi\n",
    "            # et on diminue le pas de 1\n",
    "            return(marche_aléatoire(G = Gr , pas = pas-1, init = V[Y]))\n",
    "        \n",
    "        \n",
    "        \n",
    "#fonction trimi qui prendra pour argument \n",
    "#une liste et renverra une liste de tuple triée\n",
    "\n",
    "def trimi(L):\n",
    "    # On définit un dictionnaire vide\n",
    "    Di = {}\n",
    "    taille = len(L)\n",
    "    # On itère sur chaque élément de la liste pour les rajouter dans le dictionnaire\n",
    "    for i in range(taille):\n",
    "        # Si l'élément n'est pas dans le dictionnaire, on le rajoute avec une fréquence de 1\n",
    "        if L[i] not in Di:\n",
    "            Di = { **Di, **{ L[i] : 1}}\n",
    "        # Sinon on augmente de 1 sa fréquence dans le dictionnaire\n",
    "        else:\n",
    "            Di[L[i]] += 1\n",
    "    # On retourne le dictionnaire trié selon les valeurs\n",
    "    return(sorted(Di.items(), key = lambda val: val[1]))\n",
    "        \n",
    "        \n",
    "L = []\n",
    "# On crée une liste de 100000 marches aléatoires\n",
    "for _i in range(10000):\n",
    "    L.append(marche_aléatoire())\n",
    "# On l'a tri\n",
    "tri = trimi(L)\n",
    "# On affiche les 10 éléments qui reviennent le plus souvant\n",
    "tri[-10:]\n",
    "# On se rend compte que c'est quasiment la même chose qu'en utilisant l'algorithme de PageRank\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "G = nx.read_gml('lesmis.gml')\n",
    "pos = nx.fruchterman_reingold_layout(G)\n",
    "\n",
    "plt.figure(figsize=(10,10))\n",
    "plt.axis('off')\n",
    "\n",
    "nx.draw_networkx_nodes(G, pos)\n",
    "nx.draw_networkx_edges(G, pos, alpha = 0.5)\n",
    "nx.draw_networkx_labels(G, pos, font_color = \"white\")\n",
    "\n",
    "nx.draw_networkx (G)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Importer la classe community_louvain\n",
    "from community.community_louvain import best_partition\n",
    "\n",
    "\n",
    "# Afficher les différents groupes de la meilleure répartition du réseau z\n",
    "plt.figure(figsize=(10,10))\n",
    "plt.axis('off')\n",
    "pos = nx.fruchterman_reingold_layout(G)\n",
    "node_cluster = list(best_part.values())\n",
    "nx.draw_networkx_nodes(G, pos, node_color = node_cluster)\n",
    "nx.draw_networkx_edges(G, pos, alpha = 0.5)\n",
    "nx.draw_networkx_labels(G, pos,  font_color = \"white\")\n",
    "plt.show() ;\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "from community.community_louvain import best_partition\n",
    "best_part = best_partition(G)   #fonction best part (G)\n",
    "\n",
    "from networkx.algorithms.community.quality import coverage\n",
    "\n",
    "# Définir la séquence de la meilleure partition\n",
    "sequence = [list() for _ in range(6)]\n",
    "sorted_best_partition = sorted(best_part.items(), key=lambda t: t[1])\n",
    "for e in sorted_best_partition:\n",
    "    sequence[e[1]].append(e[0])\n",
    "\n",
    "# Mesurer la qualité de la méthode de Louvain\n",
    "print(\"Ce partitionnement obtient un score de couverture de :\", coverage(G, sequence))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Examen \n",
    "\n",
    "Théorie des graphes et analyse des réseaux sociaux \n",
    "\n",
    "\n",
    "\n",
    "L'exercice est composé de plusieurs questions, faites-les dans l'ordre et faites attention à respecter le nom des variables. N'hésitez pas à contacter l'équipe DataScientest si vous rencontrez des problèmes sur help@datascientest.com\n",
    "\n",
    "L'objet de cet exercice est d'explorer le réseau social des personnages de la série télévisée Game of Thrones. Après avoir réalisé un travail de visualisation et de caractérisation du réseau social, on cherchera à détecter des communautés parmi les personnages.\n",
    "\n",
    "Cet exercice porte sur les données got.csv : deux personnages sont reliés si ils partagent une scène dans la première saison de la série Game of Thrones.\n",
    "\n",
    "Importez le package pandas sous le nom pd\n",
    "Chargez le fichier got.csv dans un DataFrame appelé df\n",
    "Affichez les 5 premières lignes de df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "df = pd.read_csv ('got.csv',index_col=[0])\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Importez le package NetworkX sous le nom nx\n",
    "Importez le sous module matplotlib.pyplot sous le nom plt\n",
    "Transformez le DataFrame df en un graphe z\n",
    "En utilisant la disposition de Fruchterman-Reignold, affichez le graphe z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "G = nx.from_pandas_edgelist(df)\n",
    "\n",
    "pos = nx.fruchterman_reingold_layout(G)    \n",
    "\n",
    "plt.figure(figsize = (20, 16)) \n",
    "plt.axis('off')\n",
    "nx.draw_networkx_nodes(G, pos)   \n",
    "nx.draw_networkx_edges(G, pos, edge_color = \"#75DFC1\")    \n",
    "nx.draw_networkx_labels(G, pos)     \n",
    "plt.show();   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculez le nombre de connexions moyennes pour un personnage\n",
    "Calculez la distance entre les deux peronnages les plus éloignés dans le graphe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v1 = G.number_of_nodes()\n",
    "v2 = G.number_of_edges()\n",
    "\n",
    "print (v1)\n",
    "print (v2)\n",
    "\n",
    "print ('Le nombre de connexions moyennes',v2/v1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Importez la fonction best_partition du sous package community.community_louvain\n",
    "A l'aide de la méthode de Louvain, déterminez le partitionnement qui maximise la modularité de ce graphe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from community.community_louvain import best_partition\n",
    "\n",
    "# Calculer et afficher la meilleure répartition des groupes\n",
    "best_part = best_partition(G)\n",
    "print('partitionnement :\\n', best_part)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Affichez le graphe en utilisant la disposition de Fruchterman Reignold et en colorant les noeuds selon le cluster auquel ils appartiennent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(10,10))\n",
    "plt.axis('off')\n",
    "pos = nx.fruchterman_reingold_layout(G)\n",
    "node_cluster = list(best_part.values())\n",
    "nx.draw_networkx_nodes(G, pos, node_color = node_cluster)\n",
    "nx.draw_networkx_edges(G, pos, alpha = 0.5)\n",
    "nx.draw_networkx_labels(G, pos, font_color = \"white\")\n",
    "plt.show()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}