04_ML_on_graphs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine Learning on graphs\n",
    "Here we review some simple yet powerful machine learning on graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "import community as community_louvain\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Clustering and community detection (unsupervised learning)\n",
    "Many real-world networks posesses communities, groups of nodes that are more connected together than with the rest of the network. Detecting these structures is of high importance. It reveals the hierarchy, the organization and interactions between nodes. It helps classifying parts of a network into categories. It can be seen as an equivalent of the unsupervised learning `k-means` clustering algorithm. Instead of computing distances and grouping data points in a high dimensional space, we use the network structure to detect the clusters.\n",
    "\n",
    "Many methods exists for community detection, see for example [this review](https://arxiv.org/abs/0906.0612). We will see two of them. The first one is available in `networkx`, the second one is the popular Louvain method which allows for fast computation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Girvan Newman algorithm\n",
    "The [GN algorithm](https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm) remove edges between communities in an iterative manner. The edges removed are the ones with the highest number of shortest paths passing through them (\"bottlenecks\" between communities). The idea is clear and intuitive. However, the computation is intensive as all shortest paths have to be computed. Moreover, the number of communities has to be specified as this algorithm do not have a stopping criterium (this can be an advantage or drawback)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Girvan Newman clustering\n",
    "G = nx.path_graph(8)\n",
    "\n",
    "num_clusters = 5 # desired number of clusters\n",
    "k = num_clusters - 1\n",
    "\n",
    "comp = nx.algorithms.community.centrality.girvan_newman(G)\n",
    "\n",
    "comp = list(comp)\n",
    "for idx in range(k):\n",
    "    print(' {} communities: {}'.format(idx+2, comp[idx]))\n",
    "\n",
    "# Alternative way using directly the generator\n",
    "#import itertools\n",
    "#for idx,communities in enumerate(itertools.islice(comp, k)):\n",
    "#    print(' {} communities: {}'.format(idx+2, tuple(sorted(c) for c in communities)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "* Apply it with a more complex network and visualize the communities using Gephi. (See [graph list in networkx](https://networkx.org/documentation/stable/reference/generators.html), you may test on the \"Karate club\" graph or \"Les Miserables\" graph)\n",
    "* Try a larger network and experience the limit of scalability. What is a reasonable number of nodes for this method?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Louvain community detection\n",
    "\n",
    "Community detection with Louvain method. You have to install an external module: `pip install louvain`, see [module Github page](https://github.com/taynaud/python-louvain) for more info or the [paper](https://arxiv.org/abs/0803.0476). This method is much more efficient than the previous one. It is a greedy, non-parametric, algorithm that finds automatically the optimal number of communities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Louvain module is called \"community\"\n",
    "partition = community_louvain.best_partition(G)\n",
    "#community_louvain.modularity(partition, G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`partition` is a dictionary where each node id is a key and its community is the value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# re-order partition to have a dictionary of clsuters\n",
    "clusters = {}\n",
    "for i, v in partition.items():\n",
    "    clusters[v] = [i] if v not in clusters.keys() else clusters[v] + [i]\n",
    "print(clusters)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Label propagation (Semi-supervised learning)\n",
    "In this approach, the graph structure is combined to values (or feature vectors) associated to the nodes. Missing node values are found by propagating the known values to their neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = nx.normalized_laplacian_matrix(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use label spreading from this [publication](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.3219) which perform a smoothing of the labels over the graph. We assume 2 classes with one-hot-encoding,i.e. feature vectors on nodes have dimension 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# labels\n",
    "labels = np.zeros((L.shape[0],2))\n",
    "labels[1,0] = 1 # node 1 has first label  \n",
    "labels[5,1] = 1 # node 5 has second label\n",
    "print(labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def labelSpreading(G, labels, alpha, tol=1e-3):\n",
    "    L = nx.normalized_laplacian_matrix(G)\n",
    "    S = np.identity(L.shape[0]) - L.toarray()\n",
    "    max_iter = 1000\n",
    "    Y = np.zeros(labels.shape)   \n",
    "    for i in range(max_iter):\n",
    "        Y_tmp = Y.copy()\n",
    "        Y = alpha * np.dot(S, Y) + (1 - alpha) * labels\n",
    "        if np.linalg.norm(Y-Y_tmp) < tol:\n",
    "            print('Converged after {} iterations.'.format(i))\n",
    "            break\n",
    "    return Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "smooth = labelSpreading(G,labels, 0.9)\n",
    "print(labels)\n",
    "print(smooth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us plot the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pos = nx.spring_layout(G, iterations=200)\n",
    "\n",
    "plt.figure(figsize=(14, 6))\n",
    "ax1 = plt.subplot(1, 2, 1)\n",
    "ax2 = plt.subplot(1, 2, 2)\n",
    "#ax3 = plt.subplot(1, 4, 3)\n",
    "nx.draw(G, pos=pos, ax=ax1, node_color=smooth[:,0],  cmap=plt.cm.Blues)\n",
    "nx.draw(G, pos=pos, ax=ax2, node_color=smooth[:,1],  cmap=plt.cm.Blues)\n",
    "\n",
    "ax1.title.set_text(\"Smoothing of class 1 over the network\")\n",
    "ax2.title.set_text(\"Smoothing of class 2 over the network\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "propagated_labels = np.argmax(smooth,axis=1)\n",
    "#label_dic = {k:v for k,v in enumerate(propagated_labels)}\n",
    "print(propagated_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G, pos=pos, node_color=propagated_labels,  cmap=plt.cm.Blues)\n",
    "plt.title(\"Final classification\")\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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}