python-data-networks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Project Notebook: Network Analysis\n",
    "\n",
    "In this notebook, we will explore the analysis of network-structured data using the NetworkX package. This package makes it easy to handle and analyse network-structured data, with many standard network algorithms implemented out-of-the-box. Along the way, we'll also learn about some other helpful tools, and use a little NumPy and matplotlib.\n",
    "\n",
    "Let's start by importing NetworkX. This is a simple `import` statement.\n",
    "\n",
    "To display graphs, we will need to import matplotlib. We can do this using `import matplotlib`, but it is actually more convenient to use the command `%pylab inline`. This imports NumPy and matplotlib in a way that allows them to interface well with NetworkX within Jupyter notebooks. Note that `%pylab inline` is a Jupyter-notebooks specific command (any command starting with % is not native python and is known as a Jupyter \"magic\" command). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%pylab inline\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Working with Graphs\n",
    "\n",
    "## A first Graph object\n",
    "NetworkX is a tool for working with networks, also called _graphs_. A graph is a collection of nodes (also called vertices), which are linked by edges. An edge from vertex $v$ to vertex $w$ can be described as the pair $(v, w)$. We'll soon see how to create our own graphs, but NetworkX also has some classical graphs pre-loaded. Let's look at one of these, a graph of 15th century Florentine families. Two family nodes are linked by an edge if there was a marriage linking the families."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.florentine_families_graph()\n",
    "type(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now `G` is a Graph object. It has a set of vertices, and a set of edges, each of which we can access."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.edges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the objects `G.nodes`, `G.edges` are _views_. Like NumPy views, if we change `G` then the view is accordingly updated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nodes = G.nodes #Create a node view\n",
    "G.add_node('Corleone') #Add a sicilian family.\n",
    "nodes #The node view has changed!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get a visual feel for the data, let's remove that last node and display the graph. To create visuals, `nx` will need matplotlib."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.remove_node('Corleone') #Remove the non-Florentines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generating Graph objects\n",
    "We'll also need to know how to create our own graphs in NetworkX. We can build a graph from scratch, starting with an empty graph and adding nodes and edges - either one at a time or in groups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph()\n",
    "G.add_node(0)\n",
    "G.add_nodes_from([1, 2, 3])\n",
    "G.add_edge(0, 1)\n",
    "G.add_edges_from([(1, 2), (2, 3), (3, 0)])\n",
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's great, but quite time-consuming. We can create a graph in one step by giving `nx` a list of edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)])\n",
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "Write a function `complete_graph` that accepts an integer `n`, and returns a Graph object with `n` nodes each linked to every other node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may also create directed graphs (digraphs). In the above, our edges had no notion of direction: $(u, v)$ was viewed as the same as $(v, u)$. If we create a digraph, these two edges would be treated differently: the first linking the two edges in the direction _from_ $u$ _to_ $v$, and the second linking them in the opposite direction. Here's an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_1 = nx.Graph([('u', 'v')])\n",
    "nx.draw(G_1, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_2 = nx.DiGraph([('v', 'u')])\n",
    "nx.draw(G_2, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The other kind of graph we might want to work with is a multigraph. This is a graph where there might be multiple edges joining $u$ and $v$. There are multigraph versions of both the Graph and DiGraph classes of objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "G_3 = nx.MultiGraph([('u', 'v'), ('u', 'v')])\n",
    "G_3.edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_4 = nx.MultiDiGraph([('u', 'v'), ('v', 'u')])\n",
    "G_4.edges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a MultiGraph or MultiDiGraph, an edge is now a triple, listing the vertices joined in the first two entries and an identifier of the distinct edge in the third entry.\n",
    "\n",
    "We won't generally have cause to generate a graph from scratch, and NetworkX has [a host of graph generating functions](https://networkx.github.io/documentation/stable/reference/generators.html) available. Of particular use might be the functions for generating random graphs. For instance, we can generate a graph at random with $n$ nodes and $m$ edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.gnm_random_graph(10, 15)\n",
    "nx.draw(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All of the methods we have used for creating graphs are called _constructor_ methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "Generate [Erdos-renyi graphs](https://networkx.github.io/documentation/stable/reference/generated/networkx.generators.random_graphs.erdos_renyi_graph.html#networkx.generators.random_graphs.erdos_renyi_graph) with a fixed size, and investigate what happens to the [average clustering coefficient](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.cluster.average_clustering.html#networkx.algorithms.cluster.average_clustering) as the parameter p increases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithms for Graphs\n",
    "NetworkX has [convenient implementations](https://networkx.github.io/documentation/stable/reference/algorithms/index.html) of a range of graph algorithms covering a wealth of possible applications. For instance, [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) for finding a minimum spanning tree can be run in one line of code!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.connected_watts_strogatz_graph(50, 20, 0.5)\n",
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = nx.minimum_spanning_tree(G)\n",
    "nx.draw(T, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will see and use some more graph algorithms implemented by NetworkX in the next section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Extended Example: Email Data\n",
    "Here we have data<sup>[[1]](#snap)</sup> from an undisclosed European research institution, representing email exchanges between individuals within the institution\n",
    "\n",
    "## Loading and preparing the data\n",
    "The data represents the institution's email network. Individuals are each allocated a unique number. Each line of the file `email-Eu-core.txt` has two identifying nummbers separated by a space, e.g. `n m`, denoting that person $n$ sent an email to person $m$.\n",
    "\n",
    "We want to analyse this data as an undirected graph. To read the data in, create a list called `edges`, and fill it by reading the file line by line, using the string utility function `.split()` to create tuples representing edges. The pass this list to the `nx` constructor for digraphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The institution is organised into 42 departments, each of which is assigned a unique identifying number. Each line of the file `email-Eu-core-department-labels.txt` has an individual's identifier, followed by the number identifying their department after a space. Open this file and create a dictionary mapping individuals to their departments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A graph may be connected or disconnected. An undirected graph is connected if any node can reach any other by walking through a sequence of edges: otherwise it is disconnected. \n",
    "\n",
    "Use the methods `nx.is_connected` to check if the graph is connected. If it is not, obtain the subgraph which is the largest connected component - nodes not in this component will be treated as outliers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithms for connectedness\n",
    "We can find the member of this graph which has a high level of influence using an algorithm called _pagerank_. We treat an edge directed inwards towards a node as a reccommendation of that node's importance. These reccommendations are weighted by the importance of the reccommending nodes. That may sound circular, but in fact, clever linear algebra allows us to easily compute a score based on this measure of \"importance\". This is the pagerank of a graph. \n",
    "\n",
    "The method `nx.pagerank` will return a dictionary mapping nodes to their respective ranking. Use this to find out which member of the institution has the highest pagerank!\n",
    "\n",
    "(Side note: if we consider the graph of the world wide web, where nodes are pages and edges are hyperlinks betweenn them, then pagerank denotes the \"best\" or \"most important\" webpage. The algorithm was developed by google to help rank search results, and is still used today whenever you erform a google search!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you use `G.degree`, you will see that the highest scoring node by pagerank is not simply the most well-connected node! (Degree of a node is the number of nodes it is connected to by an edge)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try to draw the graph of the department that person `160` belongs to. Use your dictionary of department membership to find the nodes which are in the same department as `160`, and then use `nx.subgraph` to produce the graph just containing these nodes. When you draw this subgraph, you might want to experiment with the `node_color` argument to see if you can highlight member `160`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another graph property we might be interested in is which edges are bridges. A bridge is an edge which, if removed, would disconnect the graph. Using `nx.bridges`, find out how many bridges this graph has. How many bridges occur within a department? Does the node with the highest pagerank belong to a department which also contains a bridge?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The identification of bridges could be useful in, for instance, strategic planning. The help us identify network vulnerabilities, in this case, edges which are crucial to the connectivity of the network. A planner might identify bridges, and investigate which interactions they represent to find ways of strengthening or developing connections in the network.\n",
    "\n",
    "Som community detection algorithms rely on bridge detection. The [Girvan-Newman](https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm) algorithm involves detecting edges which are bridges, or edges which are a lot like bridges, and successively removing them. This slowly disconnects the graph, grouping nodes into communities based on the connected components they end up in. Since many of the departments contain bridges, this method would fail to preserve departmental communities. That may or may not be bad, but it's something we should be aware of.\n",
    "\n",
    "If we have ground-truth data for a network, or another network which we believe to have similar structure, we can perform simple checks like the one above to determine whether a given algorithm is likely to give us useful information."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Degree Distribution\n",
    "How will we know when two networks have a similar structure? There is no simple answer to this question. In the below activity, we'll try to figure out how much like a social network this email network is.\n",
    "\n",
    "One property that has been observed in some social networks is scalefree structure. This is indicated by plotting the degree distribution of the graph. For every possible degree, we can obtain the number of nodes in the graph with this degree. This data is called the _degree distribution_ of the graph. We can make a plot degree versus the number of nodes observed with this degree in a log-log plot, then if the points lie in a line this indicates a scalefree structure.\n",
    "\n",
    "In the example below, we calculate the degree distribution from a graph randomly generated using the Barabasi-Albert method, which was designed to produce scalefree networks. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "#Generate graph\n",
    "B_A_graph = nx.barabasi_albert_graph(10000, 50)\n",
    "\n",
    "#Get a list of node degrees\n",
    "deg_list = list(dict(B_A_graph.degree()).values())\n",
    "\n",
    "#Use a Counter to total the occurrences of each degree.\n",
    "from collections import Counter\n",
    "counts = Counter(deg_list)\n",
    "degs = list(counts.keys())\n",
    "freqs = list(counts.values())\n",
    "\n",
    "#Take logs and scatter.\n",
    "x = log(degs)\n",
    "y = log(freqs)\n",
    "scatter(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The top end of the above looks quite linear, while the lower end is a bit splayed out. This is characteristic of a small scalefree network.\n",
    "\n",
    "In the above code, we used the inbuild `nx` method to obtain a dictionary-like structure mapping nodes to their degree (for technical reasons, custom libraries like `nx` often have their own versions of standard data structures). Casting this to a regular python dict, we can obtain the values and then cast these again to a list!\n",
    "\n",
    "We then used the Counter object. Calling a Counter on a list will produce a dict mapping unique entries of the list to their frequency in the list.\n",
    "\n",
    "Finally, we used `numpy.log` and `matlpolib.pyplot.scatter` to obtain a log-log plot. Note that we were able to call these using just `log` and `scatter`. This is a feature of having used `%pylab inline`, which means the functions in `numpy` and `matplotlib.pyplot` are callable at the top level.\n",
    "\n",
    "By eyeballing the graph above, we can say that the data looks like it falls into a line. We can make this precise using Pearson's correlation coefficient (PCC). A coefficient value near $\\pm1$ suggest the data are strongly correlated (are a lot like a line), while a value near zero suggests weak correlation. The PCC is implemented in `numpy`. The method `numpy.corrcoef` called with two data sets `x` and `y` returns a matrix sowing their correlation. The PCC of `x` with `y` is in any non-diagonal element of this matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "corrcoef(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we can see that `x, y` have a fairly good negative correlation. This formalises out notion of the extent to which `x, y` lie on a downwardly sloping line.\n",
    "\n",
    "Now try plotting the degree distribution of `G`. Do you think this suggests a scale-free structure? Comare this to a [barabasi-albert graph](https://networkx.github.io/documentation/stable/reference/generated/networkx.generators.random_graphs.barabasi_albert_graph.html#networkx.generators.random_graphs.barabasi_albert_graph) with the same number of nodes as G. You should set the parameter `m` to be the average degree of a node in `G`.\n",
    "\n",
    "Try the same for the subraph you obtained of a single department of the institution. Is this more or less like a social network? Do you think size matters?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "1. Data obtained from _SNAP Datasets: Stanford Large Network Dataset Collection_, Jure Leskovec and Andrej Krevl 2014, http://snap.stanford.edu/data, accessed Jan 2019.<a name=\"snap\"></a>"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}