{
  "nbformat_minor": 0, 
  "nbformat": 4, 
  "cells": [
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "%matplotlib inline"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }, 
    {
      "source": [
        "\n# Parallel Betweenness\n\n\nExample of parallel implementation of betweenness centrality using the\nmultiprocessing module from Python Standard Library.\n\nThe function betweenness centrality accepts a bunch of nodes and computes\nthe contribution of those nodes to the betweenness centrality of the whole\nnetwork. Here we divide the network in chunks of nodes and we compute their\ncontribution to the betweenness centrality of the whole network.\n\nThis doesn't work in python2.7.13. It does work in 3.6, 3.5, 3.4, and 3.3.\n\nIt may be related to this:\nhttps://stackoverflow.com/questions/1816958/cant-pickle-type-instancemethod-when-using-multiprocessing-pool-map\n\n"
      ], 
      "cell_type": "markdown", 
      "metadata": {}
    }, 
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "from multiprocessing import Pool\nimport time\nimport itertools\n\nimport matplotlib.pyplot as plt\nimport networkx as nx\n\n\ndef chunks(l, n):\n    \"\"\"Divide a list of nodes `l` in `n` chunks\"\"\"\n    l_c = iter(l)\n    while 1:\n        x = tuple(itertools.islice(l_c, n))\n        if not x:\n            return\n        yield x\n\n\ndef _betmap(G_normalized_weight_sources_tuple):\n    \"\"\"Pool for multiprocess only accepts functions with one argument.\n    This function uses a tuple as its only argument. We use a named tuple for\n    python 3 compatibility, and then unpack it when we send it to\n    `betweenness_centrality_source`\n    \"\"\"\n    return nx.betweenness_centrality_source(*G_normalized_weight_sources_tuple)\n\n\ndef betweenness_centrality_parallel(G, processes=None):\n    \"\"\"Parallel betweenness centrality  function\"\"\"\n    p = Pool(processes=processes)\n    node_divisor = len(p._pool) * 4\n    node_chunks = list(chunks(G.nodes(), int(G.order() / node_divisor)))\n    num_chunks = len(node_chunks)\n    bt_sc = p.map(_betmap,\n                  zip([G] * num_chunks,\n                      [True] * num_chunks,\n                      [None] * num_chunks,\n                      node_chunks))\n\n    # Reduce the partial solutions\n    bt_c = bt_sc[0]\n    for bt in bt_sc[1:]:\n        for n in bt:\n            bt_c[n] += bt[n]\n    return bt_c\n\n\nif __name__ == \"__main__\":\n    G_ba = nx.barabasi_albert_graph(1000, 3)\n    G_er = nx.gnp_random_graph(1000, 0.01)\n    G_ws = nx.connected_watts_strogatz_graph(1000, 4, 0.1)\n    for G in [G_ba, G_er, G_ws]:\n        print(\"\")\n        print(\"Computing betweenness centrality for:\")\n        print(nx.info(G))\n        print(\"\\tParallel version\")\n        start = time.time()\n        bt = betweenness_centrality_parallel(G)\n        print(\"\\t\\tTime: %.4F\" % (time.time() - start))\n        print(\"\\t\\tBetweenness centrality for node 0: %.5f\" % (bt[0]))\n        print(\"\\tNon-Parallel version\")\n        start = time.time()\n        bt = nx.betweenness_centrality(G)\n        print(\"\\t\\tTime: %.4F seconds\" % (time.time() - start))\n        print(\"\\t\\tBetweenness centrality for node 0: %.5f\" % (bt[0]))\n    print(\"\")\n\n    nx.draw(G_ba)\n    plt.show()"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }
  ], 
  "metadata": {
    "kernelspec": {
      "display_name": "Python 2", 
      "name": "python2", 
      "language": "python"
    }, 
    "language_info": {
      "mimetype": "text/x-python", 
      "nbconvert_exporter": "python", 
      "name": "python", 
      "file_extension": ".py", 
      "version": "2.7.12", 
      "pygments_lexer": "ipython2", 
      "codemirror_mode": {
        "version": 2, 
        "name": "ipython"
      }
    }
  }
}