community_detection.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Graph\" data-toc-modified-id=\"Graph-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Graph</a></span></li><li><span><a href=\"#Comunity-detection\" data-toc-modified-id=\"Comunity-detection-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Comunity detection</a></span></li><li><span><a href=\"#Visualization\" data-toc-modified-id=\"Visualization-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Visualization</a></span></li><li><span><a href=\"#Further-analysis\" data-toc-modified-id=\"Further-analysis-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Further analysis</a></span></li><li><span><a href=\"#Karate-club-library\" data-toc-modified-id=\"Karate-club-library-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Karate club library</a></span><ul class=\"toc-item\"><li><span><a href=\"#Graph\" data-toc-modified-id=\"Graph-5.1\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span>Graph</a></span></li><li><span><a href=\"#Algorithm\" data-toc-modified-id=\"Algorithm-5.2\"><span class=\"toc-item-num\">5.2&nbsp;&nbsp;</span>Algorithm</a></span></li><li><span><a href=\"#Evaluation\" data-toc-modified-id=\"Evaluation-5.3\"><span class=\"toc-item-num\">5.3&nbsp;&nbsp;</span>Evaluation</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Community detection in network graph\n",
    "\n",
    "In this notebook we want to detect communtiy in network graphs. \n",
    "\n",
    "First, we import all necessary modules.\n",
    "\n",
    "- `networkx`, `karateclub`: community detection algorithms\n",
    "- `matplotlib`: visualization.\n",
    "- `ipywidgets`: interactive features  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "from networkx.algorithms.community.centrality import girvan_newman\n",
    "from networkx.algorithms import community\n",
    "from karateclub import EgoNetSplitter\n",
    "import itertools\n",
    "\n",
    "from ipywidgets import interact, interactive, fixed, interact_manual\n",
    "import ipywidgets as widgets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph\n",
    "\n",
    "First, we load a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# see https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.social.karate_club_graph.html\n",
    "\n",
    "G = nx.karate_club_graph()\n",
    "print(G.edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# graph information\n",
    "\n",
    "print(\"count nodes:\" , len(G.nodes))\n",
    "print(\"count edges:\" , len(G.edges))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we can draw the graph to get an impression on how it looks like."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig=plt.figure(figsize=(18, 16), dpi= 80, facecolor='w', edgecolor='k')\n",
    "nx.draw_spring(G, with_labels=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comunity detection\n",
    "\n",
    "We use the Girvan-Newman algorithm to detect communities:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Girvan-Newman algorithm\n",
    "communities = girvan_newman(G)\n",
    "\n",
    "# save results in a list, each element of the list consists of the communities on one level. \n",
    "# necessary to use the interactive slider\n",
    "\n",
    "com_lvl_lst = [] \n",
    "for com_on_lvlk in itertools.islice(communities, len(G.nodes)):\n",
    "    com_lvl_lst.append(com_on_lvlk)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have a list of the communities on each level.\n",
    "\n",
    "Since the algorithm is a hierarchical method and terminates when no edges remain, we have to choose the level ourselves.\n",
    "\n",
    "For a small graph, we can visualize the results and have a \"sharp look\" which community structures fits best.\n",
    "\n",
    "## Visualization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_communities_per_lvl(c,k):\n",
    "    return c[k]\n",
    "def draw_communities(c, k):\n",
    "    communities = get_communities_per_lvl(c,k)\n",
    "    values = [0]*len(G.nodes)\n",
    "    for i,lst in enumerate(communities):\n",
    "        for el in lst:\n",
    "            values[el]=i   \n",
    "    fig=plt.figure(figsize=(18, 16), dpi= 80, facecolor='w', edgecolor='k')\n",
    "    nx.draw_networkx(G, cmap = plt.get_cmap('jet'), node_color = values,  with_labels=True)\n",
    "    return values\n",
    "\n",
    "# use a slider to see the different levels of the community structures\n",
    "w = interactive(draw_communities,c=fixed(com_lvl_lst), k=(0, len(G.nodes)-2, 1))\n",
    "display(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Further analysis\n",
    "\n",
    "\n",
    "Sometimes it is interesting how communities are connected to each other. To get an overview, we merge all nodes of one community to one new community node and add an edge between two community nodes if at least one pair of nodes from two community nodes are connected by an edge in the original graph.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_merged = nx.Graph()\n",
    "classified_nodes = w.result\n",
    "\n",
    "community_count = len(set(classified_nodes))\n",
    "# print(community_count)\n",
    "for n in G.edges:\n",
    "    node_1 = classified_nodes[n[0]]\n",
    "    node_2 = classified_nodes[n[1]]\n",
    "    G_merged.add_edge(node_1, node_2)\n",
    "# print(G.edges)\n",
    "# print(G_merged.edges)\n",
    "fig=plt.figure(figsize=(18, 16), dpi= 80, facecolor='w', edgecolor='k')\n",
    "nx.draw_spring(G_merged, node_color = range(0,community_count),with_labels=True)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Karate club library\n",
    "\n",
    "Before, we have used only the `networkx` library. The `karateclub` library has advanced algorithms.\n",
    "Let's try it out with a bigger graph.\n",
    "\n",
    "see: https://github.com/benedekrozemberczki/karateclub\n",
    "\n",
    "### Graph\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from karateclub import GraphReader\n",
    "\n",
    "reader = GraphReader(\"facebook\")\n",
    "\n",
    "graph = reader.get_graph()\n",
    "target = reader.get_target()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"count nodes:\" , len(graph.nodes))\n",
    "print(\"count edges:\" , len(graph.edges))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph consists of 22470 nodes and 171002 edges. This is why we can not visualize the graph, as it is too large.\n",
    "\n",
    "\n",
    "### Algorithm\n",
    "\n",
    "In the following we use the Label propagation algorithm to detect communities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from karateclub import LabelPropagation\n",
    "\n",
    "model = LabelPropagation()\n",
    "model.fit(graph)\n",
    "cluster_membership = model.get_memberships()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluation\n",
    "\n",
    "The nodes are already classified into communities. The labels are stored in the variable `target`.\n",
    "With this information, we can compare our prediction with the labels using the normalized mutual information score, which computes the correlation between two clusters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "\n",
    "cluster_membership = [cluster_membership[node] for node in range(len(cluster_membership))]\n",
    "\n",
    "nmi = normalized_mutual_info_score(target, cluster_membership)\n",
    "print('NMI: {:.4f}'.format(nmi))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO: \n",
    "- Add different algorithms.\n",
    "- Add measures (how \"good\" is the community detection\"? How can you measure it?)\n",
    "- Use \"real-world\" example (facebook data / metadata / coauthorship)\n",
    "- Use karate club library and try out one of the machine learning algorithms\n",
    "- Color communities and its nodes in same color in both graphs."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}