Add community detection example to Gallery (#6526)

* Add community-detection example

* Fix plot layout

* Create subplot layout

1 files changed, 79 insertions, 0 deletions

diff --git a/examples/algorithms/plot_girvan_newman.py b/examples/algorithms/plot_girvan_newman.py
new file mode 100644
index 00000000..151c80c1
--- /dev/null
+++ b/examples/algorithms/plot_girvan_newman.py
@@ -0,0 +1,79 @@
+"""
+=======================================
+Community Detection using Girvan-Newman
+=======================================
+
+This example shows the detection of communities in the Zachary Karate
+Club dataset using the Girvan-Newman method.
+
+We plot the change in modularity as important edges are removed. 
+Graph is coloured and plotted based on community detection when number 
+of iterations are 1 and 4 respectively.
+"""
+
+import networkx as nx
+import pandas as pd
+import matplotlib.pyplot as plt
+
+# Load karate graph and find communities using Girvan-Newman
+G = nx.karate_club_graph()
+communities = list(nx.community.girvan_newman(G))
+
+# Modularity -> measures the strength of division of a network into modules
+modularity_df = pd.DataFrame(
+    [
+        [k + 1, nx.community.modularity(G, communities[k])]
+        for k in range(len(communities))
+    ],
+    columns=["k", "modularity"],
+)
+
+
+# function to create node colour list
+def create_community_node_colors(graph, communities):
+    number_of_colors = len(communities[0])
+    colors = ["#D4FCB1", "#CDC5FC", "#FFC2C4", "#F2D140", "#BCC6C8"][:number_of_colors]
+    node_colors = []
+    for node in graph:
+        current_community_index = 0
+        for community in communities:
+            if node in community:
+                node_colors.append(colors[current_community_index])
+                break
+            current_community_index += 1
+    return node_colors
+
+
+# function to plot graph with node colouring based on communities
+def visualize_communities(graph, communities, i):
+    node_colors = create_community_node_colors(graph, communities)
+    modularity = round(nx.community.modularity(graph, communities), 6)
+    title = f"Community Visualization of {len(communities)} communities with modularity of {modularity}"
+    pos = nx.spring_layout(graph, k=0.3, iterations=50, seed=2)
+    plt.subplot(3, 1, i)
+    plt.title(title)
+    nx.draw(
+        graph,
+        pos=pos,
+        node_size=1000,
+        node_color=node_colors,
+        with_labels=True,
+        font_size=20,
+        font_color="black",
+    )
+
+
+fig, ax = plt.subplots(3, figsize=(15, 20))
+
+# Plot graph with colouring based on communities
+visualize_communities(G, communities[0], 1)
+visualize_communities(G, communities[3], 2)
+
+# Plot change in modularity as the important edges are removed
+modularity_df.plot.bar(
+    x="k",
+    ax=ax[2],
+    color="#F2D140",
+    title="Modularity Trend for Girvan-Newman Community Detection",
+)
+plt.show()