{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Parallel Betweenness\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\nNote: The example output below shows that the non-parallel implementation is\nfaster. This is a limitation of our CI/CD pipeline running on a single core.\n\nDepending on your setup, you will likely observe a speedup.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "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 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(), G.order() // node_divisor))\n    num_chunks = len(node_chunks)\n    bt_sc = p.starmap(\n        nx.betweenness_centrality_subset,\n        zip(\n            [G] * num_chunks,\n            node_chunks,\n            [list(G)] * num_chunks,\n            [True] * num_chunks,\n            [None] * num_chunks,\n        ),\n    )\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\nG_ba = nx.barabasi_albert_graph(1000, 3)\nG_er = nx.gnp_random_graph(1000, 0.01)\nG_ws = nx.connected_watts_strogatz_graph(1000, 4, 0.1)\nfor G in [G_ba, G_er, G_ws]:\n    print(\"\")\n    print(\"Computing betweenness centrality for:\")\n    print(G)\n    print(\"\\tParallel version\")\n    start = time.time()\n    bt = betweenness_centrality_parallel(G)\n    print(f\"\\t\\tTime: {(time.time() - start):.4F} seconds\")\n    print(f\"\\t\\tBetweenness centrality for node 0: {bt[0]:.5f}\")\n    print(\"\\tNon-Parallel version\")\n    start = time.time()\n    bt = nx.betweenness_centrality(G)\n    print(f\"\\t\\tTime: {(time.time() - start):.4F} seconds\")\n    print(f\"\\t\\tBetweenness centrality for node 0: {bt[0]:.5f}\")\nprint(\"\")\n\nnx.draw(G_ba, node_size=100)\nplt.show()"
      ]
    }
  ],
  "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.12.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}