III. Graph Generators.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph Generators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworkX comes with a large number of builtin graph generators. These can be especially useful for testing out new measures, metrics, and dynamics, on already well tested algorithms. In this notebook, we'll go through some of the different classes of graph generators included in NetworkX and write a few of our own. There are a lot of generators in NetworkX so before you implement your own check to see NetworkX already has it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworkX has the ability to make a bunch of the graphs we made in the previous section. They mainly fall under the `classic` namespace. For example, to make a complete graph, we could just use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "C = nx.generators.classic.complete_graph(5)\n",
    "C.edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't actually have to use the full namespace call that is `nx.generators.classic.complete_graph`, everythin is under the `nx` module"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "C = nx.complete_graph(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explore the classic generators, create graphs for at least 3 of them. You can list the graphs by typing `nx.generators.classic.[TAB]`. Read the documentation for each (remember you can type (`nx.circulant_graph?`) to see the documentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Small Data Sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworkX contains a number of small graphs from classic work. For example the Zachary karate Club is often used for testing community finding algorithms. It is included in networkx along with the community information"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "KC = nx.karate_club_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "KC.nodes(data=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Others are included under `nx.generators.social`. Explore the `davis_southern_women_graph`, what is special about it?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "DSW = nx.davis_southern_women_graph()\n",
    "DSW.nodes()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Random graphs are often used as models for various physical phenomena, and testing new measures and dynamics. NetworkX has a bunch of them built in. For example the classic Erdős–Rényi graph is implemented as `gnp_random_graph` which takes a number of nodes and a probability of connection between any two nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ER = nx.gnp_random_graph(100,1.0/100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ER.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A slight variant allows you to give it the total number of edges to be placed randomly"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ER2 =nx.gnm_random_graph(100,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ER2.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Small World Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Erdős–Rényi does not have many of the properties seen in real world social network data, particularly, triadic closures. Watts and Strogatz developed a random graph model which accounts for this, and it's implemented in NetworkX!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "WS = nx.watts_strogatz_graph(10,4,.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "WS.edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Power Law Random Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A common feature of complex networks is their heavy-tailed degree distribution. That is the degrees of the nodes in a graph varies over many orders of magnitude. NetworkX contains a number of random graph models that have power law degree sequences. One of the most famous is the Barabási–Albert model. In this model nodes are added sequentially and a fixed number of edges between new nodes and existing nodes are added with nodes being selected with probability proportional to their degree. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "BA = nx.barabasi_albert_graph(10000,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "deg = BA.degree().values()\n",
    "(min(deg),max(deg))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll plot degree sequences in the next lesson on graph analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Excercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One more exercise and then we'll get to the fun stuff. On disadvantage of the original Barabási–Albert model is that it had an integer average degree and the degree distribution was power law, but could only have integer exponent. Let's make a model that is able to ahve non-integer exponent.\n",
    "\n",
    "Let's write a new model. Instead of adding a fixed number of edges with each node, we add a random number of edges from a Poisson distribution with mean $\\lambda$. To ensure the graph stays connected, if the random number of edges is 0 we add at least 1 edge. Just as in the original model, we connect to new nodes to the graph to nodes proportional to the degree of the node.\n",
    "\n",
    "First lets find a function that can generate poisson random numbers for us. It's easy to do with the `numpy` package, we can import numpy and then just call `np.random.poisson` to generate a random number with $Poisson(\\lambda)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.poisson(3.2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A trick to write a fast BA implementation is to maintain a list of nodes with nodes repeated in the list each time they have a connection made. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def poisson_BA(n,l):\n",
    "\n",
    "    start = max(2,np.random.poisson(l)) # start with at least two nodes\n",
    "    \n",
    "    G = nx.complete_graph(start)\n",
    "    \n",
    "    #an easy list to grab nodes from\n",
    "    repeated_nodes = []\n",
    "    # For each node at it's label to the list for as many times as it's degree\n",
    "        \n",
    "    u = start\n",
    "    while u < n:\n",
    "        # Using the the poisson random number generator, generate a number of connections\n",
    "        # Make Sure it's greater than 1\n",
    "        # Store that variable in `connections`\n",
    "        for _ in range(connections):\n",
    "            # For as many connections as it has select a node at random from repeated_nodes\n",
    "            # Hint numpy as a np.random.choice function\n",
    "            # Be sure to update repeated_nodes!\n",
    "        u += 1\n",
    "    return G\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "G = poisson_BA(1000,np.pi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "deg = G.degree().values()\n",
    "min(deg),max(deg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.mean(G.degree().values())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}