Stochastic Block Models & Planted Partition Models

A generative, inferential view of community structure: assume the network was produced by hidden groups, then work backwards to recover them.

Most widely adopted models for building networks with communities

Motivation

Generative Models in Community Structure

  • Generative Models: Aim to explain how observed data could be generated by underlying processes.
  • Purpose: Provide insights into the formation and evolution of communities within networks.
  • Applications: Useful in social networks, biological systems, and information networks to identify functional groups.
  • Benefits:
    • Enhance understanding of complex systems.
    • Predict future interactions or changes in the network.
    • Inform strategies for intervention or optimization.

Two philosophies of community detection

1. Descriptive / optimization: “find groups that score well.” - Pick a quality function (modularity, cut ratio, conductance) and optimize it. - Fast and intuitive, but the objective defines what a community is, and can suffer from resolution limits and overfitting to noise.

2. Generative / inferential: “assume the data came from a model with hidden groups, then fit it.” - Write down a probability model that generates networks with communities, - then invert it to recover the groups.

Stochastic Block Models (SBMs) are the canonical generative approach.

Why bother with a generative model?

  • Principled: communities are parameters to estimate, not arxtifacts of a scoring rule.
  • Uncertainty & model selection: how many communities?
  • General structure: not just assortative “clumps”: also bipartite, core–periphery, hierarchical patterns.
  • A ground-truth generator: SBMs are the standard benchmark for testing any detection algorithm.

Generative models serve as artificial bench marks

Partion models also serve as evaluation benchmarks

Validation metric-1: Fraction of correctly classified nodes

Validation metric-2: Normalized mutual information

LFR Benchmark

The LFR benchmark is a widely-used artificial test network that realistically imitates properties of real-world networks, including heterogeneous node degrees and community sizes, to evaluate community detection algorithms.

Real world benchmarks: E.g. Zachary’s Karate Club

Stochastic Block Models

The core idea of a block model

Every node belongs to a hidden block (group). The probability that two nodes connect depends only on their blocks: not on their individual identities.

Nodes in the same block are stochastically equivalent: swap two of them and the statistics of the graph are unchanged.

Analogy. In a university, whether two people connect depends mostly on their role: student, faculty, staff: and on how those roles tend to interact, not on the specific individuals.

General idea:

nodes are divided into various groups where the probability that two nodes are connected is dependent on group memberships

  • A network with \(N\) nodes is partitioned into \(q\) groups.
  • Each node \(i\) belongs to a group \(g_i\).
  • The connection probability between nodes \(i\) and \(j\) depends only on their group memberships: \(P(i \leftrightarrow j) = p_{g_i g_j}\).
  • All node pairs from groups \(g_1\) and \(g_2\) share the same connection probability \(p_{g_1 g_2}\).
  • These probabilities form a \(q \times q\) stochastic block matrix.
  • For undirected graphs, the matrix is symmetric; for directed graphs, it may be asymmetric.
  • Diagonal entries \(p_{g g}\) represent within-group connection probabilities.
  • Off-diagonal entries represent between-group connection probabilities.

Limitation: need to specify the number of groups beforehand

Building an SBM in NetworkX

nx.stochastic_block_model(sizes, p, seed=...)
  • sizes: list of block sizes; sets \(n\) and the partition. e.g. [30, 25, 20].
  • p: a \(k\times k\) list-of-lists; p[r][s] is the edge probability between blocks \(r\) and \(s\) (symmetric for an undirected graph). This is the matrix \(B\).

NetworkX tags every node with its block id in the "block" attribute.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

plt.rcParams["figure.dpi"] = 110  # crisp inline figures
SEED = 42                         # reproducibility everywhere

# --- An assortative SBM with three communities ---------------------------
sizes = [30, 25, 20]            # 3 blocks -> n = 75 nodes

# Block matrix B: large diagonal (dense within), small off-diagonal (sparse between).
# Must be symmetric because the graph is undirected.
p = [[0.25, 0.02, 0.02],
     [0.02, 0.30, 0.03],
     [0.02, 0.03, 0.25]]

G = nx.stochastic_block_model(sizes, p, seed=SEED)

# Each node carries its ground-truth block id under the 'block' attribute.
blocks = [G.nodes[v]["block"] for v in G.nodes()]
print(f"{G.number_of_nodes()} nodes, {G.number_of_edges()} edges, {len(sizes)} blocks")
75 nodes, 287 edges, 3 blocks

Interpreting the visualization

The dense squares on the diagonal of the adjacency matrix are the communities.

But this clean block structure only appears because the nodes happen to be ordered by block. Real data arrives in arbitrary order: the whole job of community detection is to find the permutation that reveals these blocks.

# --- Two complementary views: the network, and its adjacency matrix -------
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(11, 4.3))

pos = nx.spring_layout(G, seed=SEED)               # force layout separates dense groups
nx.draw_networkx(G, pos, node_color=blocks, cmap=plt.cm.Set1,
                 node_size=70, with_labels=False,
                 edge_color="lightgray", ax=ax1)
ax1.set_title("SBM network (color = true block)"); ax1.axis("off")

# Nodes are stored in block order, so the adjacency matrix shows dense
# diagonal blocks -- the visual signature of assortative community structure.
A = nx.to_numpy_array(G)
ax2.imshow(A, cmap="Greys", interpolation="nearest")
ax2.set_title("Adjacency matrix (ordered by block)")
ax2.set_xlabel("node"); ax2.set_ylabel("node")

plt.tight_layout(); plt.show()

SBM: Meaning of the parameters

Planted Partition Model

The Planted Partition Model (PPM)

  • The simplest, most-studied SBM: also called the symmetric SBM.

  • All communities are equal-sized and interchangeable, and \(B\) has just two distinct values:

    • Simplified probability matrix: \(P_{in}\) for intra-block, \(P_{out}\) for inter-block.

\[B_{rs} = \begin{cases} p_{\text{in}} & r = s \quad(\text{within a community})\\[2pt] p_{\text{out}} & r \neq s \quad(\text{between communities}) \end{cases}\]

Two knobs only: \(p_{\text{in}}\) and \(p_{\text{out}}\).

  • \(p_{\text{in}} > p_{\text{out}}\) → assortative (ordinary communities).
  • \(p_{\text{in}} = p_{\text{out}}\) → structure disappears; the graph is just Erdős–Rényi.

This is the canonical benchmark for evaluating community-detection algorithms.

Example: Common Community Detection Benchmark

Building a PPM in NetworkX

nx.planted_partition_graph(l, k, p_in, p_out, seed=...)
  • l: number of communities.
  • k: nodes per community (equal sizes) → total \(n = l \cdot k\).
  • p_in: within-community edge probability.
  • p_out: between-community edge probability.

Note that \(p_{in}\) and \(p_{out}\) don’t need to sum to 1:

Need unequal community sizes? Use the sibling nx.random_partition_graph(sizes, p_in, p_out, seed=...), where sizes is a list like the SBM’s.

# --- How structure fades as p_out approaches p_in ------------------------
def ppm_adjacency(l, k, p_in, p_out, seed=1):
    "Planted-partition graph -> adjacency matrix (nodes ordered by community)."
    G = nx.planted_partition_graph(l, k, p_in, p_out, seed=seed)
    return nx.to_numpy_array(G)

l, k = 4, 25                    # 4 communities x 25 nodes = 100 nodes
p_in = 0.6

fig, axes = plt.subplots(1, 3, figsize=(12, 4))
settings = [(0.005, "Strong:  p_out << p_in"),
            (0.08, "Weaker"),
            (0.18, "Barely any structure")]

for ax, (p_out, label) in zip(axes, settings):
    # Show adjacency matrix
    adj = ppm_adjacency(l, k, p_in, p_out)
    ax.imshow(adj, cmap="Greys")
    ax.set_title(f"{label}\n(p_in={p_in}, p_out={p_out})")
    ax.axis("off")
    
    # Visualize the generated graph in a small inset
    from mpl_toolkits.axes_grid1.inset_locator import inset_axes
    G = nx.planted_partition_graph(l, k, p_in, p_out, seed=1)
    ax_inset = inset_axes(ax, width="35%", height="35%", loc='lower right', borderpad=1)
    nx.draw_networkx(G, ax=ax_inset, node_size=8, pos=nx.spring_layout(G, seed=1), 
                     with_labels=False, edge_color="#cccccc", node_color="#4477AA")
    ax_inset.set_xticks([]); ax_inset.set_yticks([])
    ax_inset.set_title("Graph", fontsize=8, pad=2)


plt.tight_layout(); plt.show()
/var/folders/lc/n91cn5z96ws6f52d25t2rpbh0000gn/T/ipykernel_57595/3035322147.py:32: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
  plt.tight_layout(); plt.show()

Limiting case:

As \(p_{\text{out}} \to p_{\text{in}}\) the diagonal blocks wash out and the graph becomes indistinguishable from pure noise (Erdős–Rényi).

This raises a sharp question: is there a point past which the communities are provably impossible to recover: no matter how clever the algorithm?

Inference with Partition Models

Recall: MLE with a Gaussian

The setup. We have data \(x_1,\dots,x_n\) and assume it came from a normal distribution: but we don’t know its mean \(\mu\) or variance \(\sigma^2\). Goal: recover the parameters that best explain the data.

Step 1: Write the likelihood. Each point has density \(f(x_i)=\tfrac{1}{\sqrt{2\pi\sigma^2}}\,e^{-(x_i-\mu)^2/2\sigma^2}\). Assuming independence, multiply:

\[L(\mu,\sigma^2) = \prod_{i=1}^{n} \frac{1}{\sqrt{2\pi\sigma^2}}\, e^{-\frac{(x_i-\mu)^2}{2\sigma^2}}\]

Step 2: Take the log (turns the nasty product into a friendly sum):

\[\ell(\mu,\sigma^2) = -\frac{n}{2}\log(2\pi\sigma^2) \;-\; \frac{1}{2\sigma^2}\sum_{i=1}^{n}(x_i-\mu)^2\]

Step 3: Maximize (set derivatives to zero, solve):

\[\hat\mu = \frac{1}{n}\sum_i x_i \quad(\text{the sample mean}), \qquad \hat\sigma^2 = \frac{1}{n}\sum_i (x_i-\hat\mu)^2 \quad(\text{the sample variance})\]

The takeaway: “which parameters make the observed data most likely?” The answer is just the obvious summary statistics: and this write it → log it → maximize it recipe is exactly what we do for the PPM. The only twist there: one of the parameters (the community labels) is discrete, so that piece needs a search instead of a clean derivative.

We can do a similar thing for the PPM too, but the math is more complicated.

Inference with the PPM: motivation

So far we’ve run the PPM forward: pick \(p_\text{in}, p_\text{out}\), hidden labels \(z\), and generate a network. But with real data we face the reverse problem:

\[\text{we see only } A \;\longrightarrow\; \text{recover the hidden communities } \hat z\]

The network arrives as a scrambled pile of nodes and edges.

Nobody hands us the labels: that’s the whole point.

The key idea: treat the PPM as a hypothesis about how the graph was born, and ask —

“Which assignment of nodes to groups makes the graph we actually see most believable?”

Because the PPM has just two knobs (\(p_\text{in}\) for within-group links, \(p_\text{out}\) for between), this reduces to one intuitive test: find the split that is dense inside and sparse between. That’s a partition where within-group ties look like \(p_\text{in}\) and cross-group ties look like \(p_\text{out}\): with \(p_\text{in} \gg p_\text{out}\).

  • A good split → the adjacency matrix lights up in dense diagonal blocks.
  • A bad split → edges scattered everywhere, no block structure.

Inference is simply searching partitions and scoring how believable each one is: turning “find the communities” into a well-posed estimation problem.

Steps of inference with the PPM

The PPM has only two knobs: \(p_\text{in}\) (within-group) and \(p_\text{out}\) (between-group): so recovering communities boils down to one question: which split packs the most edges inside groups?

Step 1: Propose a partition \(z\). A guess at the \(k\) equal-sized communities.

Step 2: Fill in the two knobs for free. Given the split, their best estimates are just the observed densities:

\[\hat p_\text{in} = \frac{\text{edges inside groups}}{\text{pairs inside groups}}, \qquad \hat p_\text{out} = \frac{\text{edges between groups}}{\text{pairs between groups}}.\]

Step 3: Score it. Reward the split for every within-group edge and every between-group gap. A partition scores high exactly when \(\hat p_\text{in} \gg \hat p_\text{out}\): dense inside, sparse between.

Step 4: Improve. Move a node to another group, re-score, keep moves that raise it. Repeat until no move helps.

Step 5: Sanity check. If \(\hat p_\text{in} \approx \hat p_\text{out}\), the “communities” are just noise: recall the detectability threshold: below it, no amount of searching can recover real groups.

Intuition: the whole search is hunting for the split that makes the diagonal blocks of the adjacency matrix as dense as possible and the off-diagonal blocks as empty as possible.

Methods for Finding the best partition

We can’t just test every partition: the number of ways to split \(n\) nodes into groups explodes (the Bell numbers grow faster than exponentially). So we need smart search:

  • Maximum likelihood: hill-climbing: nudge nodes between blocks, keep the moves that raise the score. Simple, but can get stuck in a local peak.

  • Bayesian / MCMC: don’t hunt for one “best” answer; sample many plausible ones. Bonus: it infers how many communities \(k\) exist on its own, with a built-in penalty against overfitting (Occam’s razor).

  • Belief propagation: nodes gossip their best self-guess to their neighbors and update until everyone agrees. Fast, and it pinpoints the exact threshold where detection becomes impossible.

  • Spectral methods: skip the search: read the groups straight off the top eigenvectors of the matrix (fast linear algebra: ties back to spectral lectures).

Forward model = how the graph was born.  Inference = rewinding the tape to recover the hidden groups.

Degree Corrected Stochastic Block Model (DCSBM)

Motivation for DCSBM

  • Limitation of Standard SBM: The standard Stochastic Block Model (SBM) performs poorly on real networks because it assumes uniform degree distribution, ignoring degree heterogeneity.

  • Motivation for DCSBM: The Degree-Corrected Stochastic Block Model (DCSBM) addresses this by incorporating actual node degrees, enabling more accurate modeling of networks with variable connectivity.

  • degree (“high-degree” vs “low-degree”) instead of by genuine community.

  • Fix. Give each node a propensity \(\theta_i\) so the expected edge rate becomes

\[\lambda_{ij} \;\propto\; \theta_i\,\theta_j\,\omega_{z_i z_j}.\]

  • Now degree heterogeneity is absorbed by the \(\theta_i\), freeing the blocks \(\omega_{rs}\) to capture the actual community structure.

Definition of Terms

  • Definitions:

    • \(G\): The observed network (graph) consisting of nodes and edges.
    • \(g\): A proposed partitioning of the nodes in \(G\) into \(q\) groups (or blocks).
  • DCSBM Log-Likelihood Function:

    \[ \mathcal{L}(G \mid g) = \sum_{r,s=1}^q L_{rs} \log\left(\frac{L_{rs}}{k_r k_s}\right) \]

    • \(L_{rs}\): Number of edges between group \(r\) and group \(s\)
    • \(k_r\), \(k_s\): Sum of degrees of nodes in group \(r\) and \(s\), respectively
    • Measures how likely it is that the observed network \(G\) was generated from partition \(g\) under the DCSBM.

Greedy Likelihood Maximization Algorithm

  • Greedy Likelihood Maximization Algorithm:

    • Initialization: Start with a random division of nodes into \(q\) groups (i.e., a random \(g\)).

    • Step 1 – Node Reassignment:

      • For each node, try moving it to a different group to increase (or least decrease) the log-likelihood.
      • Each node is moved only once per iteration.
    • Step 2 – Best Partition Selection:

      • Among all partitions visited in Step 1, select the one with the highest likelihood.
  • Stopping Criterion:

    • The algorithm halts when likelihood converges (i.e., no change between successive iterations).

Inference with the DC-SBM:

score every partition, keep the best: but the scoring now accounts for hubs.

Step 0: Precompute (once). Node degrees \(k_i\), and for any grouping, the edge counts \(m_{rs}\) and group degree-sums \(\kappa_r = \sum_{i\in r} k_i\).

Step 1: Propose a partition \(z\). A guess at who’s in which block.

Step 2: Fill in the rest of the recipe for free. The nuisance parameters have closed-form MLEs: no searching needed:

\[\hat\theta_i = \frac{k_i}{\kappa_{z_i}} \quad(\text{node's share of its group}), \qquad \hat\omega_{rs} = m_{rs}.\]

Step 3: Score the partition. Plug those back in; everything collapses to a function of \(z\) alone:

\[\mathcal{L}(z) = \sum_{rs} m_{rs}\,\log\frac{m_{rs}}{\kappa_r\,\kappa_s}.\]

Step 4: Improve. Move a node to a neighboring block, recompute \(\mathcal L\), keep moves that raise it (greedy / agglomerative). Repeat to convergence.

Step 5: Escape local peaks & pick \(k\). Restart from many seeds; or go Bayesian (MCMC over \(z\)) to sample partitions and infer the number of blocks automatically.

Summary of models

  • SBM = a generative model: edge probability depends only on block membership
    • The pattern of \(B\) sets the structure: assortative, disassortative, or core–periphery: not just clumps.
  • PPM = symmetric SBM with two knobs, \(p_{\text{in}}\) and \(p_{\text{out}}\); the field’s standard benchmark.
  • Detectability threshold: weak communities are provably unrecoverable: a real phase transition.
  • Detection = inference: invert the generative process via likelihood, Bayes/MCMC, belief propagation, or spectral methods.
  • DC-SBM makes the model usable on real, heavy-tailed networks.

Extra: PPM Fitting example

Description of what this code does:

  • Setup: Imports NumPy, NetworkX, Matplotlib; seeds a random generator for reproducibility.

  • Define the PPM likelihood (ppm_log_likelihood): Given a community assignment z and adjacency matrix A:

    • Flags every node pair as same-community or different-community (upper triangle only, so each pair counts once).
    • Counts within-community edges m_in and cross-community edges m_out, plus how many pairs of each type exist.
    • Sets the fitted probabilities to the observed densities: p_in = m_in / #same-pairs, p_out = m_out / #diff-pairs.
    • Returns the profile log-likelihood (sum of two Bernoulli-block terms) along with p_in, p_out.
  • Define the inference objective (score): Returns the log-likelihood only if the split is assortative (p_in > p_out); otherwise −inf. This enforces the “planted” (assortative) assumption and blocks the degenerate degree-based split.

  • Inference by greedy hill-climbing (infer): For each of 40 random restarts:

    • Start from a random 2-way labeling.
    • Sweep over nodes, flipping any node whose reassignment raises the score; repeat sweeps until no flip helps.
    • Track the best-scoring labeling across all restarts.
  • Run on Karate Club:

    • Loads nx.karate_club_graph(), builds A, and reads ground-truth factions from the 'club' node attribute.
    • Runs infer to get the predicted labels.
    • Aligns the arbitrary {0,1} labels to the ground truth (flips if agreement < 50%).
    • Computes accuracy, fitted p_in/p_out, and the misclassified nodes, then prints them.
  • Visualization A: graphs: Draws two side-by-side spring layouts (shared positions): ground-truth factions vs. inferred communities, coloring nodes by community and ringing misclassified nodes in red.

  • Visualization B: block structure: Shows the adjacency matrix in original order vs. reordered by inferred community, with red lines marking the community boundary to reveal the dense diagonal blocks (p_in) against the sparse off-diagonal block (p_out).

  • Save: Writes both figures to images/ and prints a confirmation.

One note: the file references an images/ directory for saving (and has a trailing # show the images comment with nothing after it): make sure that folder exists before running, or the savefig calls will error.

Source: Claude

"""
Community detection by INFERENCE with the Planted Partition Model (PPM)
======================================================================

The Planted Partition Model is the simplest Stochastic Block Model:

    * every node belongs to one of k communities (here k = 2)
    * two nodes in the SAME community are linked with probability p_in
    * two nodes in DIFFERENT communities are linked with probability p_out
    * "planting" communities means the structure is ASSORTATIVE: p_in > p_out

Detecting communities "by inference" = find the node->community assignment z
that makes the observed graph MOST PROBABLE under this model (maximum
likelihood). No modularity, no black box -- just the generative model.
"""

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

rng = np.random.default_rng(42)

# ---------------------------------------------------------------------------
# 1. Likelihood of the Planted Partition Model
# ---------------------------------------------------------------------------
# For an assignment z, look at every PAIR of nodes:
#     same-community pairs -> m_in  of them have an edge
#     diff-community pairs -> m_out of them have an edge
# The best-fit probabilities are simply the observed edge densities:
#     p_in  = m_in  / (#same-community pairs)
#     p_out = m_out / (#diff-community pairs)
# Substituting them back gives the "profile" log-likelihood of z.

def ppm_log_likelihood(A, z):
    n = len(z)
    same = z[:, None] == z[None, :]        # n x n : are i and j in same community?
    iu = np.triu_indices(n, k=1)           # each unordered pair once
    same_pair = same[iu]
    edge = A[iu].astype(bool)

    n_in,  n_out  = same_pair.sum(), (~same_pair).sum()
    m_in  = (edge &  same_pair).sum()
    m_out = (edge & ~same_pair).sum()

    p_in  = m_in  / n_in  if n_in  else 0.0
    p_out = m_out / n_out if n_out else 0.0

    def block_ll(m, npairs, p):            # log-likelihood contributed by a block
        if npairs == 0:
            return 0.0
        ll = 0.0
        if p > 0: ll += m * np.log(p)
        if p < 1: ll += (npairs - m) * np.log(1 - p)
        return ll

    ll = block_ll(m_in, n_in, p_in) + block_ll(m_out, n_out, p_out)
    return ll, p_in, p_out


def score(A, z):
    """Objective for inference: PPM log-likelihood, but only for ASSORTATIVE
    partitions (p_in > p_out). This is what makes it a *planted* partition
    model -- without it, a plain SBM splits Karate Club by degree, not faction."""
    ll, p_in, p_out = ppm_log_likelihood(A, z)
    return ll if p_in > p_out else -np.inf


# ---------------------------------------------------------------------------
# 2. Inference: greedy hill-climbing to maximize the likelihood
# ---------------------------------------------------------------------------
# Start from a random labelling; repeatedly flip whichever single node most
# improves the score; stop when nothing improves. Random restarts avoid poor
# local optima. (34 nodes is tiny, so brute simplicity is fine.)

def infer(A, restarts=40):
    n = A.shape[0]
    best_z, best = None, -np.inf
    for _ in range(restarts):
        z = rng.integers(0, 2, size=n)
        improved = True
        while improved:
            improved = False
            for i in range(n):
                cur = z[i]
                keep_ll = score(A, z)
                z[i] = 1 - cur
                flip_ll = score(A, z)
                if flip_ll > keep_ll:            # flipping helps -> keep it
                    improved = True
                else:
                    z[i] = cur                   # otherwise revert
        s = score(A, z)
        if s > best:
            best, best_z = s, z.copy()
    return best_z, best


# ---------------------------------------------------------------------------
# 3. Run on Zachary's Karate Club
# ---------------------------------------------------------------------------
G = nx.karate_club_graph()
nodes = list(G.nodes())
A = nx.to_numpy_array(G, nodelist=nodes)

# ground-truth factions: networkx stores them in the 'club' node attribute
truth = np.array([0 if G.nodes[v]["club"] == "Mr. Hi" else 1 for v in nodes])

z, s = infer(A, restarts=40)

# community labels {0,1} are arbitrary -> align them to ground truth for scoring
if (z == truth).mean() < 0.5:
    z = 1 - z

acc = (z == truth).mean()
_, p_in, p_out = ppm_log_likelihood(A, z)
wrong = [nodes[i] for i in range(len(nodes)) if z[i] != truth[i]]

print(f"log-likelihood   : {s:.2f}")
print(f"fitted p_in      : {p_in:.3f}")
print(f"fitted p_out     : {p_out:.3f}   (p_in is {p_in/p_out:.0f}x p_out)")
print(f"accuracy vs truth: {acc*100:.1f}%  ({(z==truth).sum()}/{len(nodes)})")
print(f"misclassified    : {wrong}")


# ---------------------------------------------------------------------------
# 4. Visualization A -- graphs: ground truth vs inferred
# ---------------------------------------------------------------------------
pos = nx.spring_layout(G, seed=1)          # one fixed layout, used in both panels
palette = np.array(["#4C72B0", "#DD8452"]) # blue / orange per community

fig, ax = plt.subplots(1, 2, figsize=(14, 6))
for a, (labels, title) in zip(
        ax, [(truth, "Ground-truth factions"),
             (z,     f"Inferred communities  (accuracy {acc*100:.0f}%)")]):
    nx.draw_networkx_edges(G, pos, ax=a, alpha=0.25)
    nx.draw_networkx_nodes(G, pos, ax=a, node_color=palette[labels],
                           node_size=380, edgecolors="white", linewidths=1.5)
    nx.draw_networkx_labels(G, pos, ax=a, font_size=8, font_color="white")
    a.set_title(title, fontsize=13); a.axis("off")

if wrong:                                   # ring the misclassified node(s)
    nx.draw_networkx_nodes(G, pos, nodelist=wrong, ax=ax[1], node_color="none",
                           node_size=620, edgecolors="red", linewidths=2.5)
    ax[1].scatter([], [], s=80, facecolors="none", edgecolors="red",
                  linewidths=2.5, label="misclassified")
    ax[1].legend(loc="lower left", fontsize=10)

fig.suptitle("Planted Partition Model: inferred split of Zachary's Karate Club",
             fontsize=15, y=1.02)
fig.tight_layout()
fig.savefig("images/ppm_graphs.png", dpi=130, bbox_inches="tight")
plt.close(fig)


# ---------------------------------------------------------------------------
# 5. Visualization B -- the block structure in the adjacency matrix
# ---------------------------------------------------------------------------
# Reordering rows/cols by inferred community reveals the "planted partition":
# two DENSE diagonal blocks (p_in) with a SPARSE off-diagonal block (p_out).

order = np.argsort(z, kind="stable")
split = int(np.sum(z == 0))                # boundary between the two communities

fig, ax = plt.subplots(1, 2, figsize=(13, 6))
ax[0].imshow(A, cmap="Greys", interpolation="nearest")
ax[0].set_title("Adjacency matrix\n(original node order)", fontsize=12)

ax[1].imshow(A[np.ix_(order, order)], cmap="Greys", interpolation="nearest")
ax[1].axhline(split - 0.5, color="red", lw=1.5)
ax[1].axvline(split - 0.5, color="red", lw=1.5)
ax[1].set_title(f"Reordered by inferred community\n"
                f"dense blocks (p_in={p_in:.2f}) vs sparse off-block "
                f"(p_out={p_out:.2f})", fontsize=12)
for a in ax:
    a.set_xlabel("node"); a.set_ylabel("node")

fig.suptitle("Why inference works: communities are blocks of edge density",
             fontsize=15, y=1.02)
fig.tight_layout()
fig.savefig("images/ppm_blocks.png", dpi=130, bbox_inches="tight")
plt.close(fig)

print("\nSaved images/ppm_graphs.png and images/ppm_blocks.png")


# show the images
log-likelihood   : -196.42
fitted p_in      : 0.250
fitted p_out     : 0.035   (p_in is 7x p_out)
accuracy vs truth: 94.1%  (32/34)
misclassified    : [8, 9]

Saved images/ppm_graphs.png and images/ppm_blocks.png