14_analisi_delle_reti_sociali.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Analisi delle reti sociali"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img style=\"float: right;\" src=\"figures/karate_kid.jpg\">\n",
    "\n",
    "*[Zachary's karate club](https://en.wikipedia.org/wiki/Zachary%27s_karate_club) is a well-known social network of a university karate club described in the paper [An Information Flow Model for Conflict and Fission in Small Groups](http://www1.ind.ku.dk/complexLearning/zachary1977.pdf) by Wayne W. Zachary.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Indice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. [Rappresentazione di reti binarie indirette](#reti_binarie_indirette)<br>\n",
    "2. [Algoritimi di *Force-Direction Placements*](#placements)<br>\n",
    "3. [Matrice di adiacenza](#adiacenza)<br>\n",
    "4. [Informazioni di nodo](#informazioni_nodo)<br>\n",
    "5. [Il cammino più corto (*shortest path*)](#shortest_path)<br>\n",
    "6. [Utili indici descrittivi](#indici)<br>\n",
    "    6.1 [Indici descrittivi a livello di nodo](#indici_nodo)<br>\n",
    "    6.2 [Indici descrittivi a livello di rete](#indici_rete)<br>\n",
    "7. [Community Detection](#detection)<br>\n",
    "    7.1 [Metodo di Louvain](#louvain)<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Rappresentazione di reti binarie indirette <a id=reti_binarie_indirette> </a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.cbook import mplDeprecation\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import warnings\n",
    "\n",
    "warnings.filterwarnings(\"ignore\", category=mplDeprecation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grafi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Grafi**, $\\mathcal{G} = (\\mathcal{N}, \\mathcal{A})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.karate_club_graph()\n",
    "print(nx.info(G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Insieme dei nodi $\\mathcal{N} = \\{1, \\dots, V\\}$;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nodi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = G.nodes()\n",
    "print(\"Nodi:\", N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Un arco è definito come una coppia $\\{\\{i, j\\} : i, j \\in \\mathcal{N}, i > j\\}$;\n",
    "* Insieme degli archi $\\mathcal{A} \\subseteq \\{\\{i, j\\} : i, j \\in \\mathcal{N}, i > j\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Archi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = G.edges()\n",
    "print(\"Archi:\", A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Algoritimi di *Force-Direction Placements* <a id=placements> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Definiscono le posizioni dei nodi utilizzando solo le informazioni sugli archi nella rete con un'interpretazione che deriva dalla **Fisica**. Come?\n",
    "* **I nodi** sono visti come particelle in un sistema fisco con una certa energia che risulta da due principali forze che agiscono su ogni nodo;\n",
    "* **Forza repulsiva**: Simile alla forza elettrostatica di **Coulomb**. Agisce su tutti i nodi e genera più energia tanto più i nodi sono vicini;\n",
    "* **Forza attrattiva**: Simile alla forza della molla di **Hooke**. Agisce solo su nodi connessi e genera più energia tanto più i nodi sono lontani.\n",
    "\n",
    "Questi algoritmi individuano le posizioni spaziali dei nodi in modo da ottenere la configurazione più stabile nel sistema di particelle (a minor energia).\n",
    "\n",
    "[spring_layout](https://networkx.github.io/documentation/stable/reference/generated/networkx.drawing.layout.spring_layout.html): *Position nodes using Fruchterman-Reingold force-directed algorithm.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pos = nx.spring_layout(G, iterations=50, seed=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_color_club = ['lightblue' if (N[nodo]['club'] == \"Mr. Hi\") else 'orange' for nodo in N]\n",
    "\n",
    "nx.draw_networkx(\n",
    "    G, \n",
    "    pos=pos,\n",
    "    with_labels=True,\n",
    "    node_color=node_color_club\n",
    ")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Matrice di adiacenza <a id=adiacenza> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Matrice di adiacenza**, $Y$\n",
    "* $Y$ matrice quadrata simmetrica di dimensioni $V \\times V$;\n",
    "* Nodi disposti in riga e colonna;\n",
    "* $Y_{ij} = Y_{ji} = 1$ se ${i, j} \\in \\mathcal{A}$ ($i$ e $j$ sono connessi), $0$ altrimenti."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Y = nx.adjacency_matrix(G)\n",
    "V, V = Y.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Dimensioni: {} X {}\".format(V, V))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(Y.todense())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Esempio\n",
    "\n",
    "Calcolare la matrice di adiacenza $Y$ a partire dal grafo $G$ (vedi definizione sopra)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.sparse.csr import csr_matrix\n",
    "\n",
    "row_ind = []\n",
    "col_ind = []\n",
    "\n",
    "for arco in A:\n",
    "    row_ind.extend(list(arco)) # a, b\n",
    "    col_ind.extend(list(arco)[::-1]) # b, a\n",
    "    \n",
    "Y = csr_matrix((np.ones(len(row_ind)), (np.array(row_ind), np.array(col_ind))), \n",
    "               shape=(V, V), dtype=np.int64)\n",
    "\n",
    "print(\"Dimensioni: {} X {}\\n\".format(V, V))\n",
    "print(Y.todense())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Informazioni di nodo <a id=informazioni_nodo> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### club"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mr_hi = 0\n",
    "officer = 33\n",
    "print(\"Il nodo {} rappresenta \\\"Mr. Hi\\\"\".format(mr_hi))\n",
    "print(N[mr_hi])\n",
    "print(\"\\nIl nodo {} rappresenta \\\"Officer\\\"\".format(officer))\n",
    "print(N[officer])\n",
    "print(\"\\nI rimanenti nodi appartengono a uno dei due club.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_color_club[mr_hi] = 'blue'\n",
    "node_color_club[officer] = 'red'\n",
    "\n",
    "nx.draw_networkx(\n",
    "    G, \n",
    "    pos=pos,\n",
    "    with_labels=True,\n",
    "    node_color=node_color_club\n",
    ")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Il cammino più corto (*shortest path*) <a id=shortest_path> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Per ogni coppia di nodi $i$ e $j$ gli *shortest paths* sono i cammini più corti tra nodi interconnessi che uniscono $i$ a $j$;\n",
    "* Possono essere molteplici;\n",
    "* Lunghezza dello *shortest path*: numero di archi di cui si compone."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Esercizio\n",
    "\n",
    "Utilizzare le funzioni `shortest_path()` e `shortest_path_length()` della libreria NetworkX (già importata come `nx`) per:\n",
    "1. Identificare il cammino più corto tra Mr. Hi e Officer;\n",
    "2. Calcolare la lunghezza del cammino più corto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============== YOUR CODE HERE ==============\n",
    "raise NotImplementedError\n",
    "shortest_path = []\n",
    "lunghezza_shortest_path = None\n",
    "# ============================================\n",
    "\n",
    "print(\"Cammino più corto tra Mr. Hi e Officer:\", shortest_path)\n",
    "print(\"Lunghezza del cammino più corto tra Mr. Hi e Officer:\", lunghezza_shortest_path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. Utili indici descrittivi <a id=indici> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.1 Indici descrittivi a livello di nodo <a id=indici_nodo> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grado di un nodo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Grado di *i*. Numero di nodi con cui è connesso: $d_i = \\sum_{j=1}^{V}Y_{ij}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d_mr_hi = G.degree(mr_hi)\n",
    "\n",
    "print(\"Grado del nodo associato a Mr. Hi: {}\".format(d_mr_hi))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(dict(G.degree()).values())\n",
    "plt.title(\"Istogramma dei gradi\")\n",
    "plt.xlabel('Grado')\n",
    "plt.ylabel('Frequenza')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Esercizio\n",
    "\n",
    "Calcolare il grado del nodo *Mr. Hi* a partire dalla matrice di adiacenza $Y$ (vedi definizione sopra)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============== YOUR CODE HERE ==============\n",
    "raise NotImplementedError\n",
    "d_mr_hi = None\n",
    "# ============================================\n",
    "\n",
    "print(\"Grado del nodo associato a Mr. Hi: {}\".format(d_mr_hi))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### *Betweenness*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Livello di *betweenness* di $i$. È la somma (fatta su tutte le coppie di nodi $u$ e $v$ diversi da $i$) del rapporto tra il numero degli *shortest paths* tra $u$ e $v$ che passano per $i$, $n_{uv}(i)$, ed il totale degli *shortest paths* tra $u$ e $v$, $n_{uv}$: $g_i = \\sum_{u \\neq i \\neq u}\\frac{n_{uv}(i)}{n_{uv}}$.\n",
    "\n",
    "\n",
    "[betweenness_centrality](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.betweenness_centrality.html): *Compute the shortest-path betweenness centrality for nodes. Betweenness centrality of a node $v$ is the sum of the fraction of all-pairs shortest paths that pass through $v$*.\n",
    "\n",
    "* **k** (int, optional (default=None)) – If k is not None use k node samples to estimate betweenness. The value of k <= n where n is the number of nodes in the graph. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = nx.betweenness_centrality(G, k=None)\n",
    "print(\"Livelli di betweenness per ogni nodo:\", g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Esercizio\n",
    "\n",
    "Ricavare a partire dal dizionario `g` il livello di *betweenness* di Mr. Hi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============== YOUR CODE HERE ==============\n",
    "raise NotImplementedError\n",
    "betweenness_mr_hi = None\n",
    "# ============================================\n",
    "\n",
    "print(\"Betweenness del nodo \\\"Mr. Hi\\\": {:.2f}\".format(betweenness_mr_hi))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title(\"Istogramma della betweenness\")\n",
    "plt.hist(g.values())\n",
    "plt.xlabel('Betweenness')\n",
    "plt.ylabel('Frequenza')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.preprocessing import MinMaxScaler\n",
    "\n",
    "scaler = MinMaxScaler((100, 1000))\n",
    "node_size_betweenness = scaler.fit_transform(np.array([g[nodo] for nodo in N]).reshape(-1, 1))\n",
    "\n",
    "plt.title(\"Rappresentazione nella rete dei diversi livelli di betweenness\")\n",
    "nx.draw_networkx(\n",
    "    G, \n",
    "    pos=pos,\n",
    "    with_labels=True,\n",
    "    node_color=node_color_club,\n",
    "    node_size=node_size_betweenness\n",
    ")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.2 Indici descrittivi a livello di rete <a id=indici_rete> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Densità del grafo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Densità di $G$. Frequenza relativa del numero totale di archi osservati, sul totale degli archi possibili: $D = \\frac{1}{V(V - 1)}\\sum Y_{ij}$;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "D = nx.density(G)\n",
    "\n",
    "print(\"Densità del grafo G: {:.2f}\".format(D))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Esercizio\n",
    "Calcolare la densità del grafo $G$ a partire dalla matrice di adiacenza $Y$ (vedi definizione sopra)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============== YOUR CODE HERE ==============\n",
    "raise NotImplementedError\n",
    "D = None\n",
    "# ============================================\n",
    "\n",
    "print(\"Densità del grafo G: {:.2f}\".format(D))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Diametro del grafo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Diametro di $G$. Lunghezza del più lungo *shortest path*;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Diametro del grafo G: {}\".format(nx.diameter(G)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Lunghezza media di *shortest path*. Media delle lunghezze minime di *path*. $L = \\frac{1}{V(V - 1)}\\sum s_{ij}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = nx.average_shortest_path_length(G)\n",
    "print(\"Lunghezza media di shortest path del grafo G: {:.2f}\".format(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Misure di omofilia - Modularità"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Modularità. Frazione di archi che connette nodi dello stesso tipo meno il valore atteso della stessa quantità in una rete con connessioni casuali: $Q = \\sum_k^K (e_{kk} - a_k^2)$, dove $e_{kk}$ rappresenta la frazione degli archi completamente contenuti nella comunità $k$ e $a_k$ è la frazione delle estremità degli archi contenuti nella comunità $k$.\n",
    "\n",
    "Nota: Nella rete con connessioni casuali ogni nodo viene vincolato a mantenere il suo grado, in pratica è come se si tagliasse ogni arco in due e ogni mezzo arco, chiamato *stub*, venisse ricablato casualmente con qualsiasi altro *stub* nella rete. Se $a^\\star_k$ è il numero di *stub* nella comunità $k$, il numero di possibili archi contenuti nella comunità $k$ (consentendo *self loops*) è ${a^\\star_k}^2$, il valore atteso degli archi contenuti nella comunità $k$ è quindi $^{{a^\\star}_k^2}/_{l^2}$ dove $l$ è il numero di *stub* nella rete. Visto che $a_k = {^{{a^\\star}_k}/_{l}}$, il valore atteso degli archi contenuti nella comunità è anche pari a $a_k^2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_esem = nx.make_small_graph([\"edgelist\", \"Esempio di rete\", 6, [[1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [5, 6], [2, 5]]])\n",
    "pos_esem = nx.spring_layout(G_esem, iterations=50, seed=3)\n",
    "part_esem = {0: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1}\n",
    "node_color_esem = ['lightblue' if (part_esem[nodo] == 0) else 'orange' for nodo in G_esem.nodes()]\n",
    "\n",
    "nx.draw_networkx(\n",
    "    G_esem, \n",
    "    pos=pos_esem,\n",
    "    node_color=node_color_esem,\n",
    "    with_labels=True\n",
    ")\n",
    "plt.title(\"Esempio di rete\")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import community\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calcolo della modularità"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = community.modularity(part_esem, G_esem)\n",
    "\n",
    "print(\"Modularità del grafo: {:.2f}\".format(Q))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Esempio\n",
    "\n",
    "Ricavare la modularità di un grafo senza utilizzare la funzione `modularity()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "freq_rel = pd.DataFrame(\n",
    "    [[6 / 14, 1 / 14], [1 / 14, 6 / 14]],\n",
    "    columns=[\"Gruppo 1\", \"Gruppo 2\"], \n",
    "    index=[\"Gruppo 1\", \"Gruppo 2\"]\n",
    ")\n",
    "freq_rel['Marginale'] = freq_rel.sum(axis=0)\n",
    "freq_rel = freq_rel.append(pd.Series(freq_rel.sum(axis=0), name='Marginale'))\n",
    "\n",
    "print(\"Tabella delle frequenze relative:\")\n",
    "display(freq_rel.round(2))\n",
    "\n",
    "num_archi = 7\n",
    "num_estremita = num_archi * 2\n",
    "num_archi_1 = 3\n",
    "num_archi_2 = 3\n",
    "num_estremita_1 = 7\n",
    "num_estremita_2 = 7\n",
    "\n",
    "Q_a_mano = (num_archi_1 / num_archi + num_archi_2 / num_archi) - \\\n",
    "    ((num_estremita_1 / num_estremita) ** 2 + (num_estremita_2 / num_estremita) ** 2)\n",
    "\n",
    "Q_freq_rel = np.diagonal(freq_rel)[:-1].sum() - (freq_rel['Marginale'][:-1] ** 2).sum()\n",
    "\n",
    "Q = community.modularity(part_esem, G_esem)\n",
    "\n",
    "print(\"\\nValore di Q calcolato \\\"a mano\\\": {:.2f}\".format(Q_a_mano))\n",
    "print(\"Valore di Q calcolato a partire dalla matrice delle frequenze relative: {:.2f}\".format(Q_freq_rel))\n",
    "print(\"Valore di Q calcolato tramite la funzione modularity: {:.2f}\".format(Q))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Esercizio\n",
    "\n",
    "Definire una nuova rete e ripetere l'esercizio."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============== YOUR CODE HERE ==============\n",
    "raise NotImplementedError\n",
    "# ============================================"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7. Community Detection <a id=detection> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Obiettivo**: Dividere la rete in comunità di nodi, in modo che nodi all'interno di ogni comunità abbiano molte connessioni tra loro (rete densa), mentre nodi in comunità diverse siano poco connessi (rete sparsa). Esistono vari approcci:\n",
    "* **Algoritmo di Girvan-Newman**: basato sulla *betweenness* di arco;\n",
    "* **Metodo di Louvain**: ottimizzazione della modularità;\n",
    "* E altri ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "communities = next(nx.community.girvan_newman(G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "part_girvan_newman = {node: int(node in communities[0]) for node in N}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q_girvan_newman = community.modularity(part_girvan_newman, G)\n",
    "print(\"Modularità, comunità identificate con Girvan-Newman (n = 2): {:.2f}\".format(Q_girvan_newman))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.1 Metodo di Louvain <a id=louvain> </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Metodo di Louvain**\n",
    "1. L'algoritmo è inizializzato mettendo ogni nodo in una comunità diversa;\n",
    "2. Per ogni nodo $i$ si calcola il guadagno in modularità $\\Delta Q_{i:i \\rightarrow C_j}$ ottenuto nello spostare $i$ dalla sua comunità a quella di ogni nodo $j$ connesso ad $i$;\n",
    "3. Il nodo $i$ viene messo nella comunità con maggiore incremento in modularità se l'incremento è positivo. Altrimenti rimane nella sua comunità. Questo processo è applicato in ripetizione e sequenzialmente a tutti i nodi fino a quando la modularità non aumenta più;\n",
    "4. Le comunità vengono raggruppate a formare una nuova rete (pesata con *self loops*) in cui le comunità sono i nuovi nodi e i nuovi pesi degli archi sono dati dal numero totale di archi che connettono i nodi nelle due comunità;\n",
    "5. Torna a 2. e riapplica il procedimento alla nuova rete tra comunità."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "part_louvain = community.best_partition(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q_louvain = community.modularity(part_louvain, G)\n",
    "print(\"Modularità, comunità identificate con Louvain: {:.2f}\".format(Q_louvain))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_color_girvan_newman = ['lightgreen' if (nodo in communities[0]) else 'yellow' for nodo in N]\n",
    "node_color_louvain = [part_louvain.get(nodo) for nodo in N]\n",
    "\n",
    "plt.figure(figsize=(12, 8))\n",
    "\n",
    "plt.subplot(221)\n",
    "\n",
    "nx.draw_networkx(\n",
    "    G, \n",
    "    pos=pos,\n",
    "    with_labels=True,\n",
    "    node_color=node_color_club,\n",
    "    node_size=node_size_betweenness\n",
    ")\n",
    "plt.title(\"I due club\")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "\n",
    "plt.subplot(222)\n",
    "\n",
    "nx.draw_networkx(\n",
    "    G, \n",
    "    pos=pos,\n",
    "    with_labels=True,\n",
    "    node_color=node_color_girvan_newman,\n",
    "    node_size=node_size_betweenness\n",
    ")\n",
    "plt.title(\"Comunità trovate usando l'algoritmo di Girvan-Newman (n = 2)\")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "\n",
    "plt.subplot(223)\n",
    "plt.text(0.5, 0.6, \"Community Detection\", size=30, ha=\"center\", va=\"center\")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "\n",
    "plt.subplot(224)\n",
    "\n",
    "nx.draw_networkx(\n",
    "    G, \n",
    "    pos=pos,\n",
    "    with_labels=True,\n",
    "    cmap=plt.get_cmap(\"Set2\"),\n",
    "    node_color=node_color_louvain,\n",
    "    node_size=node_size_betweenness\n",
    ")\n",
    "plt.title(\"Comunità trovate usando il metodo di Louvain\")\n",
    "plt.axis('off')\n",
    "plt.tight_layout()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}