Tutorial: computing 2D structural entropy

Worked, byte-checked examples — some with integer answers. ← benchmark · gallery · repo

The formula

For a graph with degrees d_v, total degree 2m = Σ_v d_v, and a partition into communities j with volume V_j = Σ_v∈j d_v and cut g_j (edge weight leaving j), the 2D structural entropy is

H² = − Σ_j (g_j/2m) log₂(V_j/2m) (module / cut term) − Σ_v (d_v/2m) log₂(d_v/V_c(v)) (within term)

The 1D entropy H¹ = −Σ_v(d_v/2m)log₂(d_v/2m) is the same quantity with no partition (every node its own "module" sharing the whole graph as parent); it is an upper bound that H² improves on whenever the graph has community structure. Below, the module and within columns are the per-community contributions to each sum; the displayed totals are reproduced exactly by selib.

Single edge

n=2, m=1, 2m=2; colour = community

Two nodes, one edge. Whatever the partition, both H¹ and H² equal exactly 1 bit: one bit to locate a random walker on one of two symmetric endpoints.

j	members	V_j	g_j	module	within
0	{0, 1}	2	0	0.0000	1.0000
totals				0.0000	1.0000

H¹ = 1.0000 · H² = 0.0000 + 1.0000 = 1.0000 = 1 bit exactly

selib.structural_entropy(G, [0, 0])  # -> 1.0000

Four disjoint edges

n=8, m=4, 2m=8; colour = community

Eight nodes in four independent pairs. The partition-free 1D entropy is log₂8 = 3 bits; describing each pair as its own community drives it down to exactly 1 bit — the cut term vanishes (no edges leave a pair, g=0) and only the within-pair bit remains.

j	members	V_j	g_j	within
0	{0, 1}	2	0	0.2500
1	{2, 3}	2	0	0.2500
2	{4, 5}	2	0	0.2500
3	{6, 7}	2	0	0.2500
totals				1.0000

H¹ = 3.0000 · H² = 0.0000 + 1.0000 = 1.0000 = 1 bit exactly

selib.structural_entropy(G, [0, 0, 1, 1, 2, 2, 3, 3])  # -> 1.0000

4-cycle, split in two

n=4, m=4, 2m=8; colour = community

A 4-cycle has 1D entropy log₂4 = 2 bits. Cutting it into two adjacent pairs costs a half-bit of cut entropy but saves a full bit inside the communities → H² = 1.5 bits.

j	members	V_j	g_j	module	within
0	{0, 1}	4	2	0.2500	0.5000
1	{2, 3}	4	2	0.2500	0.5000
totals				0.5000	1.0000

H¹ = 2.0000 · H² = 0.5000 + 1.0000 = 1.5000

selib.structural_entropy(G, [0, 0, 1, 1])  # -> 1.5000

Two triangles + bridge

n=6, m=7, 2m=14; colour = community

Two triangles joined by a single bridge edge. The SE-optimal partition is the two triangles; the lone bridge is the only cut, so the module term is tiny and H² ≈ 1.70 bits — the textbook case where SE recovers the obvious two communities.

j	members	V_j	g_j	module	within
0	{0, 1, 2}	7	1	0.0714	0.7783
1	{3, 4, 5}	7	1	0.0714	0.7783
totals				0.1429	1.5567

H¹ = 2.5567 · H² = 0.1429 + 1.5567 = 1.6995

selib.structural_entropy(G, [0, 0, 0, 1, 1, 1])  # -> 1.6995

Definitions & conventions (what selib actually computes)

Structural entropy is usually motivated by a random walk: on a connected graph the stationary distribution is π_v = d_v/2m, and the formulas above are its expected description length under a partition. But the quantities they use — degrees, community volumes V_j, and cuts g_j — are purely combinatorial, so the entropy is well-defined for any graph, connected or not. selib computes it directly from those quantities. Concretely:

Units: bits (log base 2). These are the raw structural-entropy values of Li & Pan (2016), not normalized by 1D-SE or by log n.
Weights: an edge attribute weight (default 1); the degree d_v is the weighted degree and 2m = Σ_v d_v.
What d_v/2m really is (and why disconnected graphs are fine): the random-walk story (π = d_v/2m is the walk's stationary distribution) needs a connected graph. But the robust reading that survives any graph is: pick a uniformly random edge-endpoint; d_v/2m is the probability it lands on v — a valid distribution (it sums to 1) whether or not the graph is connected. So SE is the expected code length under that distribution, and needs no connectivity. A disconnected graph (like Four disjoint edges above) just has components as top-level modules with cut g_j=0; their volumes still enter the sums, and the encoding tree's root simply sits above the components. Same convention as deDoc, CoDeSEG, and the glass-jax discrete scorer (verified below). One caveat: when all cross-component cuts are 0, the optimal partition is well-defined but the tree above the components is not unique (nothing to compress between them).
Isolated nodes (degree 0) contribute nothing: the d log d terms vanish. Self-loops count twice in the degree (NetworkX convention) and are always internal to their community.
Direction: graphs are treated as undirected (the adjacency is symmetrized); directed SE is out of scope for v0.2.
Higher dimensions: the 2D value is the entropy of a flat (2-level) partition; the full encoding-tree value H^T generalizes it to trees of any height (a 2-level tree's H^T equals H² exactly — checked).

Cross-checked against independent implementations

The 2D-SE numbers here are validated against code that implements the formula independently. Full per-run report: se_crosscheck.json.

glass-jax discrete scorer (an independent implementation of the same definition): over 58 random graphs — connected, disconnected, and weighted — the maximum absolute difference from selib is 1.8e-15 bits, i.e. floating-point machine precision. The definitions are identical.
Encoding-tree H^T: selib's hierarchical structural entropy matches an independent implementation (beat-hcse's tree_entropy, the Angsheng-Li-group formula) to 3.6e-15 bits, scoring the trees built by selib's se_hier and the original BBM and HCSE code (github.com/Hardict/HCSE), over connected, disconnected, weighted and isolated-node graphs. (HCSE/BBM's own code is only defined for connected graphs; selib handles all cases.)
deDoc (original Java, Li 2018): reproduces its partition exactly; the value it prints is a Hi-C‑specific normalized 2D-SE (e.g. Karate 0.625), not raw bits, so it is not directly equal to selib's H² = 4.483 of the same partition — the definition is confirmed via glass-jax above, while the normalization differs.

Every number here is computed by selib.calc and asserted equal to the hand-derived breakdown in tutorial.json — if the arithmetic and the library ever disagreed, the build would fail.