mrocklin/Jaccard.ipynb

## Jaccard.ipynb
{
 "metadata": {
  "name": "",
  "signature": "sha256:0587e0d9cf5a8c2b0d60697957428bc4c9fefe02b04d652d789b522b2f8a79c6"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# An example with Jaccard similarity\n",
      "\n",
      "Jaccard similarity is a simple measure of relative connectedness between pairs of nodes in a graph.  It is the ratio of neighbors that the nodes have in common (mutual friends) divided by the number of neighbors that the two have total (friends of either node).\n",
      "\n",
      "A ratio of one means that each node knows the entire neighborhood of the other node (they are effectively married).  A ratio of zero means that they have no friends in common."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Example Graph\n",
      "\n",
      "To demonstrate this lets play with a small example undirected graph"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "edges = [{1, 2}, {1, 4}, {4, 5}, {2, 5}, {2, 6}, {6, 3}]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import networkx as nx\n",
      "G = nx.Graph()\n",
      "G.add_edges_from(edges)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Couldn't import dot_parser, loading of dot files will not be possible.\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "nx.draw(G)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAdgAAAE+CAYAAAAuxAEGAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtYlHX+//HncBAYQEAUxLOBJxI1RDStNE+ZlW1Wtluy\nCakVlu22mr/tsGtmmZp+S1NDf6m1bu1m7pqnzGPpmouaopR4qFZd8wAqmjoch/n+QfVFROR0c88M\nr8d1cVVz3/fwmq6rXr7vzz33bXE4HA5ERESkRnmYHUBERMQdqWBFREQMoIIVERExgApWRETEACpY\nERERA6hgRUREDKCCFRERMYAKVkRExAAqWBEREQOoYEVERAygghURETGAClZERMQAKlgREREDqGBF\nREQMoIIVERExgApWRETEACpYERERA6hgRUREDKCCFRERMYAKVkRExAAqWBEREQOoYEVERAygghUR\nETGAClZERMQAKlgREREDqGBFREQMoIIVERExgApWRETEACpYERERA6hgRUREDKCCFRERMYAKVkRE\nxAAqWBEREQOoYEVERAygghURETGAClZERMQAKlgREREDqGBFREQMoIIVERExgApWRETEACpYERER\nA3iZHcBV5Obm8t///pcLFy5gtVqJiIggJCTE7FgiIuKkVLDXcfjwYea99RbvL15MkMVCkIcHOQ4H\nJ/Lz6d+nD8njx9O3b18sFovZUUVExIlYHA6Hw+wQzujy5cuMfPhhNq5bR5LdzuMFBbQusf0isASY\nGxCAo2FDPv70U9q3b29SWhERcTYq2DL8+OOPDOjVi/bffktKbi6+5ezrABZZLPwxIIDVmzYRFxdX\nWzFFRMSJqWBLsdvtDO7Th9Y7dzIvL4+KnvhdDiQHB7M9LY2WLVsaGVFERFyAriIuZdWqVZxNS+Pt\nSpQrwK+Axy5e5NUXXzQqmoiIuBBNsKXc0bMnCdu3M/wa2w8DMcCDwF9KbTsNtPf15T8nTxIcHGxk\nTBERcXKaYEs4fPgwe/bs4YFy9hkDxEOZ0204cKeHB++/954h+URExHWoYEtYv349QyyWa17U9Dcg\nBOhH8cVNZXnIZmPtRx8Zkk9ERFyHCraEc+fOEZabW+a2H4E/A//DtcsVIOyn9xERkbpNBVuCh4cH\njmvcMOIlYCTQhLJPD/+sCCgoKCA/P7/mA4qIiMvQnZxKaNiwIQd8fcFmu+L1NGAjsOenfy5vgj0B\n/HDiBPXr16dly5a0b9+eDh06XPHXoKAgYz6AiIg4DV1FXMLx48fp1KYNR3NzCSzx+lvAC/DLa5cA\nOxAN7Cr1HvcEBHDfW2/xyCOP8O2333LgwAEyMjJ++evBgwepX7/+L4VbsnybNGmiWy6KiLgJFWwp\n9w8aRP/PPuPJEq/lUHxrRCieXt8AjgDvAKEl9jsCxPn7cywzE6vVWub7FxUVcfz48auK98CBA9hs\nNtq3b3/V1BsZGYm3t3dNf1QRETGQCraUjRs3Mubee9l9+TJlVyS8DHwHvF/q9THe3tQbOZL/mTu3\nSr/73LlzHDx48IrizcjI4Pjx47Ru3fqq4m3Xrh3169ev0u8SERFjqWBLcTgcPDpsGD+uWcNSm42K\nzo1zPTx4MyKCL9PSaNiwYY1mys3N5fDhw1dNvYcOHSIkJKTMdd6IiAidbhYRMZEKtgz5+fk8MHgw\nOdu3s8RmI7ycffOAKV5evNegARu+/JLIyMjaiklRURHHjh0r83RzXl5emcUbGRmJl5eubRMRMZoK\n9hoKCwt5Ydw45qekcKeHB8k2G734v6/oHAFSvL1Z6OVFbNeuLFq6lMaNG5sXuJSzZ8+WWbw//PAD\nN9xww1XF2759ewICAsyOLSLiNlSw13H+/HneX7yYeTNm8N2JEwR5e/NjXh7+VisjRozgiWeeoW3b\ntmbHrLCcnBwOHz58VfEeOnSI0NDQq65sbt++PeHh4TrdLCJSSSrYSsjLy+PcuXM0b94cm81GvXr1\nzI5UY+x2O8eOHbuqeDMyMrDb7WWebm7durXLn25OT0/niy++IDs7G29vb8LCwhgyZEiNr6OLSN2j\ngq2Cxo0bs3v3bpo0aWJ2lFpx5syZMov31KlTREZGXlW87dq1w9/f3+zY15Sfn8+yZcuYN20a3x86\nxN1FRYTm5VHo4cFRX18+s9u55667SB43jh49epgdV0RclAq2Cjp37szixYu56aabzI5iKpvNxqFD\nh64q38OHDxMWFnZV8Xbo0IFGjRqZero5MzOTIf364XPkCM9cusQ9cNWV4meBxR4ezPL15cHHHmPa\nm2/i4aG7iopI5ahgq2DgwIE8++yzDBo0yOwoTslut3PkyJEyp17gisL9+e9btWqFp6enobnOnj1L\nr5tu4sFTp5hUUFDuPaUBsoF7rVbaDR3K/Pff1zq0iFSKCrYKEhIS6N+/P48++qjZUVyKw+EgKyur\nzOLNzMykTZs2ZZ5u9vPzq5Hf3bd7d+L37mVqJR7EcAnobbUy/M9/5vfPPVftHCJSd6hgq2DcuHGE\nhYXxnP6HW2MuX77MwYMHryre7777jsaNG5d5urkyFyJt27aNpDvuIOPy5Uo/QuoboH9QEEczM93q\nwjYRMZZrXwJqkvDwcE6dOmV2DLfi7+9PbGwssbGxV7xeWFjIf/7zn18K98svv2ThwoVkZGTg5eVV\nZvG2bNnyqjXTudOn86TNVma59gFS+b//GJoBGSW23wi0s9tZvnw5w4YNq6mPLCJuThNsFbz//vus\nW7eOJUuWmB2lznI4HJw+fbrM081nz56lbdu2VzylaPxTT3EkP5/gMt7rdiABSCrn9y0F5nbtyuZd\npZ+fJCJSNk2wVRAeHs7p06fNjlGnWSwWGjduTOPGjbn99tuv2Hbx4sUrTjcvWbKEloWFZZbrz673\np8y+wOMZGdfZS0Tk/6hgq0AF69wCAwOJi4sjLi4OgJUrV/LO3r1w4cI1j/kj8P+AdsCrQO9S24OA\n8zk5OBwOXU0sIhWiL/dVgQrWtVitVnLK2T4V+A9wAhgN3AN8X2ofG+Bfr57KVUQqTAVbBY0aNeLc\nuXPY7Xazo0gFtGjRgoMFBRReY3s84E/xDSd+C/QC1pTaZz/QvFEj40KKiNtRwVaBl5cXwcHBnDlz\nxuwoUgFt2rShVWQkq6vxHil+foxITq6xTCLi/lSwVaTTxK4lecIE5gYGXvX6BeAzIBcoBP4KbAVK\n3qPrLLDc4SBp1KhaSCoi7kIFW0UqWNfywAMP8LWX11WnfguAl4AwoBEwB/gEiPppuwN40ceHX+kJ\nOyJSSbqKuIpUsK7Fx8eHj1evZkj//iyz2bjtp9cbAjuucYwDeNnLi23NmrF1/vzaCSoibkMTbBWp\nYF3PzTffzIeffMID/v5Mt1jILmffA8BwHx9WREby2datBAUF1VZMEXETKtgqUsG6pv79+/P5jh3s\nGTKE1j4+jPT1ZTXwb4rXXpcAt/r40Kd+fVqNHcsXO3cSERFhbmgRcUk6RVxF4eHhvzx+TVxLdHQ0\nHyxfzunTp3l3/nxmrV5NdnY29by9wdOTHx0Oju7ciY+Pj9lRRcSF6V7EVbRmzRpmzZrF2rVrzY4i\nNejChQs0a9aMrKwsfH19zY4jIi5Mp4irSKeI3VNQUBAxMTFs27bN7Cgi4uJUsFWkgnVfAwYMYP36\n9WbHEBEXp4KtorCwMLKysigqKjI7itSw/v37s2HDBrNjiIiLU8FWUb169QgMDOTcuXNmR5Ea1qNH\nDw4fPszZs2fNjiIiLkwFWw06TeyevL29ufXWW9m0aZPZUUTEhalgq0EF6760Disi1aWCrQYVrPvS\nOqyIVJcKthpUsO4rOjqa3NxcvvvuO7OjiIiLUsFWgwrWfVksFk2xIlItKthqUMG6N63Dikh1qGCr\nQQXr3vr168emTZuw2+1mRxERF6SCrQYVrHtr0qQJERER7N692+woIuKCVLDVoIJ1fwMGDNA6rIhU\niQq2GsLDw8nMzEQPJHJf/fv31zqsiFSJHldXTUFBQRw5coSQkBCzo4gBLl68SEREBJmZmVitVrPj\niIgL0QRbTTpN7N4CAwO56aab2Lp1q9lRRMTFqGCrSQXr/rQOKyJVoYKtJhWs+9M6rIhUhQq2mlSw\n7i8+Pp4jR46QmZlpdhQRcSEq2GpSwbo/Ly8vevfuzcaNG82OIiIuRAVbTeHh4Zw6dYqioiKzo4iB\ntA4rIpWlr+lUgcPhYNu2bcx94w1Wr13Lxbw8LBYLIVYrQ+65h+Q//IG4uDizY0oNOnDgAAMHDuTo\n0aNYLBaz44iIC9AEW0mbN2+mS1QUj915J/ErVnAwL48CIM/hIO3yZdp99BEP9O5NfHQ0qampZseV\nGtKuXTscDgeHDx82O4qIuAgVbCV8+MEH/Pquu3jl++85cOkSv3M4aAx4Al5AM2BCURHf2Wz8PiOD\nu/v2ZfXq1eaGlhqhx9eJSGWpYCvos88+4/cjR7IpJ4chQHknCT2B3wCrbDZGDBvG9u3bayekGEqP\nrxORytAabAUUFBTQKjycD7Kz6V3JY/8JPN+8Ofu1dufyTp8+Tfv27cnKysLLy8vsOCLi5DTBVsAn\nn3xCVGHhVeX6NhAH+AKJ1zj2V4BXdjaff/65gQmlNoSHh9OiRQt27dpldhQRcQEq2AqYO3UqyRcv\nXvV6U+AlIKmcYy1A8qVLzJ0+3aB0Upu0DisiFaWCvY6zZ8/y1b593FfGtvuAe4HQ67zHcGDl+vUU\nFBTUeD6pXVqHFZGKUsFeR1ZWFuE+PtQrZ5/rLWIHAgFeXmRnZ9dgMjHDrbfeyu7du7l06ZLZUUTE\nyalgr6OwsJDrXc5SkUuXvC0WCgsLayKSmMjf35+4uDi2bNlidhQRcXIq2OsICQnhTEFBuVPq9SZY\nO3A2N5dVq1axf/9+7HZ7DSaU2qZ1WBGpCBXsdTRp0oSQBg3YVs4+15tgVwMtw8L4/PPPGTJkCCEh\nIfTt25cJEyawbNky/vvf/6JvS7kOPb5ORCpC34OtgDdnzmTHSy/xgc12xet2oAB4GfgBWEDxHZ08\nSx0/KCCAR+bOJSEhASi+cGrnzp3s2LHjlx9PT0/i4+N/+YmLiyMkJMTwzyaVZ7fbadiwIRkZGTRu\n3NjsOCLipFSwFZCdnU3rJk1Iz82leYnXJwKTSu07EfhTiX/OAHoHBHAsKwtfX98y39/hcHDs2LEr\nCnf37t00adKE+Ph4unXrRnx8PF26dLnme0jtGjp0KEOHDmX48OFmRxERJ6WCraApkyaxdOpUvrDZ\nCKzgMWeBnlYrz06fzuPJyZX6fYWFhWRkZFxRugcPHiQ6OvqKSbddu3Z4epaemcVo8+bNIzU1lcWL\nF5sdRUSclAq2ghwOB2Mee4ydH33EysuXud6JwSPAYKuVoWPGMHnatBrJYLPZ2LNnzxWnlzMzM4mL\ni/ulcLt160azZs10W0aDHT58mD59+nD8+HH9uxaRMqlgK8HhcPDKn/7Em2+8wTAgOTeXTqX22QnM\n9fNjucPBxFdf5ZlnnzU0k9ZzzeFwOGjdujWffvopHTp0MDuOiDghFWwVnDx5kgXz5jH/7bepX1hI\nuIcHDuCk3U6+nx9PPvssSSNH0rBhw1rP5nA4OHr06BWlW3I99+efzp07az23mkaOHEmnTp0YO3as\n2VFExAmpYKuhoKCAr7/+mnPnzmGxWAgNDaVjx45Otyaq9Vxj/P3vf+evf/0rK1asMDuKiDghFWwd\npfXc6svKyiIqKoozZ87g7e1tdhwRcTIqWPmF1nMrLzY2ltmzZ9OrVy+zo4iIk1HByjX9vJ77c9nu\n3LlT67mlPPfcc1itViZOnGh2FBFxMipYqZRrrefeeOONv9wQIz4+nvbt2+Ph4f534ly/fj0vv/wy\n//rXv8yOIiJORgUr1fbzem7JSTcrK4uuXbteMek2bdrU7dZzc3JyCAsL44cffqB+/fpmxxERJ6KC\nFUOcOXOGXbt2XTHpenl5XTHlust6bv/+/XnmmWe45557zI4iIk5EBSu1wp3Xc19//XVOnDjBrFmz\nzI4iIk5EBSumcZf13K+++oqEhAT2799vdhQRcSIqWHEqpddzd+zYQVZW1hXfz3W29Vy73U6jRo2Y\nNm0aDoeDoqIiGjRoQJ8+fWjUqJHZ8UTEJCpYcXrXWs8teUOMbt26ERwcXOvZ9u3bx9yZM/nLX/7C\nzfXq0crDAwuQ6enJF/n53D14MGPGj6dHjx5O8wcCEakdKlhxOaXXc3++33LTpk1rbT23qKiIcU8/\nzd8XL+aJvDxG2u1ElNrnHLDYYmGO1UqPgQNZ+OGH+Pj4GJJHRJyPClbcQnnruSUn3ZpYz3U4HIx4\n6CGOrlnDPy9f5nrXQecAw/38uBwXx8qNG3VbRZE6QgUrbsuo9dzJf/oTq2bMYJPNhrWCxxQC9/n5\n0WzYMObpIe0idYIKVuqU0uu5qampeHt7V3g999KlS7QICyMtJ4cWlfzdF4FWvr6kHTpE8+bNq/1Z\nRMS5qWClTqvsem7KO+/w2bhx/OPy5SveJx94EthI8dprJDAFGFTq94318SH42WeZ9NprtfHxRMRE\nKliRUgoLC9m/f/8vN8QouZ574uBB3rt4kf6ljrEB04FEoAWwGvgNkA60LLFfBtA3KIhjWVlaixVx\ncypYkQqw2WykpqYysF8/8hwOKnKZVGdgInBfqddbBwSwIS2NyMjIGs8pIs7DeW+PI+JErFYr0dHR\nhPj6Vug/mtPAIeDGMrYFe3hw/vz5mg0oIk5HBStSQb6+vuTa7dfdrwB4BBgBtC1je67D4XL3WxaR\nylPBilRQ/fr1cVgsnCxnnyIgAfAF3i5juw04mZ9P48aNjYgoIk5EBStSQRaLhYcfeoj/7+lZ5nYH\n8BiQBSwDytrr78AtPXoQGhpqWE4RcQ4qWJFKePL3vyelXj0Ky9oGHABWANe6IeKcgACSn3vOsHwi\n4jxUsCKV0KVLF1q3a8ecUrdbPArMB/YCjYHAn34+LLHPP4CDNht5eXm1lFZEzKSCFamkxR9/zOuB\ngSwt8VpLitdfbRTfsennn9/8tP1z4Al/f2a+8w7PPfccDz/8MGfOnKnN2CJSy1SwIpUUGRnJms2b\n+V1ICC97epJdzr6XgLeAYQEB/G3FCkaNGsXevXuJiIggJiaGjz/+uJZSi0ht040mRKro6NGjPP+7\n37Fm7VqGWiwk5OTQhOI/tWYCf6tXjyUWC7fdcguT33yTjh07XnH89u3bSUpK4sYbb2TOnDmEh4eb\n8TFExCAqWJFqyszMZOGCBSxfsoSz2dkUORyE1K/PoPvvZ3RyMi1aXPuxALm5ubz88sssXLiQmTNn\n8vDDD+vB7CJuQgUr4gR27dpFYmIirVu35p133qFJkyZmRxKRatIarIgTiIuL46uvvuKmm26iS5cu\nLFq0CP3ZV8S1aYIVcTJ79+4lMTGRsLAw5s+fX+4pZhFxXppgRZxM586dSU1N5dZbb6Vr166kpKRo\nmhVxQZpgRZzYN998Q1JSEgEBASxYsIAbbrjB7EgiUkGaYEWc2I033si2bdu488476d69O7Nnz6ao\nqMjsWCJSAZpgRVzEoUOHSEpKwmKxsHDhQtq0aWN2JBEphyZYERfRtm1bvvjiCx588EFuvvlmZsyY\ngb0Cz6cVEXNoghVxQd999x0jR44kJyeHhQsXEh0dbXYkESlFE6yIC4qMjGTjxo2MGDGC3r17M2XK\nFAoLy3qInoiYRROsiIs7evQoo0eP5syZMyxatIhOnTqZHUlE0AQr4vJatmzJ2rVrGTNmDP369WPi\nxInk5+ebHUukzlPBirgBi8VCUlISaWlp7Nq1i27duvHVV1+ZHUukTlPBiriRpk2bsnLlSsaPH8/g\nwYN5/vnnyc3NNTuWSJ2kghVxMxaLheHDh7N3714OHDhAbGwsqampZscSqXN0kZOIG3M4HCxdupSx\nY8cyfPhwXnnlFfz8/MyOJVInaIIVcWMWi4Vhw4aRnp7ODz/8QOfOndm6davZsUTqBE2wInXI8uXL\nGTNmDPfffz9TpkzB39/f7EgibksTrEgd8qtf/Yr09HQuXLhATEwMmzZtMjuSiNvSBCtSR61Zs4Yn\nnniCwYMHM23aNOrXr292JBG3oglWpI4aPHgw6enp2O12YmJi+Oyzz8yOJOJWNMGKCOvXr2fUqFH0\n7duXGTNmEBISYnYkEZenCVZEGDBgAOnp6VitVmJiYli5cqXZkURcniZYEbnCF198wWOPPUb37t2Z\nNWsWoaGhZkcScUmaYEXkCr1792bv3r2EhYURExPDsmXLzI4k4pI0wYrINX355ZckJSURExPDnDlz\nCAsLMzuSiMvQBCsi19SzZ0/27NnDDTfcQKdOnfjwww/Rn8lFKkYTrIhUyM6dO0lMTCQqKop58+YR\nERFhdiQRp6YJVkQq5OdnzHbq1InOnTuzePFiTbMi5dAEKyKVlpaWRmJiIhEREaSkpNC8eXOzI4k4\nHU2wIlJpXbp0YceOHfTs2ZPY2FgWLFigaVakFE2wIlItX3/9NYmJiQQFBbFgwQJat25tdiQRp6AJ\nVkSqpWPHjmzfvp2BAwfSrVs33n77bYqKisyOJWI6TbAiUmMOHDhAUlIS3t7evPvuu0RFRZkdScQ0\nmmBFpMa0b9+erVu3ct9999GjRw9mzpyJ3W43O5aIKTTBioghvv32W0aOHEleXh4LFy6kQ4cOZkcS\nqVWaYEXEEFFRUWzatImEhARuvfVWXn/9dQoLC82OJVJrNMGKiOGOHDnCqFGjyM7OZtGiRcTExJgd\nScRwmmBFxHCtWrVi3bp1PPHEE/Tt25dJkyaRn59vdiwRQ2mCFZFadfz4cR5//HGOHz/OokWLiI2N\nNTuSiCE0wYpIrWrWrBmrVq3iD3/4A4MGDeLFF18kLy/P7FgiNU4FKyK1zmKx8Nvf/pa9e/fyzTff\nEBsbS2pqqtmxRGqUThGLiKkcDgcfffQRzzzzDAkJCUyaNAk/Pz+zY4lUmyZYETGVxWLhoYceIj09\nnWPHjtGlSxe2bdtmdiyRatMEKyJO5R//+AdPPfUUDz74IK+99hr+/v5mRxKpEk2wIuJUhg4dSnp6\nOtnZ2XTq1InNmzebHUmkSjTBiojTWrVqFU8++SR3330306ZNIzAw8LrH2O12MjIyOHv2LBaLhdDQ\nUDp06ICHh+YJqV0qWBFxaufPn2fcuHGsX7+e+fPnc8cdd5S5X2ZmJu/On0/KW29RLzeXcE9PAE7Y\n7VgCAnjy2WcZkZREaGhobcaXOkwFKyIuYd26dYwePZp+/foxY8YMgoODgeKrkKe99hpTXnmF+y0W\nknNz6VriOAeQCsz182OFw8ErU6bw9O9+Z8ZHkDpG50xExCUMHDiQ9PR0fHx86NixI6tWrcLhcPD7\nJ5/kw9de45u8PN4tVa4AFqAH8H5ODntyc5n7wgu8NGGCCZ9A6hpNsCLicjZv3szIkSNpEBRE3sGD\nbLXZCKrgsWeAXlYrf3jjDUY/+aSRMaWOU8GKiEs6efIkbVu04OvCQlpW8tgM4LaAAI5lZuqmFmIY\nnSIWEZf0j2XLuNPH55rl+jegAxAARAH/KrGtA9AVWLp0qbEhpU7TBCsiLsfhcNCxVSvmHDtGnzK2\nrwdGAR8B8cBJii92alJinxXAqx06kLp/v9FxpY5SwYqIyzl16hQdW7cmKzcXSxnbe1JcsInlvIcd\nCPDy4sz587pblBhCp4hFxOVkZ2fT0Nu7zHK1A18BmUAboDnwNJBbaj9PIKRePbKzsw3NKnWXClZE\nXI6npyf2a2w7DRQAyyhed00D9gCTy9jX7nDg5eVlTEip81SwIuJyGjZsyOm8PPLL2PbzNcFPA+FA\nKPAssKbUfpeBCwUFhISEGBdU6jQVrIi4nAYNGtCtc2f+Wca2EKBZBd7jA2BQ7974+PjUbDiRn6hg\nRcQlJU+YwNxr3Pw/EZgNZAHZwP8A95TY7gDmBgaS/NxzRseUOkwFKyIuaciQIXzn7c2WMra9BHQD\n2gLRFH/n9YUS29cAR/PyiIqKMj6o1FkqWBFxSd7e3rz7wQcM8/Oj9DdZvYA5FE+vJ4E3gXo/bdsN\nJPr58eCIEcTHxzNv3jyKiopqL7jUGSpYEXFZd9xxBzPmz+d2Pz9WU3zq91qKKL6yeJDVSsqSJaSk\npLBlyxbee+89+vXrx/fff187oaXOUMGKiEt7ZPhwPli5kgktW3JjQACzLRbOUFy2Doq/tjPTYqGd\nvz+To6L457p13Dd0KADR0dFs27aNu+66i/j4eGbPnq1pVmqM7uQkIm7B4XCwdetW5k6fzur168nJ\nL/4Sj7+PD0MGD2bM+PF0794di6Ws21PAwYMHSUpKwtPTk3fffZc2bdrUZnxxQypYEXFLBQUFQPFa\nbUXZ7XZmz57N5MmTeeGFFxg7diyenp5GRRQ3p4IVESnl22+/JSkpCbvdzsKFC2nXrp3ZkcQFaQ1W\nRKSUqKgoPv/8c37zm9/Qq1cvpk+fjt1+rZszipRNE6yISDm+//57Ro4cic1mY+HChURHR5sdSVyE\nJlgRkXLccMMNbNiwgREjRnDbbbcxZcoUCgsLzY4lLkATrIhIBR05coRRo0Zx/vx5Fi1aRMeOHc2O\nJE5ME6yISAW1atWKdevWMXr0aG6//XYmT578y9XKIqVpghURqYJjx44xevRoMjMzWbRoEZ07dzY7\nkjgZTbAiIlXQokULPv30U55++mkGDBjAxIkTyc8v6wm1UlepYEVEqshisZCYmMiePXvYtWsX3bp1\nY/fu3WbHEiehghURqaamTZuycuVKxo0bx6BBg3jxxRfJy8szO5aYTAUrIlIDLBYLCQkJ7N27l/T0\ndLp27crOnTvNjiUmUsGKiNSgiIgIli9fzvPPP8/dd9/NH//4R3Jzc82OJSZQwYqI1DCLxcLDDz/M\nvn37OHToELGxsfz73/82O5bUMn1NR0TEQA6Hg6VLlzJ27FgSEhKYNGkSfn5+ZseSWqAJVkTEQBaL\nhWHDhpGens6xY8fo0qUL27ZtMzuW1AJNsCIitWjZsmU89dRT/PrXv+bVV1/FarWaHUkMoglWRKQW\n3X///aQA9usqAAAGeElEQVSnp5OZmUmnTp3YsmWL2ZHEIJpgRURM8sknn5CcnMzQoUOZMmUKAQEB\nZkeSGqQJVkTEJPfeey/p6en8+OOPdOrUic2bN5sdSWqQJlgRESewevVqnnjiCe655x6mTp1KYGCg\n2ZGkmjTBiog4gbvuuov09HTy8vKIiYlhw4YNZkeSatIEKyLiZNauXcvo0aMZNGgQ06dPJygoyOxI\nUgWaYEVEnMygQYNIT08HICYmhrVr15qcSKpCE6yIiBNbv349o0aNom/fvsycOZPg4GCzI0kFaYIV\nEXFiAwYMID09HV9fX2JiYli9erXZkaSCNMGKiLiIzZs389hjj3HLLbfw5ptv0qBBA7MjSTk0wYqI\nuIjbb7+dffv2ERwcTExMDJ988onZkaQcmmBFRFzQli1bSEpKIj4+nlmzZtGwYUOzI0kpmmBFRFzQ\nbbfdxr59+wgPDycmJoZly5aZHUlK0QQrIuLitm3bRlJSEl26dOHtt9+mUaNGZkcSNMGKiLi8Xr16\nkZaWRosWLYiJieGjjz5Cs5P5NMGKiLiR1NRUEhMT6dChA3PnziU8PNzsSHWWJlgRETfSvXt3du/e\nTdu2benUqRMffPCBplmTaIIVEXFTO3fuJDExkcjISN555x0iIiLMjlSnqGBFRNxYXl4ekydPJiUl\nhTfeeIOEhAQsFku5x5w/f56VK1dy8uRJ8vPzCQ4OpmfPnsTGxtZSavegghURqQN2795NYmIizZs3\nJyUlhaZNm161T1paGnNnzmTp0qX08fIiKjeXenY753x8WOPhQeOWLUmeMIGHHnoIX19fEz6Fa1HB\niojUEfn5+UyZMoU5c+YwdepURowYgcViweFwMPnPf2buG28wJj+fkXY7jUsdawfWALMDAjgVHs6a\nzz+nWbNmJnwK16GCFRGpY/bu3UtiYiJhYWEsWLCAt2fOZP2CBay+fJnrrdI6gDc8PZkTGsqXe/bQ\npEmT2ojsklSwIiJ1UEFBAVOnTmXa1Kk0ys9nR34+oZU4foqXFx9HRrLjm2/w9PQ0LKcrU8GKiNRR\nRUVFRDVuzPtZWdxSyWMdQPfAQP784YfcddddRsRzefoerIhIHbVx40YCc3LoVca24UAEUB+4AXi1\n1HYLMObiReZMnWpwStelCVZEpI66/447GLhuHY+Xse0bIBLwBQ4CvYHFwKAS++QALXx92bF/P61b\ntzY6rsvRBCsiUkelpaXR9xrbbqS4XH/mBYSV2scP6OHjw759+4yI5/JUsCIiddT5S5cILmd7MuBP\ncdm+CJR1m4lgu50LFy4YEc/lqWBFROooq48PtnK2zwUuARsoLtgdZexj8/DAarUaEc/lqWBFROqo\nFk2bsv86+1iAPsCDwIeltjmA/UVFNG/e3IB0rk8FKyJSRz361FOk+PtXaN8Cik8Xl7QVIDiY+Pj4\nGk7mHlSwIiJ11MOPPMKWoiKOlXo9C/gbcJniWyR+BiwF7i2131yrleTx46/78IC6SgUrIlJHBQQE\nMGLECCb4+lLy+5oW4B2gGRAKvAT8BehWYp9/ARssFn776KO1ltfV6HuwIiJ1mM1mo1+PHvQ4eJAZ\n+fkVmrp2A4P9/Hh/+XIGDhxodESXpQlWRKQOs1qtrNq8mZ3R0Tzg60t6OfteovjK4jusVuYtWaJy\nvQ4VrIhIHRcaGsqG7dvpMn48g4KDuS0wkPcpPg28k+I12Kd9fGjh68uGgQNZu2UL9w0dam5oF6BT\nxCIi8ouCggJWrFjBBykpnDpxgry8PIKDg+k5YACjk5P1DNhKUMGKiIgYQKeIRUREDKCCFRERMYAK\nVkRExAAqWBEREQOoYEVERAygghURETGAClZERMQAKlgREREDqGBFREQMoIIVERExgApWRETEACpY\nERERA6hgRUREDKCCFRERMYAKVkRExAAqWBEREQOoYEVERAygghURETGAClZERMQAKlgREREDqGBF\nREQMoIIVERExgApWRETEACpYERERA6hgRUREDKCCFRERMYAKVkRExAAqWBEREQOoYEVERAygghUR\nETGAClZERMQAKlgREREDqGBFREQMoIIVERExgApWRETEACpYERERA6hgRUREDKCCFRERMYAKVkRE\nxAAqWBEREQOoYEVERAygghURETGAClZERMQAKlgREREDqGBFREQMoIIVERExgApWRETEACpYERER\nA6hgRUREDKCCFRERMcD/Ak8v4omdW9rVAAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x37f1190>"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We want to quantify the similarity between pairs of nodes in a subset of this graph.  We care about the following subset "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sub_nodes = {1, 5, 6}  # subset of nodes about which we care"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lets get all edges originating from these nodes"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "edges = [(a, b) for a, b in edges] +  [(b, a) for a, b in edges]  # Direct an undirected graph\n",
      "\n",
      "sub_edges = [(a, b) for a, b in edges \n",
      "                    if a in sub_nodes]\n",
      "sub_edges"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "[(1, 2), (1, 4), (5, 4), (5, 2), (6, 2), (6, 3)]"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "G = nx.DiGraph()\n",
      "G.add_edges_from(sub_edges)\n",
      "nx.draw(G)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAd8AAAE+CAYAAADMGBp/AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xd4FdXCxeFfGmn0LkXwCoTeO6EqGCUgoKiABZFQRaQk\ndGnSEsqlq0FFBUVigQBXaSKhg4KR3hQFaaGTQup8f4D5CAkQIGfmJFnv8+S5eGbOnHW86sqesreD\nYRgGIiIiYhpHqwOIiIhkNypfERERk6l8RURETKbyFRERMZnKV0RExGQqXxEREZOpfEVEREym8hUR\nETGZyldERMRkKl8RERGTqXxFRERMpvIVERExmcpXRETEZCpfERERk6l8RURETKbyFRERMZnKV0RE\nxGQqXxEREZOpfEVEREym8hURETGZyldERMRkKl8RERGTqXxFRERMpvIVERExmcpXRETEZCpfERER\nk6l8RURETKbyFRERMZnKV0RExGQqXxEREZOpfEVEREym8hURETGZyldERMRkKl8RERGTqXxFRERM\npvIVERExmcpXRETEZCpfERERk6l8RURETKbyFRERMZnKV0RExGQqXxEREZOpfEVEREym8hURETGZ\nyldERMRkKl8RERGTqXxFRERMpvIVERExmcpXRETEZCpfERERk6l8RURETKbyFRERMZnKV0RExGQq\nXxEREZOpfEVEREym8hURETGZyldERMRkKl8RERGTqXxFRERM5mx1ABERyZySkpJYt24dO3fu5OqF\nC7h6elKseHE6duxIoUKFrI5n1xwMwzCsDiEiIpnHlStX+GTBAuZPn47n9es8Gx1NvqQkbgBHPTxY\nkZiI73PP8XZAAPXr17c6rl1S+YqISLodOHCA1s2b0+D6dfrFxFAfcLhjn0vAQgcHZri789a77zL6\n/fdxcLhzr+xN5SsiIuly+PBhmtatS+D167yejuo4B/h6eNDcz4/A//7X9gEzEZWviIjc140bN6j8\nn/8w/OxZuj1AbVwCGnp4MGL+fF57/XXbBcxkdLeziIjc19KlS3ny+vW7Fu8SoAKQEygDbL71en7g\ng+hoJo8ahcZ6/0/lKyIi9zVvyhT6RkamuW0tMBT4DIgENgH/uW17U8C4dImwsDBbx8w0VL4iInJP\n4eHhnDlxgtZ32T761k/dW3/9GFDstu0OQJ+oKD6YNs2GKTMXla+IiNzTvn37aOjoiFMa2xKBX4Hz\nQFmgJNAPuHHHfo0Ng33h4bYNmomofEVE5J6uXbtG7sTENLedA+KBb7l5nfc3YA/w/h375QGuRUXZ\nMGXmovIVEZF78vT0JNox7bpwv/W//YAiQAFgIPC/O/aLAjzd3GwVMdNR+YqIyD2VLl2a3x0dSete\n5XxAiXQc43eg9BNPZGywTEzlKyIi9+Tt7U2Upyfb77L9TWA2EAFcBmYAbe7Y54NcuejWv78NU2Yu\nKl8REbknR0dHeg0YwEwXlzS3jwLqAOWAikAtYMRt2/cBx5yceP75520dNdPQqkYiInJP+/fv5+uQ\nEA4mJrIJaHzHdmdg7q2fO8UDAz086PPuu7jcpbyzI418RUQkTTdu3GDUqFE0a9aMbt26sXTFCto6\nObErne+PA7q6uZGjXj2GjBhx3/2zE5WviIik8vPPP1O1alUOHDjAb7/9Rs+ePQkJCeHxSpV4zsOD\naQ4OXL7Lew3gZ6ClhweR3t4sXbkSZ2edaL2d/m6IiEiyS5cuERAQwOrVq5k9ezbt2rXDMAz69u3L\n8ePH2bp1K8ePHydwzBj+88MPdHBwwCcmhnzcnFjjqIMDwZ6ekC8ffQMC6NW7N05OaU3Pkb1pVSMR\nEcEwDL7++msGDBjACy+8wMSJE8mdOzeGYTBw4EC2bdvGmjVryJ07d/J7zp8/zyfBwezcsIErly/j\n5uZGsdKledXPj6ZNm2oN33tQ+YqIZHMnTpygT58+nDx5kuDgYOrXrw/cLOQRI0bwww8/8NNPP5Ev\nXz6Lk2YduuYrIpJNJSQkMGPGDGrXro23tze//vprcvECvP/++4SGhrJ27VoVbwbTNV8RkWxoz549\n+Pn5kTt3brZt20bZsmVTbJ86dSqLFy9m48aNFCxY0KKUWZdGviIi2UhUVBT+/v4888wz9O3bl/Xr\n16cq3jlz5jB//nzWrVtHkSJFLEqatal8RUSyidWrV1OlShVOnz7Nvn37ePPNN1PdFLVgwQKCgoJY\nv349JUqkZ9ZmeRi64UpEJIs7f/48AwcOZMuWLcyfPx8fH58091u0aBFDhw5lw4YNqUbDkrE08hUR\nyaIMw2DhwoVUqVKFokWLsm/fvrsWb0hICP7+/qxZs0bFawLdcCUikgUdO3aMnj17cuXKFX744Qdq\n1qx5131DQ0Pp168fq1evpmLFiiamzL408hURyULi4+OZNGkS9evXp3Xr1uzYseOexbt69Wq6d+/O\nypUrqVatmolJszeNfEVEsogdO3bg5+dH8eLF2bVrF0/cZ/H6n3/+mddee41ly5ZRu3Ztk1IKqHxN\nFx0dzfr16zl//jzx8fHkzZuXRo0aUbJkSaujiUgmdf36dUaMGEFISAjTp0/nlVdeue/Ujlu3buWl\nl15i6dKlNGzY0KSk8i+Vr0mOHj3KB7Nm8dmnn1LVyYnSCQk4GwYXnZ3pExdH08aN6RMQwFNPPYWj\no64GiEj6hIaG8vbbb9OyZUv2799P/vz57/ueX375hXbt2vHFF1/QrFkz24eUVPSokY0ZhkHgxIlM\nnTCBbgkJ9IyP5z937BMJfAnMyZmTotWqEbJqFXny5LEgrYhkFmfOnKFfv36Eh4fz0Ucf0bx583S9\nLzw8nFatWhEcHEzbtm1tnFLuRkMsGxvh78+XkyaxJyaGKWkUL0BOoAewOzKSsr/8Qot69bh+/brJ\nSUUkM0hKSuLDDz+katWqlC9fnt9///2+xfvvGOvAgQP4+PgwZ84cFa/FNPK1oYUff8zEd95hW3Q0\nBdL5HgPo5ebG6QYNWPHTT7aMJyKZzIEDB+jRoweJiYkEBwdTqVIltm3bxk8//cTl8+dxcnamcLFi\ntG/fnieffBL4/zmcp02bRpcuXZg8eTKvvvqqxd9EVL42kpiYyJOPPcbSiAjqPuB7E4Bynp58vWED\nderUsUU8EclEYmNjmThxInPnzmXs2LG88cYbfLl4MfMCA4k6d44OMTEUSkoiEfgrRw5CHB2pXbs2\nrV9+mdGjR3Pp0iWcnJwYN24cw4cPt/rrCCpfm1m5ciXjOndmZxqnj+cAC4F9QCfg0zTeH+joyMGO\nHfl0yRKb5hQR+xYWFkaPHj0oX748c+bMwcnJidbNmlHk1CkGREfzNKmvH8YAS4FxDg6cNgxu3Hq9\nWLFi/PbbbxQqVMjU7yCp6ZqvjcwPCqLPXa7bFgdGAd3u8f5uSUksW76cS5cu2SKeiNi5y5cv06NH\nDzp37sykSZNYtmwZrq6uNKldmw5//MH/oqNpRdr/EXcH3gD2GQZNb/01QOfOnbU8oJ1Q+drIzt27\nSXsGVWgPPA/3vA5cEKjs6srevXszPJuI2C/DMFi6dCmVKlXCxcWF/fv30759ewzDoONzz/FyRAQj\nExK491O8N7kDK4DqQL0aNQgMDLzv879iDj3nayNXoqO539N29zvfnxe4cuVKBiUSEXv3999/07dv\nX/7880+++eabFJNf7Nixg1MHDzIuPj7V+14F1gNR3PzF/S1gxK1tLsDXQLVDh4iKiiJnzpy2/hqS\nDhr52oibi0vydZa7ud/vnzcANze3DEokIvYqMTGRmTNnUrNmTerVq8fu3btTzTo1b+pUekdHp/kf\n7WHAn8A14AdgNvDjbdtLAk0dHVm8aJGNvoE8KJWvjRQrUIAj99nnXiPfJGDf9essW7aMn376iejo\n6AxMJyL24rfffqNBgwZ8//33bNmyhZEjR5IjR44U+1y6dIkVq1bR9S73x1YCbv813RkofMc+faKi\n+GDq1IyMLo9A5Wsjr3bvTvB9Rq33GvmuB3IVLkzu3LkZMWIEhQsXxtvbm+HDh7N69WpNwiGSyUVH\nRzNkyBBatWpFr1692LBhA15eXmnue/z4cZ50db3nfSJ9AE9uFvFI4M51jBoDB06cQA+42AeVr410\n79WLpYbB1TS2JXLzlHLCrT/H3vrf201zcuLV3r2ZMmUK27Zt49y5c4wZMwZnZ2cmTpzIY489Rt26\ndfH392fFihW6NiySiaxdu5YqVarw999/s3fvXrp163bPG6GuXbtG7vsccx43p6pdx83y3XnHdjdu\n3swVFxf3KNElg+g5Xxvq1LYtJX78kaA7bpAYA4y7Y98xwHu3/rwVeDZHDpxz5qRLly6MHj2aAgVS\n/s5748YNdu7cycaNG9m4cSM7duygTJkyNGnShKZNm9K4cWM9yydiZyIiIhg0aBBhYWHMmzeP5557\nLl3v2759O/19fNhxNa1f51Przc2ynXHba/GAh6MjcQkJuuPZDmjka0OzPv6YZYUKMeuOVYrGcPOa\n7u0//xbv70AHd3e+Xr6cQ4cOkZCQQPny5fnvf/+b4jdWNzc3mjRpwqhRo1i3bh0XL15k3rx5FCtW\njAULFlCmTBkqVapEnz59WLJkCWfOnDHjK4tIGgzD4PPPP6dy5coULFiQffv2pbt4AUqVKsWx2Fhi\n0rl/PDdPQd8uHChVqJCK114YYlN//PGHUbZ4caOfi4txGgzjLj83wFgIRiF3d+PrJUtSHGPfvn2G\nj4+PUbZsWWPZsmVGUlLSfT83Pj7e+OWXX4xp06YZbdu2NfLly2eUKVPGeOutt4zPP//cOHHihK2+\nsojc5tixY8bTTz9tVK9e3di1a9dDH6d106bGp2n8t+M8GF+BEQlGAhg/gpEbjJ137PeWm5sxcfz4\nDPxm8ihUviaIiIgwer7xhpHXzc14ycPD+BGMg2AcA2MHGMNcXIzC7u5Gy/r1ja1bt971OD/88INR\nsWJFo3nz5saePXseKENiYqIRHh5uzJ4923jxxReNwoULG6VKlTJef/11Y8GCBcbRo0fTVeoikj5x\ncXHG5MmTjQIFChhBQUFGfHz8Ix1v1apVRp1cuVKVbwQYTcHIC0YeMOqAsfyOfS6BkdfNzTh37lwG\nfTt5VLrma6KrV6/yxeef83VwMOcvXCAuPp58uXPT9Jln6P3uu5QrV+6+x0hISCA4OJixY8fi6+vL\n+PHjeeyxxx44i2EYHD58OPma8caNGwGSrxk3adKEChUq6BSVyEPYuXMnfn5+FC1alA8++IAnnnji\nkY+ZmJhIpSeeYOipU3d95CgtBtDD1ZX4tm1ZuHTpI+eQjKHyzaSuXLnCxIkT+eSTTxgwYAADBw7E\n3d39/m+8C8Mw+OOPPwgLC0su46ioKJo0aZJcyFWqVMHRUbcJiNzN9evXGTVqFEuWLGHatGl07tw5\nQ3+BPXjwIM3q1WP+9et0SMf+BjDcxYUfS5cm7NdfyZUrV4ZlkUej8s3kjh8/zpAhQ9i1axeTJk2i\nU6dOGfYv+99//51cxmFhYURERODt7Z08Mq5RowbOzpqhVARurmTWt29fWrRowdSpU1M9oZBRdu/e\nTZunn6bz9ev0S0jg8bvs9yswwc2N02XKELp+PYUL3znthlhJ5ZtFbNq0iQEDBuDs7MyMGTNo0KBB\nhn/GmTNn2LRpU/LI+OTJkzRs2DB5ZFy7du1UM/OIZHVnzpyhf//+7N69mw8//JCnnnrK5p956tQp\npk6YwBeff05jBwdeiIqiEDfnDjgJLMyVi3OurvTs35/+Awfi4eFh80zyYFS+WUhSUhKLFi1i+PDh\neHt7M2XKFEqVKmWzz7tw4QKbNm1KHh0fPXqUunXrJo+M69Wr90inwkXsWVJSEh9//DEjRoyge/fu\njBo1yvR/3qOiovhy8WLWL1/O5YsXcXZ2plCxYrz4+us8++yzODk5mZpH0k/lmwVFRUUxdepUZs2a\nRc+ePRk6dCi5c99vfpxHd+XKFbZs2ZI8Mt6/fz81a9ZMHhk3aNBAK6pIlnDo0CF69OhBbGwswcHB\nVK1a1epIksmofLOwf/75hxEjRrB69WrGjRtHt27dTP1NODIykq1btyaPjPfs2UPlypWTR8be3t7k\nyZPHtDwijyo2NpbJkycze/ZsRo8eTZ8+fTS6lIei8s0Gfv31VwYMGMCVK1eYPn06Tz/9tCU5YmJi\n2LFjR/LIeOfOnXh5eaWYEtNWN6mIPKrNmzfTo0cPypQpw9y5cylZsqTVkSQTU/lmE4Zh8N133xEQ\nEEDFihWZOnXqXVdQMUtcXBy7du1KHhlv3bqVUqVKJY+MmzRpQtGiRS3NKHLlyhWGDh3KihUrmDVr\nFh06dNDz7/LIVL7ZTGxsLLNnz2by5Ml07tw5zUUbrJKQkMCePXuSR8abN2+mSJEiKSb+0GhDzGIY\nBt9++y39+/enbdu2TJo0ibx581odS7IIlW82FRERwejRowkJCWHEiBH06dPH7h4TSkxMZO/evSme\nNc6VK1dyETdt2pQnnnhCoxDJcCdPnuTtt9/m6NGjfPTRR3h7e1sdSbIYlW82t3//fgYPHszx48cJ\nCgqibdu2dltmhmFw8ODBFFNiOjs7pxgZe3l52W1+sX+JiYnMmzePsWPH8s477zBkyBBcXV2tjiVZ\nkMpXAPjxxx8ZNGgQRYoUYfr06VSvXt3qSPdlGAbHjh1LMSVmbGxsiikxK1WqpCkxJV1+//13/Pz8\ncHV15aOPPqJ8+fJWR5IsTOUryW5ftKF169a8//77D7Vog5X++uuv5CIOCwvj0qVLNG7cOHlkXL16\ndT0aIinExMQwfvx4FixYwMSJE+nWrZt+YRObU/lKKhm9aIOV/vnnnxRTYp4+fZpGjRolj4xr1aqF\ni4uL1THFIuvXr6dnz57UqlWLmTNn6u56MY3KV+7Klos2WOX8+fPJZRwWFsbx48epX79+8si4bt26\nuLm5WR1TbOzixYsMGjSIDRs2MHfuXHx9fa2OJNmMylfuy4xFG6xy+fJlNm/enDwyPnjwILVr104x\nJaYmpc86DMPgyy+/ZNCgQXTq1Inx48drylOxhMpX0sXsRRuscu3aNbZu3Zo8Mg4PD6dq1arJI+NG\njRqZMk+2ZIwrV65w/PhxatWqxR9//EHv3r05d+4cwcHB1KlTx+p4ko2pfOWBWLVog1Wio6PZvn17\n8sj4l19+oUKFCskjY29vb/Lnz291TLmDYRh88803vPPOOzg6OtKrVy9mzpxJQEAAAwYM0HV+sZzK\nVx6K1Ys2WCU2NpadO3cmj4y3b9/OE088kWJKTC1abq2TJ0/Sp08fVq5cmfxaiRIl+Pnnn3nyySct\nTCby/1S+8kjsZdEGq8THx7N79+7kkfGWLVsoVqxYiok/ihcvbnXMbCExMZG5c+cyYsQIIiMjU2xz\ncHBg+/bt1K1b16J0IimpfOWRGYbB999/j7+/v90s2mCVxMREwsPDk0fGYWFh5MuXL8WUmKVLl7Y6\nZpYTHh6On58fu3btSrXNxcWFYcOGMWzYMN3JLnZD5SsZ5t9FG6ZMmUKnTp3satEGqyQlJXHgwIEU\nE3+4urqmGBmXLVs20z/CZZWYmBjGjh3L1KlTSUxMTLW9UaNGfPTRR1SsWNGCdCJ3p/KVDJcZFm2w\nimEYHDlyJLmIN27cSGJiYoopMStUqKAZltJh3bp19OrVi+PHj6faljt3bqZMmUKPHj3091LskspX\nbCYzLdpgFcMwOHHiRIqR8bVr11JMiVm1atUUN7MdO3aMEydO0KBBAzw9PS1Mb40LFy4waNAgPv/8\n8zS3v/DCC8yaNYtixYqZnEwk/VS+YnOZcdEGK508eTL5evHGjRs5d+4c3t7eySPj0NBQJkyYgLOz\nM7Vr104uaW9v7yz92JdhGCxevJgBAwZw4cKFVNuLFy/O3Llzef755y1IJ/JgVL5iiqywaINVzp07\nl2JN4wMHDqR5fdPR0ZEaNWqkeAY5q1xz/+OPP+jVqxdr165Ntc3BwYG+ffsyYcKELP3Lh2QtKl8x\nVVZatMEKN27cIG/evMTGxqZr/ypVqqR4BrlIkSI2Tpix4uPjmTFjBmPGjCEmJibV9sqVKxMcHEz9\n+vUtSCfy8FS+YomsuGiDGSIiIhg2bBgbN27k2LFjD/z+8uXLp7jTukSJEjZImbaEhASuXbuGh4dH\nuh752bVrF35+foSHh6fa5urqyujRoxk8eLBmq5JMSeUrlrp90Ybp06fTsGFDqyNlGqdPn051OvpB\n/ec//0n1DHJG/hJ05coVPvv0Uz6YPp2j//xDThcXohMSyJ8zJ2/6+dHz7bdTPfccGRnJqFGjmDVr\nFklJSamO2aJFCz744APKli2bYTlFTGeIWCwxMdH47LPPjOLFixsvv/yy8eeff1odKVM6f/688c03\n3xjvvPOOUa1aNcPBwcEAHuinZMmSRpcuXYyPPvrIOHTokJGUlPRQWeLj441Bffsaed3cjFc8PIww\nMBLBMMBIAuMQGO/myGHkd3Mz2rdqZURERBiGYRgrV640Hn/88TSz5c+f3/j0008fOpOIPdHIV+zG\n7Ys29OjRg2HDhukGmkdw+3KJYWFh7N69O80bte6laNGiKZ5Brlix4n2fm42NjaWDjw9JO3fyaXQ0\n91qePgoYkyMHywoUoHytWinmY75dly5dmD59uubNlixD5St2J7su2mBr169fZ8uWLcmnqnft2kV8\nfPwDHaNAgQIpnkGuVq1aiv9vDMOgc/v2JKxZw5cxMaT3auxEYAIQfcfrpUuXZv78+fj4+DxQThF7\np/IVu5XdF22wtduXSwwLC2Pbtm3pvov6X3ny5EnxDPK5c+cY2aULOyMjeZBZlA3gFeA7IIGbj00N\nHDiQMWPGZMuJRCTrU/mKXTO0aINp/l0u8d+R8datW4mKinqgY+RxdGRGUhJv3vF6HNAbWA9cAp4E\nJgG3j2cPATUBr+rV+fjjj6lZs+ZDfxcRe6fylUxBizaY7/blEsPCwti0aRPXrl2753s8gfOAxx2v\nRwNBwJvA48AqoBOwFyh1236NXV3p/ckndO7cOaO+hohdUvlKphIREcGYMWMICQlh+PDhWrTBRP8u\nl3j7402XLl1Ksc9rQNozLqdWDRgDtL/ttYXAD889x9erVmVAYhH7pfKVTOnAgQMMHjyYY8eOadEG\ni9y+XGJYWBj/W7mSwdHRjE7He88BpYFwoNxtr68FJteqxfpffrFBYhH7ofKVTG316tUMHDhQizbY\ngeFDhuARGMjI++wXDzwLlAXm37HtJ2B8jRps2L3bFhFF7IYWupRM7ZlnniE8PJyXXnoJHx8f3nrr\nLc6cOWN1rGwpf6FCnL/PVI9J3Dw17QbMSWP7eSBf/vwZH07Ezqh8JdNzdnamV69eHD58mAIFClCl\nShUmTJiQ5kT8YjstW7bkO2dnEu6y3QDeAiKAb4G0ntwO8fTkmRdftFVEEbuh8pUsI0+ePAQGBrJj\nxw727NlD+fLl+fLLL9GVFXNUq1aN0mXLsuIu23tz83GiUMA1je2ngJ8Ngy6vvmqriCJ2Q+UrWc6T\nTz7JN998w6JFi5g+fToNGjRg69atVsfKFvoMGcIMT0/uXA7hL+Ajbt5gVRTIdevnq9v2menkROfO\nncmZM6c5YUUspBuuJEtLSkpi0aJFDB8+HG9vbyZPnpxqFR3JOHFxcTxVvz719u8nKC6O9N5//jXQ\n3cmJHb//TsWKFW0ZUcQuaOQrWZqjoyOvv/46hw8fpkKFCtSqVYthw4bdd7IIeTg5cuRg+bp1rC1Z\nkrddXbnfzNEG8AE3J9+ITExkwIABDzzftEhmpPKVbMHT05PRo0fz+++/c+bMGby8vAgODn7gVX7k\n/vLnz0/Yr79yytub0h4ejHF25p879rkOzAPKOTszCPj31rg1a9bQr18/XaeXLE/lK9lK8eLFWbhw\nIStXruSLL76gRo0arFu3zupYWU6ePHlYvm4da3bu5MIbb1DF3Z3yuXJRL08eKufOTUlXV37y8WFW\naCiV69ZN8d4PP/yQ6dOnW5RcxBy65ivZ1p2LNgQFBVG+fHmrY2VJUVFR/PXXX1y9ehVPT0+KFy+e\nPDf3uXPnqF+/PidOnEje38HBge+++4527dpZlFjEtlS+ku39u2jD5MmT6dy5sxZtsMCBAwdo0KBB\nimvx7u7uhIWFUbt2bQuTidiGTjtLtufq6srgwYM5ePAgiYmJlC9fnhkzZhAXF2d1tGyjYsWKfPPN\nNzg5/f/UGzExMbRp04aTJ09amEzENlS+IrcUKlSIuXPnsnHjRtauXUvlypVZvnw5hmEwbtw4li5d\nqhuBbKhly5bMn59ytuezZ8/i6+vL9evXLUolYhs67SxyF/8u2uDp6cmvv/5KUlISjRo1Yvr06dS9\n4yYhyTgBAQEEBQWleO3ZZ58lNDQUZ2dni1KJZCyVr8g9xMfHU61aNQ4ePJji9S5dujBp0iRKlixp\nUbKsKykpiY4dO/Ldd9+leL1v377Mnj1bS0dKlqDyFbmHgwcPUrVqVRISUi8X4O7uzuDBgwkICNCU\niBksOjqaZs2asWvXrhSv//e//6V///4WpRLJOLrmK3IPFSpUYN++fbRp0ybVtpiYGMaPH0+5cuX4\n9NNPSUq6c0ZjeVgeHh6Ehoby+OOPp3h9wIABrFhxt6UbRDIPjXxF0mndunUMGjSI33//Pc3tNWrU\nYPr06TRr1szcYFnY3r17adSoUYobrjw9Pdm0aRM1atSwMJnIo9HIVySdnn76aXbv3k1wcDBFihRJ\ntX3Pnj00b96c9u3bc+zYMQsSZj1VqlRh6dKlKR5BioqKwtfXl1OnTlmYTOTRqHxFHoCTkxPdu3fn\n6NGjDBs2DFfX1CvTLlu2jIoVKzJw4EAuX75sQcqsxcfHh9mzZ6d47fTp07Rp04bIyEiLUok8Gp12\nFnkEf/31F0OHDmXJkiVpbi9QoABjxoyhZ8+euLi4mJwuaxk4cCAzZsxI8Zqvry/Lli1LMTIWyQxU\nviIZYNu2bQwYMIAdO3akub18+fJMnTqV5557To/KPKTExEQ6dOhAaGhoitffeecdZs6caVEqkYej\n8hXJIIbRYqJKAAAWaUlEQVRhsGTJEoYMGXLXKRFbtmzJtGnTqFKlisnpsoaoqCiaNGnC7t27U7w+\ne/Zs3n77bYtSiTw4la9IBouJiWHGjBlMmjQpzWuSjo6OdO/enfHjx1O4cGELEmZup0+fpl69eilu\nuHJ0dCQ0NJTWrVtbmEwk/VS+IjZy9uxZRo4cySeffJLmnNC5cuVixIgR9O/fHzc3t/se7/z580RE\nRJCYmEi+fPkoUaJEtj2FHR4ejre3d4pfbnLmzMnmzZupVq2ahclE0kflK2Jj4eHhDBw4kJ9++inN\n7aVLl2bKlCl07NgxVZnGxsby7bffMm/KFPYfPsxjOXLg5OBARHw8efPnp/fgwbzRtSt58+Y146vY\nlf/973+0adMmxeQmJUqUYMeOHRQrVszCZCLpYIiIzSUlJRnLly83ypYtawBp/jRq1MjYsWNH8ntC\nQ0ONIrlzG0/lymV8B0Y8GMatnyQwNoHRycPDyOvmZkyZMMFISkqy8BtaY/bs2an+PtasWdOIioqy\nOprIPWnkK2KiuLg45s+fz9ixY+/6DHCXLl2oUbUq08aM4duYGBrc55h/A209PGjSpQszP/ww252K\n7t+/P7NmzUr+66FDhzJhwgQcHTWNgdgvla+IBS5dusTYsWOZN29emos25AZ2AeXSebxrQFMPD14e\nNoyhI0dmYFL7l5iYSLt27fjxxx/x8vKiWbNmWv1I7J7KV8RChw8fxt/fP8ViAZ7Ad0CrBzzWP0Bl\nNzeO/P03hQoVysCU9i8yMpLw8HAqV65Mo0aN8PPz0+pHYtd0XkbEQl5eXoSGhrJu3TqqVq0KQGGg\n5T3ecxRwA1674/XiQHsHBz4JDrZJVnuWM2dOGjVqRJ48eVi1ahWBgYFa/Ujsmka+InYiMTGRhlWr\n0vXAAXrfY79WwA2gNPD5Hdt+AV4sVIjjZ85k6ykXd+7cia+vL6tXr9bqR2KXNPIVsRNOTk7sPXqU\nV+6xzxIgH/AUN2/tvVNtwDkmhsOHD9siYqZRt25d5s+fT9u2bbX6kdglla+Inbhx4wYJiYnc7Ynd\na8BoYAZpF++/Cjs5cenSpQzPl9m88MIL9OvXT6sfiV1S+YrYifs9GjMK6A4UA+51H6+RjmNlF/7+\n/tSuXZtOnTqRmJhodRyRZPo3VMRO5MiRA1cXFy6kse03YD3w7q2/vtvI1wBOJyRQoEABW0TMdBwc\nHJg3bx43btxg4MCBVscRSabyFbEjbZ99lkVpPJ+6ETgBPA48BkwDvuXmNd7bbQaiEhKIioqybdBM\nxMXFhZCQENatW8ecOXOsjiMC6G5nEbuyZcsW3nzmGQ5FRaX4zTgGuH7rzwYwlZtl/AFw+xi3LbCC\nmyO+V199lfHjx1OqVCkTktu/P//8k0aNGhEcHKzVj8RyGvmK2JGGDRviUbQo39/xujs3n/8tDBQB\nct567fbiPQqsufVnwzD44osv8PLyIiAg4K5TWWYnTzzxBN999x1vvvkm4eHhVseRbE4jXxE7s3Xr\nVtq1bMkP0dHUSud7zgG1HR35JykpzevB+fLlY+TIkfTt2xdXV9cMTJv5hISEMGjQILZv367Vj8Qy\nGvmK2JmGDRsSvHgxz3p4sJx7P1YEEA408PCgx4gRrPrf/6hcuXKqfS5fvsygQYMoX748X375ZYpl\n+LKbjh070rt3b9q0aaNr42IZjXxF7NTmzZvp3qkTLleu0CcykleBXLe2xQPLgXk5c3LA0ZHJM2bQ\ntVs34OZMWZ9//jmjRo3in3/+SfPYNWvWJCgoiBYtWpjxVeyOYRi89dZbXLx4ke+++y5bzwYm1lD5\nitgxwzD46aefmD91KivWrsXT2RknBweuxMVRv0oV+g4dSocOHciRI0eq90ZHRzNz5kwmTZrE9evX\n0zg6PPvss0yZMoUqVarY+qvYnbi4OHx8fKhRowbTpk2zOo5kMypfkUwiISGBq1evkpCQQL58+dIs\n3LREREQwfvx45s+fn+byhY6OjnTt2pVx48ZRvHjxjI5t1y5fvkyDBg1499136dWrl9VxJBtR+Ypk\nE8eOHWP48OGEhISkud3d3Z0BAwYQEBBAnjx5TE5nnePHj+Pt7c3ChQt55plnrI4j2YTKVySb2bFj\nB/7+/mzatCnN7QULFuS9996jZ8+e6R5dZ3Zbtmyhffv2rF+/Plueghfz6W5nkWymXr16bNy4keXL\nl1O+fPlU2y9cuMA777xDxYoVCQkJITv8ft6oUSNmzpxJmzZtOHv2rNVxJBvQyFckG0tISOCTTz7h\nvffe49y5c2nuU69ePYKCgmjcuLHJ6cw3fvx4VqxYwc8//4yHh4fVcSQLU/mKCJGRkUyfPp3AwMC7\nPvvatm1bJk+eTIUKFUxOZx7DMOjatSuRkZGEhIRodSixGZWviCQ7e/YsY8eOJTg4OM0l+BwdHene\nvTtjx46laNGiFiS0vdjYWFq1akW9evUIDAy0Oo5kUSpfEUnl0KFDDBs2jGXLlqW53dPTk8GDBzN4\n8GBy5sxpcjrbu3jxIg0aNMDf3x8/Pz+r40gWpPIVkbvavHkz/v7+bN++Pc3tRYoUYcyYMfTs2ROH\nNJZCzMyOHj1K48aN+eKLL2jZsqXVcSSL0QUNEbkrb29vtm7dSkhICGXKlEm1/dy5c6xfvz7LFS9A\n2bJlCQkJoUuXLuzfv9/qOJLFqHxF5J4cHBx48cUX2b9/P7Nnz6ZgwYIptl+8eJEDBw5YlM62Gjdu\nzPTp0/H19b3r3eAiD0PlKyLpkiNHDt5++22OHz/OiBEjcHd3p3fv3vj6+tKsWTN69OjBmTNnrI6Z\n4V599VXeeOMNnn/+eWJiYqyOI1mErvmKyEP5559/cHNzo0CBAly+fJlJkybx8ccf07dvX/z9/cmV\nK9f9D5JJGIbBa6+9RmxsLF9//bUeQZJHpn+CROShFC9enAIFCgCQL18+AgMD2b17N3/++SflypVj\n/vz5xMfHW5wyYzg4OPDxxx9z9uxZRo4caXUcyQJUviKSYUqVKsUXX3zBqlWr+Pbbb6lcuTLff/99\nlpii0tXVle+//56lS5fy6aefWh1HMjmddhYRmzAMgzVr1iSfgg4KCqJhw4ZWx3pkhw8fpkmTJnz1\n1Ve0aNHC6jiSSWnkKyI24eDgwDPPPMOePXvw8/Pj5Zdf5oUXXuDIkSNWR3skXl5efP3113Tq1IlD\nhw5ZHUcyKZWviNiUk5MTXbt25ciRI9SpU4eGDRvy9ttvc/78eaujPbRmzZoRGBhI69atiYiIsDqO\nZEIqXxExhbu7O0OHDuXQoUM4OztTsWJF3n///bsu5GDv3njjDTp16kS7du24ceOG1XEkk1H5ioip\nChYsyH//+1927NjB3r17KVeuHAsWLCAhIcHqaA9s3LhxlCxZkjfffJOkpCSr40gmohuuRMRSO3bs\nICAggAsXLjBlyhRat26dqaarvHHjBi1atOCpp55i/PjxVseRTELlKyKWMwyDlStXMmTIEIoUKUJg\nYCB16tSxOla6RUREUL9+fd577z3eeOMNq+NIJqDTziJiOQcHB9q0acPvv/9O586dadeuHZ06deKP\nP/6wOlq6FCpUiJUrVxIQEMDPP/9sdRzJBFS+ImI3nJ2d8fPz48iRI1SsWJE6deowYMAALl68aHW0\n+6pQoQJfffUVr7zyCocPH7Y6jtg5la+I2B1PT09GjRrFgQMHiIuLw8vLiylTptj9wgYtWrRg4sSJ\n+Pr6cuHCBavjiB1T+YqI3SpSpAhz585ly5Yt7Ny5Ey8vLz777DMSExOtjnZX3bp148UXX6R9+/bE\nxsZaHUfslG64EpFMY8uWLfj7+xMdHU1gYCCtWrWyOlKakpKSeOWVV3BxcWHRokWZ6u5tMYfKV0Qy\nFcMw+P777xk6dCilS5cmMDCQ6tWrWx0rlZiYGJo3b46Pjw9jxoyxOo7YGZ12FpFMxcHBgQ4dOrB/\n/37atWuHj48Pr7/+On/99ZfV0VJwd3dn+fLlfPbZZyxevNjqOGJnVL4ikim5uLjQp08fjhw5QunS\npalZsyYBAQFcvnzZ6mjJihQpwsqVKxkwYACbNm2yOo7YEZWviGRquXPnZty4cezdu5fLly/j5eXF\n9OnT7eZmp0qVKrF48WI6duzIsWPHrI4jdkLlKyJZQrFixQgODmbDhg1s2LCB8uXL89VXX9nFnMst\nW7Zk3LhxtG7dmkuXLlkdR+yAbrgSkSzp559/xt/fH8MwCAoKonnz5lZHwt/fn127drFmzRpy5Mhh\ndRyxkMpXRLKspKQkQkJCGDZsGBUqVGDKlClUrlzZ0jwvvvgiuXLlYuHChXoEKRvTaWcRybIcHR15\n+eWXOXjwIC1btqRFixZ0796df/75x7I8ixYt4sCBA0yYMMGSDGIfVL4ikuW5urry7rvvcuTIEQoW\nLEjVqlUZOXIk165dMz2Lh4cHoaGhBAcH89VXX5n++WIfVL4ikm3kzZuXyZMns2fPHk6dOkW5cuWY\nM2cOcXFxpuZ47LHHWLlyJf3792fr1q2mfrbYB5WviGQ7jz/+OAsXLmT16tWsXLmSSpUq8c0332Dm\nLTBVqlTh888/54UXXuD48eOmfa7YB91wJSLZ3tq1awkICMDNzY2goCC8vb1N++z58+czc+ZMtm3b\nRr58+Uz7XLGWyldEhJt3Ii9evJiRI0dSo0YNJk+eTPny5U357IEDB/Lbb7/x448/6hGkbEKnnUVE\nuHkn8muvvcbhw4dp1KgRjRs3pnfv3pw9e9bmnx0UFESuXLno1auXqae+xToqXxGR27i5ueHv78+h\nQ4fw8PCgUqVKjB07lsjISJt9ppOTE19++SXh4eFMnjzZZp8j9kPlKyKShgIFCjBt2jR++eUXjhw5\nQrly5fjwww9JSEiwyed5enqyYsUK5s+fz9KlS23yGWI/dM1XRCQdfvnlF/z9/Tl79iyTJ0+mbdu2\nNpmhKjw8nJYtWxIaGkr9+vUz/PhiH1S+IiLpZBgGP/zwAwEBAeTPn5+goCDq1auX4Z+zatUq/Pz8\n2Lp1K6VLl87w44v1dNpZRCSdHBwceO655wgPD6dr16688MILvPTSSxm+VGDr1q0ZNmwYrVu35sqV\nKxl6bLEPKl8RkQfk5OREt27dOHLkCNWrV6d+/fq88847REREZNhn9OvXj6eeeoqOHTsSHx+fYccV\n+6DyFRF5SB4eHgwfPpyDBw9iGAYVKlRg4sSJREdHZ8jxZ8yYgaurK3379tUjSFmMyldE5BEVKlSI\n2bNns23bNvbs2YOXlxeffvopiYmJj3RcJycnvvrqK3bu3MnUqVMzKK3YA91wJSKSwbZv346/vz9X\nrlwhMDAQHx+fR7oz+tSpUzRo0ICZM2fSoUOHDEwqVlH5iojYgGEYhIaGMmTIEIoXL05gYCC1atV6\n6OPt3r0bHx8fVq1aRZ06dTIwqVhBp51FRGzAwcGB559/nn379vHSSy/h6+tLly5dOHHixEMdr2bN\nmixYsIB27drx119/ZWxYMZ3KV0TEhpydnenZsydHjx6lbNmy1KpVi0GDBnHp0qUHPlbbtm3x9/fH\n19eXq1ev2iCtmEXlKyJigpw5czJmzBj27dtHVFQUXl5eTJ06lRs3bjzQcfr370+TJk14+eWXbTbV\npdieyldExESPPfYYH3zwAWFhYWzevBkvLy8WLVpEUlJSut7v4ODAzJkzcXR0pF+/fnoEKZPSDVci\nIhbatGkT/v7+xMXFERgYyNNPP52u9127dg1vb2+6du3KwIEDbZxSMprKV0TEYoZh8O233zJ06FDK\nlCnDlClTqFat2n3f9/fff9OwYUPmzJlDu3btTEgqGUWnnUVELObg4MCLL77IgQMHaN26Na1ataJr\n166cPHnynu97/PHHWbZsGX5+fvz6668mpZWMoPIVEbETOXLkoF+/fhw5coTixYtTvXp1hg0bds87\nm2vXrk1wcDDPP//8fcta7IfKV0TEzuTJk4cJEyYQHh7O+fPnKVeuHDNnziQuLi7N/du1a8eAAQPw\n9fXl+vXrJqeVh6FrviIidm7v3r0MGTKEw4cPM3HiRF566aVU01UahkGvXr04deoUy5cvx9nZOXnb\noUOH2LBhA5cuXcLJyYlChQrh6+tLkSJFzP4qcovKV0Qkk1i/fj0BAQE4OTkRFBRE06ZNU2yPj4+n\ndevWeHl5MWPGDEJDQ5k7eTL79u6ljYMDhWNjSXRw4G83N35ISOA5Hx/6DB5Mo0aNHmnuaXlwKl8R\nkUwkKSmJJUuWMGLECKpUqcLkyZOpWLFi8varV69Sv359iI4mz6VL9I+MpAPgesdxLgOfOTgwy8MD\nn5dfZtaHH6YYLYtt6ZqviEgm4ujoSOfOnTl06BDNmjWjWbNm9OjRg9OnTwM375x2unGD5n//zZbI\nSDqRungB8gHvGga/RUVxbMkSXu/YMd0TfcijU/mKiGRCrq6uDBw4kMOHD5M3b16qVKnCe++9R6e2\nbWly5gxzAad0HCc3sDw6mhNr1jBxzBjbhpZkOu0sIpIF/PXXX/Tt25ftq1ZxBnB5wPf/CdTx9OTv\n8+fx8PCwQUK5nUa+IiJZQKlSpSheoAD9nZzSLN5mgDuQ69ZPhTu2PwHUd3BgyZIltg0qgEa+IiJZ\nwvXr13m8SBEOxsRQNI3tzYHXgG73OMb/gNFeXuw6dMgmGeX/aeQrIpIFHD16lFIuLmkW77/uN9J6\nCgg/dkwrJZlA5SsikgVcvXqVPPd5VncYUAjwBjamsd2Vm6UQExOT4fkkJZWviEgW4OHhwb0qcwo3\nb6o6DfQA2gB/3LFPIhCflISbm5ttQkoyla+ISBZQokQJ/oiNJfYu2+sCnty8C/p1oBE3r/He7iBQ\nLF8+HB1VDbamv8MiIllA8eLFqVm9Ot88wjE+dHWla48eGZZJ7k7lKyKSRfQZMoR5uXKlev0qsBq4\nASQAi4FNgM9t+0Teer1Hnz62DyoqXxGRrMLX15fT7u6pRr/xwCigMDdvuJoLLAfK3LbPWBcXWjRv\nTsmSJc0Jm83pOV8RkSxkz549tGrcmC+jomiZzvdMc3Liw6JF2frbbxQsWNCm+eQmjXxFRLKQGjVq\n8N0PP/BqrlxMdHTk0j32/QPwy5GDj0uUYO2WLSpeE6l8RUSymMaNG7P511853KEDT7q58aa7O6uA\nHcBW4GvguZw5qZczJ3l79WLLnj2UKlXK2tDZjE47i4hkYRcuXOCTBQtY9/33XL58GWdnZwoWKsSL\n3brx0ksv4e7ubnXEbEnlKyIiYjKddhYRETGZyldERMRkKl8RERGTqXxFRERMpvIVERExmcpXRETE\nZCpfERERk6l8RURETKbyFRERMZnKV0RExGQqXxEREZOpfEVEREym8hURETGZyldERMRkKl8RERGT\nqXxFRERMpvIVERExmcpXRETEZCpfERERk6l8RURETKbyFRERMZnKV0RExGQqXxEREZOpfEVEREym\n8hURETGZyldERMRkKl8RERGTqXxFRERMpvIVERExmcpXRETEZCpfERERk6l8RURETKbyFRERMZnK\nV0RExGQqXxEREZOpfEVEREym8hURETGZyldERMRkKl8RERGTqXxFRERMpvIVERExmcpXRETEZCpf\nERERk6l8RURETKbyFRERMZnKV0RExGQqXxEREZOpfEVEREym8hURETGZyldERMRk/wcKcGNQLCn0\nyAAAAABJRU5ErkJggg==\n",
       "text": [
        "<matplotlib.figure.Figure at 0x47a6cd0>"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We want to count how many shared neighbors each pair has.  Our result should look something like the following"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "shared_neighbors = {(1, 5): {2, 4},\n",
      "                    (1, 6): {2},\n",
      "                    (5, 6): {2}}\n",
      "\n",
      "num_shared_neighbors = {(1, 5): 2,\n",
      "                        (1, 6): 1,\n",
      "                        (5, 6): 1}"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To acheive this we can join the edges dataset with itself on the target node.\n",
      "\n",
      "Below we do this with a naive nested Python list comprehension.  This is much slower most Join operations in standard backends."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "joined_edges = [(tgt1, a, b) for (a, tgt1) in sub_edges\n",
      "                             for (b, tgt2) in sub_edges\n",
      "                             if tgt1 == tgt2\n",
      "                             if a < b]\n",
      "joined_edges"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "[(2, 1, 5), (2, 1, 6), (4, 1, 5), (2, 5, 6)]"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Notice that the node 2 connects three pairs, `(1, 5), (1, 6)`, and `(5, 6)` while 4 connects one pair `(1, 5)`\n",
      "\n",
      "After this join operation we can perform a grouping operation to get out the shared neighbors"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from toolz import groupby, first, valmap\n",
      "\n",
      "groups = groupby(lambda (tgt, a, b): (a, b), joined_edges)\n",
      "shared_neighbors = {k: set(map(first, v)) for k, v in groups.items()}\n",
      "shared_neighbors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "{(1, 5): {2, 4}, (1, 6): {2}, (5, 6): {2}}"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "And so the number of shared neighbors is just the length of these values"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "num_shared_neighbors = valmap(len, shared_neighbors)\n",
      "num_shared_neighbors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "{(1, 5): 2, (1, 6): 1, (5, 6): 1}"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Total neighbors\n",
      "\n",
      "Now that we have the number of shared neighbors (the hard part) we just need to compute the total number of neighbors per node, and then do a joined add / divide"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# A simple split-apply-combine - this could be made more efficient\n",
      "out_neighbors = groupby(lambda (a, b): a, sub_edges)\n",
      "out_degree = valmap(len, out_neighbors)\n",
      "out_degree"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "{1: 2, 5: 2, 6: 2}"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now we need to join the datasets `shared_neighbors` with `out_degree`.  Here we'll do it naively with a triple Join"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "jaccard = [(a, b, c / (aout + bout)) for (a, b), c in num_shared_neighbors.items()\n",
      "                                     for a2, aout in out_degree.items()\n",
      "                                     for b2, bout in out_degree.items()\n",
      "                                     if a == a2 \n",
      "                                    and b == b2]\n",
      "                                     "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "TypeError",
       "evalue": "unsupported operand type(s) for /: 'set' and 'int'",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-13-2d331e433b37>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      3\u001b[0m                                      \u001b[1;32mfor\u001b[0m \u001b[0mb2\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mbout\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mout_degree\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m                                      \u001b[1;32mif\u001b[0m \u001b[0ma\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0ma2\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m                                     and b == b2]\n\u001b[0m\u001b[0;32m      6\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;31mTypeError\u001b[0m: unsupported operand type(s) for /: 'set' and 'int'"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}