tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Load libraries\n",
    "\n",
    "It's the start of everything\n",
    "\n",
    "Make sure you have NetworkX version 2.1 or newer installed. Otherwise you can install it with `pip install --upgrade networkx` or if you are using Anaconda `conda install networkx`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import networkx as nx\n",
    "\n",
    "print(nx.__version__)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Loading the data and creating the network\n",
    "\n",
    "Loading data in networkX is very straightforward. In the most basic case, you only have to provide a NetworkX with a list of edges, and the package will automatically create the nodes and connect them with an edge.\n",
    "\n",
    "As the first example, we will load and play around with data extracted from email data from a large European research institution [1,2]. The data is stored in the *email-Eu-core.txt* file in the data directory.\n",
    "\n",
    "Fist, we use pandas to load the txt file into a DataFrame\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "network_data_frame = pd.read_csv('data/email-Eu-core.txt', sep=' ', header = None)\n",
    "network_data_frame.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here each row represents an edge between its two elements.\n",
    "\n",
    "Now we initialize the network as an object of the **Graph** class in NetworkX (if you are not familiar with the object-oriented paradigm, don't worry too much about the technicalities).\n",
    "\n",
    "Then we can use the **add_edges_from** method to create the graph, by just supplying it with a list of edges.\n",
    "\n",
    "Obs: In this example, the nodes are numbered, but it is also possible to work with named nodes, just provide the edge list as pairs of strings. Also, if you are working with a **directed graph**, you will need to use the **Digraph** class, and in this case the order in which you provide the edges information matters, as it reads the pairs of nodes as [from, to]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "network = nx.from_pandas_edgelist(network_data_frame, source = 0, target = 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's display the network to see what it looks like. This can be done with the **draw** function. \n",
    "\n",
    "There are many ways in which a graph can be displayed. By default, the **draw** function uses a so-called [force-directed graph drawing](https://en.wikipedia.org/wiki/Force-directed_graph_drawing) to position the nodes, and this might take a bit of time to calculate. There are other functions like **draw_circular** or **draw_random** that use other techniques.\n",
    "\n",
    "(bellow also use a few parameters to make the graph look more pleasant, like *node_size* and *edge_color*. They are optional)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(network, node_size = 10, edge_color = 'gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Connected components\n",
    "\n",
    "The force-directed display makes it easy to see that the graph is a bit fragmented (weirdly, some people only email themselves), and we are really only interested in the core of the graph. \n",
    "\n",
    "This is a great opportunity to use the **connected_components** function. As the name suggests, it returns all the **subgraphs** consisting of nodes that are connected by any **path**.\n",
    "\n",
    "Here it is also good to note that this function, and many others in NetworkX, returns a [generator](https://wiki.python.org/moin/Generators) object. Again if you are not familiar with the concept, don't worry, just know that you have to transform it to a list to get the results, and this is when most of the computation is done."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "parts_generator = nx.connected_components(network)\n",
    "\n",
    "parts = list(parts_generator)\n",
    "parts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we have a list of **sets**, showing the big subgraph at first, followed by some lonely nodes. \n",
    "\n",
    "Now let's exclude the smaller subgraphs' nodes. For this, we will use the method **remove_nodes_from**, and provide it with a list of the nodes to be removed.\n",
    "\n",
    "(the first line of code bellow converts the list of sets to a list of integers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "singles = [list(x)[0] for x in parts[1:]]\n",
    "\n",
    "network.remove_nodes_from(singles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nx.draw(network, node_size = 5, edge_color = 'gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks better!\n",
    "\n",
    "Now we can begin analysing this network.\n",
    "\n",
    "## Node degree\n",
    "\n",
    "Let's look at the node [degree](https://en.wikipedia.org/wiki/Degree_(graph_theory)) distribution of the graph as it is usually very informative of the type of graph we are looking at.\n",
    "\n",
    "This can be accessed on the **degree** attribute of the Graph, and it outputs an object that contains the degree of every node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "network.degree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us extract only the values from this and display them in a histogram."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degree_list = [d for n, d in network.degree]\n",
    "\n",
    "plt.hist(degree_list)\n",
    "plt.show()\n",
    "\n",
    "np.mean(degree_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obs: a power law distribution like this indicated that the network was probably formed through [preferential attachment](https://en.wikipedia.org/wiki/Preferential_attachment).\n",
    "\n",
    "## Clustering coefficient\n",
    "\n",
    "Another informative metric is the [clustering coefficient](https://en.wikipedia.org/wiki/Clustering_coefficient) of the nodes. This coefficient gives us an idea of how densely the network is connected around each node. \n",
    "\n",
    "We use the function **clustering** for this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "clustering_coeff = nx.clustering(network)\n",
    "clustering_coeff"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, let's look at the distribution and the mean clustering coefficient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(list(clustering_coeff.values()))\n",
    "plt.show()\n",
    "\n",
    "np.mean(list(clustering_coeff.values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Average shortest path length\n",
    "\n",
    "Now we could start to look at metrics concerning how all the nodes are connected.\n",
    "\n",
    "As the name suggests, a \"shortest path length\" between nodes *a* and *b* is the minimum number of steps you need to take to reach *b* from *a*. The average shortest path is then taken between all node combinations. \n",
    "\n",
    "This gives you another metric for how well-connected the network is.\n",
    "\n",
    "Obs: You might think that this would take a long time to calculate, but clever **dynamic programming** technique allows this to be done with much fewer computations.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_shortest_path_length(network)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diameter\n",
    "\n",
    "The diameter of a network is its maximum shortest path length among any nodes in the network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.diameter(network)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Maximum cliques\n",
    "\n",
    "We can also find the **maximum cliques** in the network using the **find_cliques** function. A maximum clique is one that is not a subset of any other larger clique. Beware that in large networks there can be a very large number of them!\n",
    "Let's see how many of them we have here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cliques = nx.find_cliques(network)\n",
    "len(list(cliques))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth and Breath first search\n",
    "\n",
    "These are two [**graph traversal**](https://en.wikipedia.org/wiki/Graph_traversal) algorithms, and they differ in their approach to the traversal.\n",
    "\n",
    "There are many [functions](https://networkx.github.io/documentation/stable/reference/algorithms/traversal.html) on NetoworkX dealing with traversal, but let's use the **dfs_tree** and **bfs_tree** functions, which output the **tree objects** resulting from the paths taken by the traversal algorithms. Let us create those trees and draw them.\n",
    "\n",
    "Note that to perform the traversal we have to specify the starting (or root) node, I'll choose node 0 to start with."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = nx.dfs_tree(network, 0)\n",
    "nx.draw(tree, node_size = 5, edge_color = 'gray')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = nx.bfs_tree(network, 0)\n",
    "nx.draw(tree, node_size = 5, edge_color = 'gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see they look very different, but don't judge them by their looks, we have now many quantitative tools to analyse them.\n",
    "\n",
    "* What do you expect from their diameters?\n",
    "* What about their number of cliques and clustering coefficient?\n",
    "* And their degree distribution?\n",
    "\n",
    "## Minimum spanning tree\n",
    "\n",
    "A **spanning tree** is a **tree** made of a subset of the graph edges that connects all nodes with the minimum number of edges possible.\n",
    "\n",
    "Let's create a minimum spanning tree for this network and see what it looks like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = nx.minimum_spanning_tree(network)\n",
    "\n",
    "nx.draw(tree, node_size = 5, edge_color = 'gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Community detection\n",
    "\n",
    "Communities in a network are very loosely defined as groups of nodes that are very well-connected within themselves but not between themselves.\n",
    "\n",
    "With such a loose definition, many algorithms exist each with its own interpretation of what a community is.\n",
    "\n",
    "Here will use the [Girvan–Newman](https://en.wikipedia.org/wiki/Girvan–Newman_algorithm) algorithm as an example, and it is based on the concept of [edge betweenness](https://en.wikipedia.org/wiki/Betweenness_centrality) and provides a hierarchy of communities.\n",
    "\n",
    "It is good to note here that most community detection algorithms have a high complexity and so it might take a long time to run in a large network, so we will switch to a much smaller network as an example.\n",
    "\n",
    "The **karate_club_graph** function in NetworkX loads this example network, let's look at it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "community_network = nx.karate_club_graph()\n",
    "nx.draw(community_network)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Much simpler! \n",
    "\n",
    "Now let's run the community detection algorithm and see what happens. The Girvan–Newman algorithm, together with the other community detection algorithms, are hidden in the **algorithms.community** module of NetworkX."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "partitions = nx.algorithms.community.girvan_newman(community_network)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can see how the partitions look like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "part_list = list(partitions)\n",
    "part_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can see there are many levels of the hierarchical structure, and a list of all the nodes in each community at every level.\n",
    "\n",
    "Let's try to visualize them in the network by colouring the nodes according to their corresponding community. I'll choose to go with the fourth level for this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "communities = part_list[3]\n",
    "communities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But first, we need to do a trick to convert this list of which node belongs to which community to a list of what is the community of each node. A bit confusing, but once this is done we can tell NetworkX's **draw** function to colour each node with the colour corresponding to their community.\n",
    "\n",
    "Let's see how this looks like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "colors = np.zeros(nx.number_of_nodes(community_network))\n",
    "\n",
    "for i in range(len(communities)):\n",
    "    nodes = list(communities[i])\n",
    "    for j in range(len(nodes)):\n",
    "        colors[nodes[j]] = i\n",
    "\n",
    "nx.draw(community_network, node_color = colors, cmap=plt.cm.Set1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ... and much more\n",
    "\n",
    "Network analysis is a very broad field and we here only mentioned a few of the tools available to you. \n",
    "For instance, NetworkX has an [implementation](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html) of Google's own [PageRank](https://en.wikipedia.org/wiki/PageRank) algorithm that you could use to analyse the importance of every node in the network.\n",
    "\n",
    "If you want to learn more of what NetworkX has to offer, you can [read the docs](https://networkx.github.io/documentation/stable/reference/index.html).\n",
    "\n",
    "# The task\n",
    "\n",
    "In the data/ directory, there are three files (N1.txt, N2.txt, N3.txt) that represent three different networks (all are undirected and unweighted). \n",
    "\n",
    "One is a social network of email exchanges at a Spanish university [3], one is the Western States power grid [4], and one is (the largest cluster of) the protein interaction network in yeast [5].\n",
    "\n",
    "Your task now is to use the tools to decide which network corresponds to which file. The more information you gather to support your conclusions, the better.\n",
    "\n",
    "# And maybe a practical one\n",
    "\n",
    "If you work with any kind of data that has a network structure, try to load it into NetworkX, display it and look at its statistics.\n",
    "\n",
    "As an example, you may be interested in [SpringDB](https://string-db.org/).\n",
    "\n",
    "# Or maybe a more advanced one\n",
    "\n",
    "The first network we looked at has a ground-truth for the communities, as we know which department each of the nodes belongs to. This information can be found in the *email-Eu-core-department-labels.txt* file.\n",
    "This means that it can be used to benchmark community detection algorithms.\n",
    "\n",
    "Always beware of the complexity of the algorithms you are using. Try to find it out before running them, and see if it applies to a network of the size you are using.\n",
    "\n",
    "[This article](https://www.nature.com/articles/srep30750) has a very good review many community detection algorithms (Figure 7 is specially informative).\n",
    "\n",
    "* You may choose to test NetworkX many [community detection algorithms](https://networkx.github.io/documentation/stable/reference/algorithms/community.html).\n",
    "* You can try to install and use [this Python package](https://github.com/taynaud/python-louvain) that is a plug-in to NetworkX and implements the [Louvain method](https://en.wikipedia.org/wiki/Louvain_Modularity).\n",
    "* You could also use [IGraph](http://igraph.org/) which has a Python, C and R packages, is very fast and has many more community detection algorithm implementations. It is a bit less intuitive to use than NetworkX in Python, but also very powerful.\n",
    "\n",
    "\n",
    "### References\n",
    "\n",
    "\n",
    "[1] Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. \"Local Higher-order Graph Clustering.\" In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017.\n",
    "\n",
    "[2] J. Leskovec, J. Kleinberg and C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007.\n",
    "\n",
    "[3] R. Guimer, L. Danon, A. Daz-Guilera, F. Giralt, and A. Arenas. Self-similar community structure in a network of human interactions. Physical Review E, 68(6):065103, December 2003.\n",
    "\n",
    "[4] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, June 1998.\n",
    "\n",
    "[5] H. Jeong, S. P. Mason, A.-L. Barabasi, and Z. N. Oltvai. Lethality andcentrality in protein networks. Nature, 411(6833):41–42, May 2001.\n"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}