{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Community Detection using Girvan-Newman\n\nThis example shows the detection of communities in the Zachary Karate\nClub dataset using the Girvan-Newman method.\n\nWe plot the change in modularity as important edges are removed. \nGraph is coloured and plotted based on community detection when number \nof iterations are 1 and 4 respectively.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import networkx as nx\nimport pandas as pd\nimport matplotlib.pyplot as plt\n\n# Load karate graph and find communities using Girvan-Newman\nG = nx.karate_club_graph()\ncommunities = list(nx.community.girvan_newman(G))\n\n# Modularity -> measures the strength of division of a network into modules\nmodularity_df = pd.DataFrame(\n    [\n        [k + 1, nx.community.modularity(G, communities[k])]\n        for k in range(len(communities))\n    ],\n    columns=[\"k\", \"modularity\"],\n)\n\n\n# function to create node colour list\ndef create_community_node_colors(graph, communities):\n    number_of_colors = len(communities[0])\n    colors = [\"#D4FCB1\", \"#CDC5FC\", \"#FFC2C4\", \"#F2D140\", \"#BCC6C8\"][:number_of_colors]\n    node_colors = []\n    for node in graph:\n        current_community_index = 0\n        for community in communities:\n            if node in community:\n                node_colors.append(colors[current_community_index])\n                break\n            current_community_index += 1\n    return node_colors\n\n\n# function to plot graph with node colouring based on communities\ndef visualize_communities(graph, communities, i):\n    node_colors = create_community_node_colors(graph, communities)\n    modularity = round(nx.community.modularity(graph, communities), 6)\n    title = f\"Community Visualization of {len(communities)} communities with modularity of {modularity}\"\n    pos = nx.spring_layout(graph, k=0.3, iterations=50, seed=2)\n    plt.subplot(3, 1, i)\n    plt.title(title)\n    nx.draw(\n        graph,\n        pos=pos,\n        node_size=1000,\n        node_color=node_colors,\n        with_labels=True,\n        font_size=20,\n        font_color=\"black\",\n    )\n\n\nfig, ax = plt.subplots(3, figsize=(15, 20))\n\n# Plot graph with colouring based on communities\nvisualize_communities(G, communities[0], 1)\nvisualize_communities(G, communities[3], 2)\n\n# Plot change in modularity as the important edges are removed\nmodularity_df.plot.bar(\n    x=\"k\",\n    ax=ax[2],\n    color=\"#F2D140\",\n    title=\"Modularity Trend for Girvan-Newman Community Detection\",\n)\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
}