.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "tutorials/stochastic_variability.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. .. rst-class:: sphx-glr-example-title .. _sphx_glr_tutorials_stochastic_variability.py: .. _tutorials-stochastic-variability: ========================================================= Stochastic Variability in Community Detection Algorithms ========================================================= This example demonstrates the use of stochastic community detection methods to check whether a network possesses a strong community structure, and whether the partitionings we obtain are meaningul. Many community detection algorithms are randomized, and return somewhat different results after each run, depending on the random seed that was set. When there is a robust community structure, we expect these results to be similar to each other. When the community structure is weak or non-existent, the results may be noisy and highly variable. We will employ several partion similarity measures to analyse the consistency of the results, including the normalized mutual information (NMI), the variation of information (VI), and the Rand index (RI). .. GENERATED FROM PYTHON SOURCE LINES 13-18 .. code-block:: Python import igraph as ig import matplotlib.pyplot as plt import itertools import random .. GENERATED FROM PYTHON SOURCE LINES 19-22 .. note:: We set a random seed to ensure that the results look exactly the same in the gallery. You don't need to do this when exploring randomness. .. GENERATED FROM PYTHON SOURCE LINES 22-24 .. code-block:: Python random.seed(42) .. GENERATED FROM PYTHON SOURCE LINES 25-27 We will use Zachary's karate club dataset [1]_, a classic example of a network with a strong community structure: .. GENERATED FROM PYTHON SOURCE LINES 27-29 .. code-block:: Python karate = ig.Graph.Famous("Zachary") .. GENERATED FROM PYTHON SOURCE LINES 30-34 We will compare it to an an Erdős-Rényi :math:`G(n, m)` random network having the same number of vertices and edges. The parameters 'n' and 'm' refer to the vertex and edge count, respectively. Since this is a random network, it should have no community structure. .. GENERATED FROM PYTHON SOURCE LINES 34-36 .. code-block:: Python random_graph = ig.Graph.Erdos_Renyi(n=karate.vcount(), m=karate.ecount()) .. GENERATED FROM PYTHON SOURCE LINES 37-38 First, let us plot the two networks for a visual comparison: .. GENERATED FROM PYTHON SOURCE LINES 38-69 .. code-block:: Python # Create subplots fig, axes = plt.subplots(1, 2, figsize=(12, 6), subplot_kw={"aspect": "equal"}) # Karate club network ig.plot( karate, target=axes[0], vertex_color="lightblue", vertex_size=30, vertex_label=range(karate.vcount()), vertex_label_size=10, edge_width=1, ) axes[0].set_title("Karate club network") # Random network ig.plot( random_graph, target=axes[1], vertex_color="lightcoral", vertex_size=30, vertex_label=range(random_graph.vcount()), vertex_label_size=10, edge_width=1, ) axes[1].set_title("Erdős-Rényi random network") plt.show() .. image-sg:: /tutorials/images/sphx_glr_stochastic_variability_001.png :alt: Karate club network, Erdős-Rényi random network :srcset: /tutorials/images/sphx_glr_stochastic_variability_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 70-71 Function to compute similarity between partitions using various methods: .. GENERATED FROM PYTHON SOURCE LINES 71-81 .. code-block:: Python def compute_pairwise_similarity(partitions, method): similarities = [] for p1, p2 in itertools.combinations(partitions, 2): similarity = ig.compare_communities(p1, p2, method=method) similarities.append(similarity) return similarities .. GENERATED FROM PYTHON SOURCE LINES 82-89 The Leiden method, accessible through :meth:`igraph.Graph.community_leiden()`, is a modularity maximization approach for community detection. Since exact modularity maximization is NP-hard, the algorithm employs a greedy heuristic that processes vertices in a random order. This randomness leads to variation in the detected communities across different runs, which is why results may differ each time the method is applied. The following function runs the Leiden algorithm multiple times: .. GENERATED FROM PYTHON SOURCE LINES 89-100 .. code-block:: Python def run_experiment(graph, iterations=100): partitions = [ graph.community_leiden(objective_function="modularity").membership for _ in range(iterations) ] nmi_scores = compute_pairwise_similarity(partitions, method="nmi") vi_scores = compute_pairwise_similarity(partitions, method="vi") ri_scores = compute_pairwise_similarity(partitions, method="rand") return nmi_scores, vi_scores, ri_scores .. GENERATED FROM PYTHON SOURCE LINES 101-102 Run the experiment on both networks: .. GENERATED FROM PYTHON SOURCE LINES 102-105 .. code-block:: Python nmi_karate, vi_karate, ri_karate = run_experiment(karate) nmi_random, vi_random, ri_random = run_experiment(random_graph) .. GENERATED FROM PYTHON SOURCE LINES 106-108 Finally, let us plot histograms of the pairwise similarities of the obtained partitionings to understand the result: .. GENERATED FROM PYTHON SOURCE LINES 108-151 .. code-block:: Python fig, axes = plt.subplots(2, 3, figsize=(12, 6)) measures = [ # Normalized Mutual Information (0-1, higher = more similar) (nmi_karate, nmi_random, "NMI", 0, 1), # Variation of Information (0+, lower = more similar) (vi_karate, vi_random, "VI", 0, max(vi_karate + vi_random)), # Rand Index (0-1, higher = more similar) (ri_karate, ri_random, "RI", 0, 1), ] colors = ["red", "blue", "green"] for i, (karate_scores, random_scores, measure, lower, upper) in enumerate(measures): # Karate club histogram axes[0][i].hist( karate_scores, bins=20, range=(lower, upper), density=True, # Probability density alpha=0.7, color=colors[i], edgecolor="black", ) axes[0][i].set_title(f"{measure} - Karate club network") axes[0][i].set_xlabel(f"{measure} score") axes[0][i].set_ylabel("PDF") # Random network histogram axes[1][i].hist( random_scores, bins=20, range=(lower, upper), density=True, alpha=0.7, color=colors[i], edgecolor="black", ) axes[1][i].set_title(f"{measure} - Random network") axes[1][i].set_xlabel(f"{measure} score") axes[0][i].set_ylabel("PDF") plt.tight_layout() plt.show() .. image-sg:: /tutorials/images/sphx_glr_stochastic_variability_002.png :alt: NMI - Karate club network, VI - Karate club network, RI - Karate club network, NMI - Random network, VI - Random network, RI - Random network :srcset: /tutorials/images/sphx_glr_stochastic_variability_002.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 152-169 We have compared the pairwise similarities using the NMI, VI, and RI measures between partitonings obtained for the karate club network (strong community structure) and a comparable random graph (which lacks communities). The Normalized Mutual Information (NMI) and Rand Index (RI) both quantify similarity, and take values from :math:`[0,1]`. Higher values indicate more similar partitionings, with a value of 1 attained when the partitionings are identical. The Variation of Information (VI) is a distance measure. It takes values from :math:`[0,\infty]`, with lower values indicating higher similarities. Identical partitionings have a distance of zero. For the karate club network, NMI and RI value are concentrated near 1, while VI is concentrated near 0, suggesting a robust community structure. In contrast the values obtained for the random network are much more spread out, showing inconsistent partitionings due to the lack of a clear community structure. .. GENERATED FROM PYTHON SOURCE LINES 171-172 .. [1] W. Zachary: "An Information Flow Model for Conflict and Fission in Small Groups". Journal of Anthropological Research 33, no. 4 (1977): 452–73. https://www.jstor.org/stable/3629752 .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.974 seconds) .. _sphx_glr_download_tutorials_stochastic_variability.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: stochastic_variability.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: stochastic_variability.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: stochastic_variability.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_