Week7_networks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Networks "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lab you'll do some exercises to familiarise yourself with network properties and concepts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "from collections import Counter\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1(a):**\n",
    "\n",
    "This exercise is to do by hand, on paper. Given the undirected graph drawn below, write down the adjacency matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/small_graph_undirected.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1(b):**\n",
    "\n",
    "This exercise is to do by hand, on paper. Given the directed graph drawn below, write down the adjacency matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/small_graph_directed.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2:**\n",
    "\n",
    "Create the above graphs in networkx (or just in your own data structure if you prefer, but this will make the exercise harder). Draw them with the below code to make sure your graphs have the same structure as the diagrams above. Code is given to compute the adjacency matrix with networkx, to check your own adjacency matrices from Exercise 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define as a networkx object and add nodes/edges\n",
    "graphA = #???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define as a networkx object and add nodes/edges\n",
    "graphB = #???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_spring(graphA, with_labels=True, node_size=1200, node_color='#eeeeff', edge_color='red')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.adjacency_matrix(graphA)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(nx.adjacency_matrix(graphA))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(graphA.nodes())\n",
    "nx.to_numpy_matrix(graphA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part (b):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_spring(graphB, with_labels=True, node_size=1200, node_color='#eeeeff', edge_color='red')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the adjacency matrix for your `graphB` as above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3:**\n",
    "\n",
    "Complete the function below to find the degree distrbution for any given graph. You can use the networkx method `graph.degree()`, which returns the number of edges connecting to each node. You should return a tuple of two lists: the first list contains all observed vertex degree values in the graph, and the second contains the counts showing how often a vertex with that degree was observed.\n",
    "\n",
    "For instance, calling `degree_distribution()` on `graphA` above could return\n",
    "\n",
    "```([1, 2, 3], [1, 2, 1])```\n",
    "\n",
    "meaning that there is one vertex with degree 1 (D), two vertices with degree 2 (A and B), and one vertex with degree 3 (C).\n",
    "\n",
    "These two lists will give us a handy form for plotting the degree distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 141,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's the networkx function `graph.degree()`:\n",
    "graphA.degree('C')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def degree_distribution(graph):\n",
    "    \"\"\"\n",
    "    For the networkx graph provided, return a tuple of lists, where\n",
    "    the first list gives all observed vertex degrees, and the second list gives\n",
    "    the corresponding vertex counts.\n",
    "    \"\"\"\n",
    "    # Complete this function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have this function, you can draw the degree distribution with a scatter plot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x15180b9ef0>"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAD8JJREFUeJzt3W2MXFd9x/Hvr7ahhqQ4wVuaOHFNJeqWACHpFlKgrRFSHVJoAFEpKeIhAllq0wqkyqLhBVHhBaqsVhQhsCyIQioaQMW4FAEmUqGpmiZ0nYQ4ITV1Ex5sR7VD6vAQq43Nvy9mXNab3Z3Z3bsz66PvRxrtnXPP3vv30dmf79yH3VQVkqS2/My4C5Akdc9wl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDVo9bh2vH79+tq0adO4di9JZ6V9+/Y9WlUTg/qNLdw3bdrE1NTUuHYvSWelJN8Zpp+nZSSpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJatDAcE9ycZKvJnkwyQNJ3jlLnyT5UJKDSe5LcvnylCtJGsYwDzGdBP60qu5Oci6wL8ltVfXNaX1eDTyv/3op8NH+V+mssueew+zYe4Ajx09w4bq1bN+6mdddtmHcZUkLNvDIvaoeqaq7+8s/BB4EZs72q4FbqudOYF2SCzqvVlpGe+45zA2793P4+AkKOHz8BDfs3s+eew6PuzRpwRZ0zj3JJuAy4K4ZqzYA35v2/hBP/Q9AWtF27D3AiSdPndF24slT7Nh7YEwVSYs3dLgnOQf4LPCuqvrBzNWzfEvNso1tSaaSTB07dmxhlUrL7MjxEwtql1ayocI9yRp6wf7Jqto9S5dDwMXT3l8EHJnZqap2VdVkVU1OTAz8pWbSSF24bu2C2qWVbJi7ZQJ8HHiwqv5qjm6fB97Sv2vmCuDxqnqkwzqlZbd962bWrll1RtvaNavYvnXzmCqSFm+Yu2VeDrwZ2J/k3n7be4CNAFW1E/gicBVwEHgCuK77UqXldfquGO+WUQtS9ZRT4yMxOTlZ/j53SVqYJPuqanJQP59QlaQGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0aGO5JbkpyNMn9c6x/VpJ/SPKNJA8kua77MiVJCzHMkfvNwJXzrL8e+GZVXQpsAf4yydOWXpokabEGhntV3Q48Nl8X4NwkAc7p9z3ZTXmSpMXo4pz7h4FfBY4A+4F3VtVPZuuYZFuSqSRTx44d62DXkqTZdBHuW4F7gQuBFwMfTvJzs3Wsql1VNVlVkxMTEx3sWpI0my7C/Tpgd/UcBB4GfqWD7UqSFqmLcP8u8CqAJM8BNgMPdbBdSdIirR7UIcmt9O6CWZ/kEHAjsAagqnYC7wduTrIfCPDuqnp02SqWJA00MNyr6toB648Av9NZRZKkJfMJVUlqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBg0M9yQ3JTma5P55+mxJcm+SB5L8U7clSpIWapgj95uBK+damWQd8BHg96rqEuD3uylNkrRYA8O9qm4HHpunyx8Au6vqu/3+RzuqTZK0SF2cc/9l4LwkX0uyL8lbOtimJGkJVne0jV8DXgWsBf41yZ1V9a2ZHZNsA7YBbNy4sYNdS5Jm08WR+yHgy1X146p6FLgduHS2jlW1q6omq2pyYmKig11LkmbTRbj/PfCbSVYneQbwUuDBDrYrSVqkgadlktwKbAHWJzkE3AisAaiqnVX1YJIvA/cBPwE+VlVz3jYpSVp+A8O9qq4dos8OYEcnFUmSlswnVCWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDBoZ7kpuSHE1y/4B+v57kVJI3dleeJGkxhjlyvxm4cr4OSVYBfwHs7aAmSdISDQz3qrodeGxAtz8BPgsc7aIoSdLSLPmce5INwOuBnUP03ZZkKsnUsWPHlrprSdIcurig+kHg3VV1alDHqtpVVZNVNTkxMdHBriVJs1ndwTYmgU8lAVgPXJXkZFXt6WDbkqRFWHK4V9VzTy8nuRn4gsEuSeM1MNyT3ApsAdYnOQTcCKwBqKqB59klSaM3MNyr6tphN1ZVb1tSNZKkTviEqiQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwaGe5KbkhxNcv8c69+U5L7+644kl3ZfpiRpIYY5cr8ZuHKe9Q8Dv11VLwLeD+zqoC5J0hKsHtShqm5Psmme9XdMe3sncNHSy5IkLUXX59zfDnyp421KkhZo4JH7sJK8kl64v2KePtuAbQAbN27sateSpBk6OXJP8iLgY8DVVfX9ufpV1a6qmqyqyYmJiS52LUmaxZLDPclGYDfw5qr61tJLkiQt1cDTMkluBbYA65McAm4E1gBU1U7gvcCzgY8kAThZVZPLVbAkabBh7pa5dsD6dwDv6KwiSdKS+YSqJDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJatDqQR2S3AS8BjhaVS+YZX2AvwauAp4A3lZVd3dd6HR77jnMjr0HOHL8BBeuW8v2rZt53WUblnOXkrRo48isYY7cbwaunGf9q4Hn9V/bgI8uvay57bnnMDfs3s/h4yco4PDxE9ywez977jm8nLuVpEUZV2YNDPequh14bJ4uVwO3VM+dwLokF3RV4Ew79h7gxJOnzmg78eQpduw9sFy7lKRFG1dmdXHOfQPwvWnvD/XbniLJtiRTSaaOHTu2qJ0dOX5iQe2SNE7jyqwuwj2ztNVsHatqV1VNVtXkxMTEonZ24bq1C2qXpHEaV2Z1Ee6HgIunvb8IONLBdme1fetm1q5ZdUbb2jWr2L5183LtUpIWbVyZ1UW4fx54S3quAB6vqkc62O6sXnfZBj7whheyYd1aAmxYt5YPvOGF3i0jaUUaV2alatYzKD/tkNwKbAHWA/8F3AisAaiqnf1bIT9M746aJ4Drqmpq0I4nJydrampgN0nSNEn2VdXkoH4D73OvqmsHrC/g+gXUJklaZj6hKkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwY+xLRsO06OAd9Z4mbWA492UE6XVmJNYF0LtRLrWok1gXUtRBc1/WJVDfzlXGML9y4kmRrmSa1RWok1gXUt1EqsayXWBNa1EKOsydMyktQgw12SGnS2h/uucRcwi5VYE1jXQq3EulZiTWBdCzGyms7qc+6SpNmd7UfukqRZrMhwT3JTkqNJ7p9jfZJ8KMnBJPcluXzaurcm+Y/+660jrOlN/VruS3JHkkunrft2kv1J7k3S6S+xH6KuLUke7+/73iTvnbbuyiQH+uP4ZyOua/u0mu5PcirJ+f11yzJeSS5O8tUkDyZ5IMk7Z+kzjrk1TF0jn19D1jXS+TVkTeOYWz+b5OtJvtGv689n6fP0JJ/uj8ddSTZNW3dDv/1Akq2dFFVVK+4F/BZwOXD/HOuvAr5E7++3XgHc1W8/H3io//W8/vJ5I6rpZaf3Bbz6dE39998G1o9prLYAX5ilfRXwn8AvAU8DvgE8f1R1zej7WuAfl3u8gAuAy/vL5wLfmvlvHtPcGqaukc+vIesa6fwapqYxza0A5/SX1wB3AVfM6PNHwM7+8jXAp/vLz++Pz9OB5/bHbdVSa1qRR+5VdTvw2DxdrgZuqZ47gXVJLgC2ArdV1WNV9d/AbfT+QtSy11RVd/T3CXAnvb8lu+yGGKu5vAQ4WFUPVdX/Ap+iN67jqOta4Nau9j2Xqnqkqu7uL/8QeBCY+bfOxjG3BtY1jvk15HjNZVnm1yJqGtXcqqr6Uf/tmv5r5gXNq4FP9Jf/DnhVkvTbP1VV/1NVDwMH6Y3fkqzIcB/CBuB7094f6rfN1T5qb6d39HdaAV9Jsi/JtjHU8xv9j4tfSnJJv21FjFWSZ9ALyc9Oa1728ep/JL6M3hHWdGOdW/PUNd3I59eAusYyvwaN1ajnVpJVSe4FjtI7EJhzblXVSeBx4Nks01gN/DN7K1Rmaat52kcmySvp/fC9Ylrzy6vqSJKfB25L8u/9I9tRuJve48o/SnIVsAd4HitgrPpeC/xLVU0/yl/W8UpyDr0f+HdV1Q9mrp7lW0YytwbUdbrPyOfXgLrGMr+GGStGPLeq6hTw4iTrgM8leUFVTb/mNNK5dbYeuR8CLp72/iLgyDztI5HkRcDHgKur6vun26vqSP/rUeBzdPCRa1hV9YPTHxer6ovAmiTrGfNYTXMNMz42L+d4JVlDLxQ+WVW7Z+kylrk1RF1jmV+D6hrH/BpmrPpGOrem7eM48DWeetru/8ckyWrgWfROXS7PWHV1QaHrF7CJuS8S/i5nXvT6er/9fOBhehe8zusvnz+imjbSO1f2shntzwTOnbZ8B3DlCMfqF/jp8wwvAb7bH7fV9C4KPpefXvC6ZFR19defntzPHMV49f/dtwAfnKfPyOfWkHWNfH4NWddI59cwNY1pbk0A6/rLa4F/Bl4zo8/1nHlB9TP95Us484LqQ3RwQXVFnpZJciu9q/DrkxwCbqR3gYKq2gl8kd5dDQeBJ4Dr+useS/J+4N/6m3pfnfmRbDlrei+982cf6V0j4WT1fkHQc+h9RIPehP/bqvpyFzUNWdcbgT9MchI4AVxTvRl1MskfA3vp3dlwU1U9MMK6AF4PfKWqfjztW5dzvF4OvBnY3z83CvAeesE5trk1ZF3jmF/D1DXq+TVMTTD6uXUB8Ikkq+idEflMVX0hyfuAqar6PPBx4G+SHKT3H881/ZofSPIZ4JvASeD66p3iWRKfUJWkBp2t59wlSfMw3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJatD/AXQD2+PTmkK7AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Graph A:\n",
    "degrees, counts = degree_distribution(graphA)\n",
    "fig, ax = plt.subplots()\n",
    "ax.scatter(degrees, counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some graphs of types described in lectures. You can generate other graph types with networkx functions described at https://networkx.github.io/documentation/stable/reference/generators.html\n",
    "\n",
    "A random (Erdos-Renyi) graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 600 nodes, probability of each edge 0.4\n",
    "random_graph = nx.fast_gnp_random_graph(600, 0.4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A scale-free graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 600 nodes\n",
    "scale_free_graph = nx.scale_free_graph(600)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are finding the degree distribution correctly, you can plot the distributions for these different graph types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degrees, counts = degree_distribution(random_graph)\n",
    "fig, ax = plt.subplots()\n",
    "ax.scatter(degrees, counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degrees, counts = degree_distribution(scale_free_graph)\n",
    "fig, ax = plt.subplots()\n",
    "ax.scatter(degrees, counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The plot for the scale-free graph doesn't look very clear as the relationship shown in lectures is on a log-log scale. Try using `ax.set_xscale('log')` and `ax.set_yscale('log')` on your plot to see this relationship more clearly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4:**\n",
    "\n",
    "Complete the function below to implement the clustering coefficient calculation described in lectures. This function does exist in networkx, but don't use it - implement it yourself. You can however use the `graph.neighbors()` method from networkx to find all the neighbours of a given node.\n",
    "\n",
    "You can check that your answer gives the same result as the networkx function `nx.clustering()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [],
   "source": [
    "def clustering_coefficient(graph, node_label):\n",
    "    \"\"\"\n",
    "    Calculate and return the clustering coefficient for a node in an undirected graph.\n",
    "    The clustering coefficient is the number of edges between neighbors \n",
    "    divided by the possible number of edges between neighbors.\n",
    "    \"\"\"\n",
    "    # Complete this function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Should give 0.333333\n",
    "clustering_coefficient(graphA, 'C')"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}