demo/Louvain.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Louvain Community Detection\n",
    "\n",
    "Community  detection  is  a  critical  component  in  the  anal-isys  of  real-world  network  systems  with  important  appli-cations  in  social  media  analytics,  biology,  recommendationsystems, and telecommunications among others [1]. The Lou-vain  method  [2]  based  on  modularity  optimization  [3]  is  acommonly adopted technique to identify communities.\n",
    "\n",
    "https://users.ece.cmu.edu/~lowt/papers/Louvain_accepted.pdf\n",
    "\n",
    "First import and define some utility functions for benchmarking the louvain method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "from random import choice\n",
    "from time import time\n",
    "\n",
    "from pygraphblas import *\n",
    "from pygraphblas import lib\n",
    "from pygraphblas.gviz import draw\n",
    "\n",
    "from collections import defaultdict\n",
    "from itertools import groupby\n",
    "from operator import itemgetter\n",
    "\n",
    "def group_labels(T):\n",
    "    d = defaultdict(list)\n",
    "    for k,v in groupby(T, itemgetter(1)):\n",
    "        d[k].append(list(v)[0][0])\n",
    "    return d\n",
    "\n",
    "def compare_groups(left, right):\n",
    "    left = {k: set(v) for k, v in left.items()}\n",
    "    right = {k: set(v) for k, v in right.items()}\n",
    "    return sorted(left.values()) == sorted(right.values())\n",
    "\n",
    "def get_louvain_cluster_assignments(cluster_matrix):\n",
    "    return cluster_matrix.cast(INT64).apply(INT64.POSITIONJ).reduce_vector()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a Matrix to be used for quick testing.  It creates two communities that the algorithm should detect:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "I = [0, 0, 0, 0,\n",
    "    1, 1, 1, 1,\n",
    "    2, 2, 2, 2,\n",
    "    3, 3, 3, 3,\n",
    "    4, 4, 4, 4,\n",
    "    5, 5, 5, 5, 5,\n",
    "    6, 6, 6,\n",
    "    7, 7, 7, 7]\n",
    "\n",
    "J = [0, 2, 3, 6,\n",
    "    1, 2, 3, 7,\n",
    "    0, 2, 4, 6,\n",
    "    0, 1, 3, 5,\n",
    "    0, 2, 4, 6,\n",
    "    1, 3, 5, 6, 7,\n",
    "    0, 4, 6,\n",
    "    1, 3, 5, 7]\n",
    "\n",
    "M = Matrix.from_lists(I, J, [1.0] * len(I), typ=FP64)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Current  implementations  of  the  Louvain  method  adopt  atraditional  vertex-based  approach  in  their  algorithmic  for-mulation  despite  there  being  a  linear  algebraic  formulationfor  the  computation  of  modularity  [4].  In  this  paper,  weshow  that  by  starting  with  the  linear  algebraic  formulationof  modularity,  a  linear  algebraic  algorithm  for  computingthe  Louvain  method  can  be  determined.  This  formulationcan  leverage  recent  community-driven  efforts  behind  linearalgebraic  graph  interfaces,  such  as  the  GraphBLAS  [5],  torapidly  develop  an  implementation  of  the  Louvain  method.Productivity  is  enhanced  through  the  use  of  pygraphblas  [6],a python interface for the GraphBLAS effort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def louvain_cluster_easy(A, max_iters=10):\n",
    "    S = Matrix.identity(BOOL, A.nrows)\n",
    "    empty = Vector.sparse(BOOL, A.nrows)\n",
    "    i = 0\n",
    "    changed = True\n",
    "    \n",
    "    start = time()\n",
    "    G = A.T + A\n",
    "    k = A.reduce_vector()\n",
    "    m = k.reduce_int() / 2.0\n",
    "    k = (-k) / m\n",
    "    while changed and i < max_iters:\n",
    "        changed = False\n",
    "        for j in set(k.indexes):\n",
    "            Sj = S[j]\n",
    "            S[j] = empty\n",
    "            v = G[j] + k[j]\n",
    "            q = v @ S\n",
    "            t = q.select('max')\n",
    "            if t:\n",
    "                r = choice(list(t.indexes))\n",
    "                S[j, r] = True\n",
    "                if Sj.get(r) is None:\n",
    "                    changed = True\n",
    "        i += 1\n",
    "    return S, time() - start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def louvain_cluster(A, max_iters=10):\n",
    "    An = A.nrows\n",
    "    S = Matrix.identity(BOOL, An)\n",
    "    empty = Vector.sparse(BOOL, An)\n",
    "    Sj = Vector.sparse(BOOL, An)\n",
    "    v = Vector.sparse(FP64, An)\n",
    "    q = Vector.sparse(FP64, An)\n",
    "    t = Vector.sparse(FP64, An)\n",
    "    i = 0\n",
    "    changed = True\n",
    "    \n",
    "    start = time()\n",
    "    G = A.T + A\n",
    "    k = A.reduce()\n",
    "    m = k.reduce_int() / 2.0\n",
    "    k = (-k) / m\n",
    "    kI = set(k.I)\n",
    "    while changed and i < max_iters:\n",
    "        changed = False\n",
    "        for j in kI:\n",
    "            S.extract_row(j, out=Sj)                  # Sj = S[j]\n",
    "            S.assign_row(j, empty)                    # S[j] = empty\n",
    "            G.extract_row(j, out=v)                   # v = G[j] + nkm[j]\n",
    "            v.apply_second(FP64.PLUS, k[j], out=v)\n",
    "            v.vxm(S, out=q)                           # q = v @ S\n",
    "            if not q:\n",
    "                continue\n",
    "            q.select('max', out=t)                    # t = q.select('max')\n",
    "            if t:\n",
    "                r = choice(list(t.indexes))\n",
    "                S[j, r] = True\n",
    "                if Sj.get(r) is None:\n",
    "                    changed = True\n",
    "        i += 1\n",
    "    return S, time() - start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"548pt\" height=\"232pt\"\n",
       " viewBox=\"0.00 0.00 548.00 232.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 228)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-228 544,-228 544,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-163\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-159.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"378\" cy=\"-102\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"378\" y=\"-98.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M45.3481,-170.014C74.1616,-176.7789 120.9629,-186 162,-186 162,-186 162,-186 234,-186 284.0978,-186 332.2819,-147.5973 358.2366,-122.7236\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.133,-166.603 35.5904,-167.6544 44.4876,-173.4069 46.133,-166.603\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"360.8994,-125.013 365.5554,-115.4961 355.9808,-120.0323 360.8994,-125.013\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"90\" cy=\"-125\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-121.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M42.9666,-149.8232C50.0595,-146.0797 57.7848,-142.0024 64.8864,-138.2544\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"41.1893,-146.8036 33.9791,-154.5666 44.4567,-152.9943 41.1893,-146.8036\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"66.8553,-141.1728 74.0655,-133.4099 63.588,-134.9821 66.8553,-141.1728\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"522\" cy=\"-64\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"522\" y=\"-60.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M41.1754,-179.666C68.621,-197.727 116.3849,-224 162,-224 162,-224 162,-224 378,-224 448.8768,-224 493.7707,-136.1839 512.2795,-90.6678\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"42.9202,-176.6204 32.6791,-173.9056 38.992,-182.4143 42.9202,-176.6204\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"515.6303,-91.7102 516.0261,-81.1228 509.1142,-89.1526 515.6303,-91.7102\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;6 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>2&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M392.0715,-90.3672C405.8472,-80.0518 427.9263,-66.2749 450,-64\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"450\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"450\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M396.6791,-80.2077C407.4046,-67.6946 420.8231,-52.0397 431.5157,-39.565\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"393.7399,-78.2587 389.8893,-88.1291 399.0547,-82.8143 393.7399,-78.2587\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"434.2425,-41.7619 438.093,-31.8915 428.9276,-37.2063 434.2425,-41.7619\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"306\" cy=\"-102\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"306\" y=\"-98.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>3&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M117.956,-129.9418C150.6022,-134.7425 205.9978,-139.8596 252,-129 262.2968,-126.5693 272.8688,-121.8578 281.8982,-117.0421\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"118.2248,-126.4413 107.8032,-128.3494 117.1401,-133.3567 118.2248,-126.4413\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"283.6933,-120.0479 290.6731,-112.0771 280.2461,-113.9555 283.6933,-120.0479\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"162\" cy=\"-64\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-60.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M111.6115,-106.6902C120.6877,-99.0007 131.2243,-90.0738 140.309,-82.3771\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.2497,-104.1039 103.8823,-113.2386 113.7747,-109.4448 109.2497,-104.1039\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"142.7929,-84.86 148.1603,-75.7253 138.268,-79.5191 142.7929,-84.86\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M324.1686,-102C331.869,-102 341.0257,-102 349.5834,-102\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"349.5868,-105.5001 359.5867,-102 349.5867,-98.5001 349.5868,-105.5001\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"234\" cy=\"-102\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-98.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;3 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>7&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M215.8273,-104.9026C191.1303,-108.8472 146.7405,-115.9373 117.8316,-120.5547\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"117.2693,-117.1 107.9465,-122.1335 118.3734,-124.0124 117.2693,-117.1\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M262.4274,-102C267.3208,-102 272.4096,-102 277.3099,-102\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.1687,-98.5001 252.1686,-102 262.1686,-105.5001 262.1687,-98.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"277.5868,-105.5001 287.5867,-102 277.5867,-98.5001 277.5868,-105.5001\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;0 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>4&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M431.8146,-18C404.4983,-18 351.25,-18 306,-18 162,-18 162,-18 162,-18 95.6528,-18 49.3962,-95.3762 29.2826,-137.0821\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"26.0073,-135.8245 24.9523,-146.3667 32.3512,-138.7833 26.0073,-135.8245\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;6 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>4&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M473.8804,-33.2569C481.6689,-38.2329 490.3143,-43.7563 498.1039,-48.7331\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"475.5807,-30.1899 465.2693,-27.7554 471.8119,-36.0888 475.5807,-30.1899\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"496.4413,-51.8241 506.7527,-54.2586 500.2101,-45.9253 496.4413,-51.8241\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M179.7415,-59.9449C194.3074,-57.1173 215.4778,-54.1552 234,-56\"/>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M234,-56C329.5929,-65.5209 354.4403,-73.8484 450,-64\"/>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M450,-64C464.3533,-61.9495 480.481,-61.7572 493.8285,-62.1601\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"493.7101,-65.6581 503.8499,-62.5867 494.0079,-58.6644 493.7101,-65.6581\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M234,-56C253.5574,-57.9479 272.1577,-70.2022 285.5525,-81.5724\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"283.4072,-84.3504 293.182,-88.4376 288.0895,-79.1469 283.4072,-84.3504\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;7 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>5&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M186.9666,-77.1768C194.0595,-80.9203 201.7848,-84.9976 208.8864,-88.7456\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"188.4567,-74.0057 177.9791,-72.4334 185.1893,-80.1964 188.4567,-74.0057\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"207.588,-92.0179 218.0655,-93.5901 210.8553,-85.8272 207.588,-92.0179\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f198f4da100>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ans, took = louvain_cluster(M, 5)\n",
    "random.seed(33)\n",
    "labels = get_louvain_cluster_assignments(ans)\n",
    "draw(M.offdiag(), show_weight=False, label_vector=labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the algorithm on the GraphChallenge.org 2017 community detection challenge data set:\n",
    "\n",
    "http://graphchallenge.mit.edu/data-sets#PartitionDatasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def py_bench(sizes):\n",
    "    random.seed(46)\n",
    "    times = []\n",
    "    for iters, size in sizes:\n",
    "        data = Matrix.from_tsv('louvain_data/simulated_blockmodel_graph_%s_nodes.tsv' % size, FP64, size, size)\n",
    "        print('Loaded', size, 'nodes.')\n",
    "        ans, took = louvain_cluster(data, max_iters=iters)\n",
    "        assignments = get_louvain_cluster_assignments(ans)\n",
    "        with open('louvain_data/simulated_blockmodel_graph_%s_nodes_truePartition.tsv' % size) as truth:\n",
    "            T = Vector.sparse(UINT8, size)\n",
    "            for line in truth:\n",
    "                i, j = map(int, line.split('\\t'))\n",
    "                T[i-1] = j\n",
    "        times.append(took)\n",
    "        print(size, f'Took {took:.4} Correct?', compare_groups(group_labels(assignments), group_labels(T)))\n",
    "    return times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below is the same algorithm with networkx authored by:\n",
    "    \n",
    "https://python-louvain.readthedocs.io/en/latest/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'community'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m/tmp/ipykernel_22910/561067630.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mimport\u001b[0m \u001b[0mcommunity\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mnetworkx\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0mnx\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mtime\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0mname\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mv\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m\"louvain_data/simulated_blockmodel_graph_{}_nodes\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'community'"
     ]
    }
   ],
   "source": [
    "import community\n",
    "import networkx as nx\n",
    "from time import time\n",
    "\n",
    "name = lambda v: \"louvain_data/simulated_blockmodel_graph_{}_nodes\".format(v)\n",
    "\n",
    "def make_dict(tup):\n",
    "    trued = {}\n",
    "    for n,c in tup:\n",
    "        trued.setdefault(c, []).append(n)\n",
    "    trued = { tuple(trued[c]):c for c in trued }\n",
    "    return trued\n",
    "\n",
    "def get_nodes_comm(name):\n",
    "    with open(name + \"_truePartition.tsv\", \"r\") as f:\n",
    "        truep = [tuple(map(int, l.split('\\t'))) for l in f]\n",
    "\n",
    "    G = nx.read_edgelist(name + \".tsv\", delimiter='\\t', data=(('weight', float),), create_using=nx.DiGraph())\n",
    "    start = time()\n",
    "    partition = community.best_partition(G.to_undirected())\n",
    "    took = time() - start\n",
    "    print(name, f'took {took}')\n",
    "    pl = [ (int(n), c) for n,c in list(partition.items()) ]\n",
    "    pl.sort()\n",
    "    return make_dict(truep), make_dict(pl), took"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def nx_bench(sizes):\n",
    "    nxtimes = []\n",
    "    for _, numv in sizes:\n",
    "        trued, pd, took = get_nodes_comm(name(numv))\n",
    "        nxtimes.append(took)\n",
    "    return nxtimes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "sizes = [(3, 5000), (3, 20000)]#, (3, 50000)]#, (3, 20000), (3, 50000)]\n",
    "\n",
    "#options_set(nthreads=1)\n",
    "\n",
    "pytimes = py_bench(sizes)\n",
    "nxtimes = nx_bench(sizes)\n",
    "\n",
    "labels = [str(s) for i, s in sizes]\n",
    "\n",
    "x = np.arange(len(labels))  # the label locations\n",
    "width = 0.35  # the width of the bars\n",
    "fig, ax = plt.subplots()\n",
    "rects1 = ax.bar(x - width/2, pytimes, width, label='pygraphblas')\n",
    "rects2 = ax.bar(x + width/2, nxtimes, width, label='NetworkX')\n",
    "\n",
    "# Add some text for labels, title and custom x-axis tick labels, etc.\n",
    "ax.set_ylabel('Time')\n",
    "ax.set_xticks(x)\n",
    "ax.set_xticklabels(labels)\n",
    "ax.legend()\n",
    "\n",
    "fig.tight_layout()\n",
    "\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}