betweenness-centrality.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DyNetworkX Tutorial – Plotting Dynamic Betweenness Centrality\n",
    "\n",
    "The objective of this tutorial is to showcase a typical use case of DyNetworkX.  \n",
    "We will be using the Enron dataset, a preview of the data file can be seen below.  \n",
    "Enron dataset will be downloaded to current directory if not already present. (Size: 2 MB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import  os\n",
    "import urllib\n",
    "import datetime\n",
    "\n",
    "file_path = \"execs.email.linesnum\"\n",
    "\n",
    "if not os.path.exists(file_path):\n",
    "    print(\"Downloading Enron dataset from http://www.cis.jhu.edu/~parky/Enron/execs.email.linesnum ...\")\n",
    "    urllib.request.urlretrieve(\"http://www.cis.jhu.edu/~parky/Enron/execs.email.linesnum\", file_path)\n",
    "    print(\"Download complete.\")\n",
    "    \n",
    "lines = []\n",
    "with open(file_path, \"r\") as file:\n",
    "    for line in file:\n",
    "        t, u, v = line.split(\" \")\n",
    "        if int(t) > 315522000:\n",
    "            lines.append(line)\n",
    "            \n",
    "with open(file_path, \"w\") as file:\n",
    "    for line in lines:\n",
    "        file.write(line)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loading Data into DyNetworkX\n",
    "\n",
    "Loading data a text file using the function `dnx.ImpulseGraph.load_from_txt`.\n",
    "Make sure to specify necessary arguments such as `delimiter`, `timestamptype`, and `order`.\n",
    "\n",
    "Comparing the output of the new ImpulseGraph, it is possible to verify the data set is correctly imported. (Note: order not guaranteed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import dynetworkx as dnx\n",
    "\n",
    "impulseG = dnx.ImpulseGraph.load_from_txt(\"execs.email.linesnum\", delimiter=\" \",\n",
    "                                          timestamptype=int, order=('t', 'v', 'u'))\n",
    "\n",
    "print(impulseG.edges()[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Converting between different graph types\n",
    "\n",
    "Traditionally working with dynamic networks, it is commmon to flatten the temporal dimension by binning data into smaller static graphs called snapshots. This behavior is replicated by the DynetworkX class `SnapshotGraph`.  \n",
    "By using the argument `length_of_snapshots`, it is possible to specify the desired length of each snapshot to 1 year (converted to seconds to match the data set)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "snapshots = impulseG.to_snapshots(length_of_snapshots=31536000)\n",
    "first_timestamp = impulseG.interval()[0]\n",
    "snapshotG = dnx.SnapshotGraph()\n",
    "\n",
    "i = 0\n",
    "for snapshot in snapshots:\n",
    "    snapshotG.add_snapshot(graph=snapshot, start=31536000*i + first_timestamp,\n",
    "                           end=31536000*(i+1) + first_timestamp)\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating Dynamic Betweenness Centrality\n",
    "\n",
    "`compute_network_statistic` returns a list, each item in the list refers to each snapshot in the SnapshotGraph. The specified method is applied to each snapshot in the graph, passing additional arguments if present.\n",
    "The first snapshot can be seen below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from networkx.algorithms.centrality import betweenness_centrality\n",
    "\n",
    "centrality_list = snapshotG.compute_network_statistic(betweenness_centrality)\n",
    "\n",
    "centrality_sorted = []\n",
    "unique_nodes = set()\n",
    "snapshot_list = snapshotG.get()\n",
    "for snapshot in snapshot_list:\n",
    "    for node in snapshot.nodes():\n",
    "        unique_nodes.add(node)\n",
    "\n",
    "for snapshot in centrality_list:\n",
    "    centrality_sorted.append(sorted(snapshot.items(), key=lambda x: x[1], reverse=True)+\n",
    "                             [(float(\"NaN\"), float(\"NaN\"))]*(len(unique_nodes)-len(snapshot)))\n",
    "\n",
    "print(\"{:10s}{:10s}{:10s}{:10s}{:10s}{:10s}{:10s}{:10s}\".format(\n",
    "    \"Node\", \"Year 1\", \"Node\", \"Year 2\", \"Node\", \"Year 3\", \"Node\", \"Year 4\"))\n",
    "\n",
    "for i in range(len(unique_nodes)):\n",
    "    print(\"{:<10.0f}{:0.3f}\\\n",
    "     {:<10.0f}{:0.3f}\\\n",
    "     {:<10.0f}{:0.3f}\\\n",
    "     {:<10.0f}{:0.3f}\".format(\n",
    "        *centrality_sorted[0][i], *centrality_sorted[1][i],\n",
    "        *centrality_sorted[2][i], *centrality_sorted[3][i]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Formatting Data\n",
    "\n",
    "From this point forward, we are done using DyNetworkX.\n",
    "We will finish the objective by getting ready our data to plot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_max = []\n",
    "for i in range(len(centrality_list)):\n",
    "    min_value = float(\"inf\")\n",
    "    max_value = float(\"-inf\")\n",
    "    for value in centrality_list[i].values():\n",
    "        min_value = min(min_value, value)\n",
    "        max_value = max(max_value, value)\n",
    "    min_max.append((min_value, max_value))\n",
    "        \n",
    "snapshot_list = snapshotG.get()\n",
    "\n",
    "colors = []\n",
    "\n",
    "for i in range(len(snapshot_list)):\n",
    "    colors.append([])\n",
    "    for node in snapshot_list[i]:\n",
    "        color_value = 0.75*(centrality_list[i][node] - min_max[i][0]) / (min_max[i][1] - min_max[i][0])\n",
    "        colors[i].append((1-color_value, 1-color_value, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Plotting Dynamic Betweenness Centrality\n",
    "\n",
    "Finally, plot the betweenness centrality over time using Matplotlib.animation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "from matplotlib import animation\n",
    "\n",
    "def update(i, colors, pos, snapshot_list, ax):\n",
    "    ax.clear()\n",
    "    ax.set_xlim([-1.1, 1.1])\n",
    "    ax.set_ylim([-1.1, 1.1])\n",
    "    ax.xaxis.set_visible(False)\n",
    "    ax.yaxis.set_visible(False)\n",
    "\n",
    "    nx.draw_networkx(snapshot_list[i], pos=pos, font_size=16, node_size=900, edgecolors=\"#000000\",\n",
    "                     node_color=colors[i], ax=ax)\n",
    "\n",
    "    ax.set_title(f\"Year {i+1}\", fontsize=24)\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(20, 20))\n",
    "\n",
    "staticG = nx.Graph()\n",
    "for snapshot in snapshotG:\n",
    "    for u, v in snapshot.edges():\n",
    "        staticG.add_edge(u, v)\n",
    "pos = nx.spring_layout(staticG, k=1)\n",
    "\n",
    "anim = animation.FuncAnimation(fig, update, frames=len(snapshot_list), interval=5000,\n",
    "                              fargs=(colors, pos, snapshot_list, ax))\n",
    "anim.save('betweenness.gif', writer='pillow')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(10, 10))\n",
    "\n",
    "for node in [169, 125, 82, 105]:\n",
    "    centrality = [0]*4\n",
    "    for i in range(4):\n",
    "        if node in centrality_list[i]:\n",
    "            centrality[i] = centrality_list[i][node]\n",
    "    plt.plot(range(4), centrality, label=node)\n",
    "\n",
    "plt.xticks(ticks=range(4), labels=[1, 2, 3, 4])\n",
    "plt.ylabel(\"Betweenness Centrality\", fontsize=16)\n",
    "plt.xlabel(\"Year\", fontsize=16)\n",
    "plt.legend()\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.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}