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).

import igraph as ig
import matplotlib.pyplot as plt
import itertools
import random

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.

random.seed(42)

We will use Zachary’s karate club dataset [1], a classic example of a network with a strong community structure:

karate = ig.Graph.Famous("Zachary")

We will compare it to an an Erdős-Rényi \(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.

random_graph = ig.Graph.Erdos_Renyi(n=karate.vcount(), m=karate.ecount())

First, let us plot the two networks for a visual comparison:

# 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()