Entropy of stochastic blockmodel ensembles

I. INTRODUCTION

• The standard model gives same-block vertices equal expected degrees, while degree correction accommodates observed degree variation within blocks.The paper derives entropy expressions for traditional and degree-corrected ensembles, including simple and multigraph, directed and undirected, and soft and hard degree constraints.Source: §I · pp. 1–2
• Earlier blockmodel log-likelihoods may be non-closed or omit terms, preventing direct recovery of the ensemble entropy.With equal probability for each graph, the log-likelihood is the negative entropy and can be used to infer a likely block structure.Source: §I · p. 1

II. TRADITIONAL AND DEGREE-CORRECTED BLOCKMODELS

• The traditional microcanonical model fixes block sizes and edge counts; degree-corrected variants additionally impose vertex degrees as averages or as an exact sequence.When nonzero block-edge counts are sufficiently large, the microcanonical and canonical formulations become equivalent because fluctuations around the mean can be neglected.Source: §II · p. 2

A. Standard stochastic blockmodel

• For simple graphs, sparse-limit entropy approximations can omit important terms when block pairs are locally dense, even if the whole graph is sparse.The paper says to use the fuller expressions instead in such cases.Source: A. Standard stochastic blockmodel · p. 3

1. Directed graphs

• Directed blockmodels allow an asymmetric block-edge matrix and distinguish edges leaving a block from those entering it.The number of edge choices is counted as in the undirected case, without a separate diagonal treatment.Source: §1 · p. 3
• The directed entropy is identical to the corresponding undirected expression except for a factor of 1/2.The paper also gives the corresponding alternative expression and sparse approximation with the same factor.Source: §1 · p. 3
• For directed graphs, the diagonal edge count represents internal edges, rather than twice that number as in the undirected convention.This convention is specified for the directed entropy expression.Source: §1 · p. 3

B. Degree-corrected ensembles with “soft” constraints

• Expected degrees label vertices within each block, with each degree imposed as an ensemble average rather than a fixed value on every graph.This soft constraint is implemented by splitting each block into degree-labeled classes.Source: B. Degree-corrected ensembles with… · pp. 3–4
• The full matrix of edge counts between degree-labeled classes accommodates arbitrary expected-degree sequences and degree correlations, generalizing the ensemble in.A less-constrained version fixes only total edges between blocks, irrespective of degree labels.Source: B. Degree-corrected ensembles with… · p. 4
• Maximizing entropy subject to block-pair edge totals yields a nonlinear system with no general closed-form solution; its sparse-limit approximation neglects intrinsic correlations between block pairs.The sparse or classical limit assumes exp(λ_rs + μ_rκ + μ_sκ′) ≫ 1.Source: B. Degree-corrected ensembles with… · p. 4
• Higher moments of the expected-degree sequence can contribute substantially to entropy, regardless of the blockwise mean degree.Their importance depends on the degree sequence; broad distributions can make these contributions non-negligible even for sparse graphs.Source: B. Degree-corrected ensembles with… · p. 4
• In the stated limit, block partition and expected-degree sequence contribute independent entropy terms, and the block term corresponds to mutual information between memberships at edge ends.The expected edge-end distribution is expressed using the total half-edges leaving each block.Source: B. Degree-corrected ensembles with… · p. 4
• The sparse approximation requires valid degree-class edge counts and can fail with strong intrinsic inter-block disassortative degree correlations.Even when the approximation is valid, entropy still reflects the cost of connecting to a block with a broad degree distribution.Source: B. Degree-corrected ensembles with… · p. 5

1. Directed graphs

• Directed degree-corrected ensembles separate vertices by block and expected in- and out-degree, using labels (r, κ−, κ+).The labels are incorporated into the degree-corrected entropy expression.Source: §1 · p. 5
• Taking the classical limit for directed degree-corrected ensembles yields an entropy expression by inserting the directed edge-count approximation into the degree-corrected entropy.The expression is omitted in the passage.Source: §1 · p. 5
• The directed expression inherits the undirected case’s caveats about the suitability of the approximation and the resulting entropy formula.Source: §1 · p. 5

IV. MULTIGRAPH ENSEMBLES

• For undirected multigraphs, allowing multiple edges changes the count of edge choices between blocks and leads to a corresponding entropy expression.The edge-choice count uses combinations with repetition.Source: §IV · p. 5
• In the sparse limit, the multigraph entropy matches the simple-graph entropy because the probability of multiple edges vanishes.The expanded expression differs by an alternating sign in its last term before that term is dropped.Source: §IV · p. 5

2. Directed graphs

• For directed multigraphs, graph counts multiply over directed block pairs, since the edge-count matrix is generally asymmetric.The diagonal block term is treated without the undirected-case adjustment.Source: §2 · p. 6
• Directed multigraph entropy is the corresponding undirected expression with a factor of 1/2, including in the stated approximation.For directed graphs, e_rr counts internal edges rather than twice that number.Source: §2 · p. 6

A. Degree-corrected ensembles with “soft” constraints

• Soft degree-corrected ensembles allow arbitrary degree correlations; imposing an uncorrelated constraint yields a nonlinear system without a closed-form solution.In the classical limit, the entropy expression is approximated by the sparse-limit expression, where the simple-graph and multigraph ensembles become equivalent.Source: A. Degree-corrected ensembles with… · p. 6

1. Directed graphs

• The directed multigraph analysis uses block labels that include in- and out-degree, and its classical-limit entropy expression has caveats like the simple-graph case.The expression is similar to the simple-graph ensemble except for an alternating sign in the last term.Source: §1 · p. 6

V. DEGREE-CORRECTED ENSEMBLES WITH “HARD” CONSTRAINTS

• The hard-constraint counting approach starts from configurations obeying a degree sequence and assumes sufficiently sparse limits, neglecting interactions between edge placements.The assumption is described as non-rigorous but compatible with more rigorous analyses.Source: §V · p. 7
• For a single block, randomly matching half-edges generates configurations; rejecting multigraphs can yield uniformly generated simple graphs, but multigraphs are not equiprobable.The hard-constraint case has no universally valid asymptotic entropy expression, even for a single block.Source: §V · pp. 6–7

A. Configurations

• The configuration count corrects for equivalent permutations of out-neighbours, but additional corrections are needed to count simple graphs or multigraphs accurately.For multigraphs, repeated edges reduce the number of equivalent pairings by a factor of m! for m parallel edges.Source: A. Configurations · p. 7
• In the sparse limit with sufficiently large degrees, simple- and multigraph ensembles with soft constraints and the hard-constraint configuration ensemble become equivalent.The comparison uses the condition that individual degrees equal their expected values.Source: A. Configurations · pp. 7–8

1. Directed configurations

• Directed configuration counting accounts for the asymmetric block-edge matrix and corrects for permutations of both in- and out-degrees.Source: §1 · p. 8

• The calculation estimates the probability that configurations yield simple graphs by treating repeated-edge and self-loop probabilities as independent.It applies Stirling’s approximation and assumes vertex degrees are much smaller than the number of half-edges leaving each block.Source: B. Simple graphs · p. 8
• For one block, the hard-constraint expression matches a known degree-sequence entropy result in the limit k_i ≪ N.The expression is also compatible with a later result, apart from a trivial constant.Source: B. Simple graphs · p. 8
• Hard- and soft-constraint ensembles are equivalent only in sufficiently sparse cases when higher-order terms can be neglected and degrees are large enough or distributions broad enough.The self-loop term must also be negligible.Source: B. Simple graphs · pp. 8–9

1. Directed graphs

• For one block, the directed simple-graph expression recovers a known result for imposed in- and out-degree sequences when k−/+ ≪ N.Source: §1 · p. 9

C. Multigraphs

• Multigraph configurations require a correction because graphs with m parallel edges have fewer generating configurations by a factor of m!.The resulting entropy resembles the simple-graph expression except for the signs of its last two terms.Source: C. Multigraphs · p. 9
• For one block, the multigraph expression matches a known result in the limit k_i ≪ N; another expression omits the final term because it counts parallel self-edges differently.Source: C. Multigraphs · p. 9

1. Directed multigraphs

• For directed multigraphs, the self-loop correction is treated like other parallel edges, so there is no separate self-loop term.With B = 1, the expression recovers the known count for multigraphs with imposed in/out-degree sequence when k−/+ ≪ N.Source: §1 · p. 9

VI. BLOCKMODEL DETECTION

• Blockmodel inference maximizes the likelihood over vertex partitions to identify latent equivalence classes, unlike community detection’s focus on dense within-group connections.The dense-within-group case corresponds to blockmodels whose diagonal elements of ers are largest.Source: §VI · pp. 9–10
• The objective’s L parameter controls how many terms are included: L = 0 recovers, while L > 0 includes higher-order corrections that may matter for large within-block degree moments.The second term can be neglected entirely in the L = 0 case.Source: §VI · p. 10
• A greedy inference procedure repeatedly moves vertices to maximize L, but can get trapped in local maxima and require restarts from other random partitions.Updating one vertex has complexity O(B(B(L + 1) + ⟨k⟩)), independent of system size.Source: §VI · p. 10
• The entropy-derived log-likelihood generalizes, whose expression is recovered when graphs are sparse and degree distributions are not broad.The same entropy methods extend to multigraph and directed ensembles.Source: §VI · p. 10
• In a deliberately simple broad-degree example, failing to account for entropic effects produces spurious block partitions relative to the higher-order objective.The example is chosen to make block identification easy, not to test the approach in difficult cases.Source: §VI · p. 10

A. Intrinsic degree correlations

• A typical generated sample has N = 103 vertices, B = 4, strong block structure with w = 0.99, and a broad degree distribution with γ = 1.1 and [kmin, kmax] = [30, 200], causing intrinsic dissortative degree correlations.Source: A. Intrinsic degree correlations · p. 11
• Because log-likelihood increases monotonically with B, choosing the partition with the largest likelihood can fail to identify the appropriate block count.As B grows, the number of suitable models grows while the data remain fixed.Source: A. Intrinsic degree correlations · p. 11
• An estimate of the expected true log-likelihood helps distinguish gains from discovering block structure from gains caused by limited data.The passage denotes this expected value by L* as sample size tends to infinity.Source: A. Intrinsic degree correlations · p. 11
• B = 4 yields the correct partition for every tested L, while B = 8 with L = 0 separates vertices by degree, an entropic artifact.For L = 2, the inferred partition is correct; larger values give the same result with negligible differences.Source: A. Intrinsic degree correlations · p. 11, Figure 4 · p. 12
• For L ≥ 2, the inferred partition's correlation with degree essentially vanishes, whereas lower L values remain significantly correlated.The right panel compares average normalized mutual information across B and L values.Source: A. Intrinsic degree correlations · p. 12, Figure 3 · p. 12
• The log-likelihood approximation neglects some entropic effects and may diverge for sufficiently large degrees and L.The exact entropy expression can address extreme cases, but requires more parameters and may overfit.Source: A. Intrinsic degree correlations · p. 12

B. Extrinsic degree correlations

• Ignoring degree correlations recovers the correct B = 4 partition, but larger B creates degree-based sub-blocks and rising log-likelihood; full resolution may require B ∼ 4K.For the example, K = 168, making the full parameter matrix larger than the number of network edges.Source: B. Extrinsic degree correlations · p. 13
• An auxiliary partition bins vertices by degree and is held fixed while inferring B blocks, allowing degree correlations to be inferred separately from degree-independent block structure.Choose few bins with low within-bin degree variance and avoid bins with very few vertices; then swap labels within each degree bin to make the inferred block labels meaningful.Source: B. Extrinsic degree correlations · p. 14
• With the auxiliary partition, log-likelihood growth points more convincingly to B = 4, and the degree-partition NMI differs significantly from inference without it.For D = 8, a residual degree association remains.Source: Figure 7 · p. 13, B. Extrinsic degree correlations · p. 14

VII. CONCLUSION

• The paper derives analytical entropies for traditional and degree-corrected ensembles, including directed and undirected graphs and soft and hard degree constraints.Setting the number of blocks to one recovers known entropies for random graphs with arbitrary degree sequences.Source: §VII · p. 14
• Entropy-derived likelihoods support block inference with intrinsic degree correlations and can be adapted to arbitrary extrinsic degree correlations, generalizing the approach in.The approach is described as suitable beyond the sparse-graph, non-broad-degree-sequence setting in which is expected to work well.Source: §VII · p. 14
• Blockmodel entropy can help assess the relevance of empirical-network topological features and the statistical significance of modular partitions.Source: §VII · p. 14
• For network systems with an energy function depending on block structure, blockmodel entropy can be used to obtain equilibrium properties.A cited gene-regulatory model uses robustness as an energy function and reports a core-periphery transition at higher selective pressure.Source: §VII · p. 14