Modularity: Definition and Derivation

Why Compare Within-Community Edges With a Baseline?

A partition can place many graph edges within its proposed communities simply because some vertices have many edges. To assess whether a partition groups vertices more strongly than their degrees alone would suggest, modularity compares observed within-community edge weight with a degree-based reference. In a cell-cell neighborhood graph, this provides a numerical summary of how well a proposed grouping aligns with the graph’s connectivity. It does not, by itself, establish that the groups are biologically distinct.

The key is the comparison, not the raw number of internal edges. A high-degree cell is expected to connect to many other cells even under a null model that does not favor any particular community assignment. Modularity discounts the within-community connectivity that such a degree-based baseline would predict.

Definition for an Undirected Graph

Consider an undirected, loop-free graph with \(n\) vertices. Let \(A_{ij}\) be 1 if vertices \(i\) and \(j\) are connected and 0 otherwise. The adjacency matrix is symmetric, \(A_{ij}=A_{ji}\), and its diagonal entries are zero. The degree of vertex \(i\) is \(k_i=\sum_j A_{ij}\), and the number of edges is \(m=\frac{1}{2}\sum_i k_i\). A partition assigns every vertex to exactly one community. Write \(c_i\) for the community of vertex \(i\), and let \(\delta(c_i,c_j)\) equal 1 when \(c_i=c_j\) and 0 otherwise.

The baseline is motivated by a degree-preserving configuration model: vertices are represented by degree-many stubs, and stubs are paired to form edges. The standard modularity baseline \(k_i k_j/(2m)\) is a factorized reference that preserves expected degrees. It is not the exact finite expected adjacency for distinct vertices under uniform pairing of a fixed number of stubs. For a finite stub-pairing model, that distinction matters; it is addressed below.

For a graph with nonnegative edge weights, replace \(A_{ij}\) by the weight \(w_{ij}\), degree \(k_i\) by strength \(s_i=\sum_j w_{ij}\), and edge count \(m\) by total edge weight \(W=\frac{1}{2}\sum_i s_i\). This gives the standard weighted modularity. In either case, the score is a comparison to a specified baseline, not a probability or a test statistic with an automatic significance threshold.

Deriving the Community-Level Formula

The defining sum can be reorganized by community. Let \(L_c\) be the number of edges whose two endpoints are in community \(c\), and let \(K_c=\sum_{i:c_i=c} k_i\) be the sum of the degrees of vertices in that community. Because the adjacency sum is over ordered pairs, each internal edge contributes twice to \(\sum_{i,j\in c} A_{ij}\). Therefore, its observed contribution after division by \(2m\) is \(2L_c/(2m)=L_c/m\).

For the baseline part, the sum over ordered pairs within \(c\) factorizes: \(\sum_{i,j\in c} k_i k_j/(2m)=K_c^2/(2m)\). Dividing that quantity by \(2m\) gives \(K_c^2/(2m)^2\). Adding the observed and baseline terms over all communities yields the equivalent formula:

This form makes the interpretation direct. The first term is the fraction of all edges that are internal to community \(c\). The second is the standard baseline’s predicted fraction of edge weight internal to that community, based on its share \(K_c/(2m)\) of all degree. Modularity adds the differences across communities.

Finite Stub Pairing and the Standard Baseline

A careful distinction is needed between the usual modularity formula and the exact expectation under uniform finite stub pairing. In the latter model, there are \(2m\) stubs, and each possible pairing of stubs is equally likely. For two distinct vertices \(i\) and \(j\), each of the \(k_i\) stubs at \(i\) can pair with any one of the \(k_j\) stubs at \(j\). A particular pair of stubs is matched with probability \(1/(2m-1)\), because after fixing one stub there are \(2m-1\) possible partners. By summing these probabilities, the exact expected number of edges between the distinct vertices is \(k_i k_j/(2m-1)\).

This is different from \(k_i k_j/(2m)\). The latter remains the conventional baseline in classic modularity and is often a useful large-graph approximation to the finite stub-pairing expectation. It should not be described as the exact distinct-vertex expectation for uniform finite stub pairing. The finite pairing model also permits loops and multiple edges, unlike a simple graph.

If the null model instead samples simple graphs with the given degree sequence, loops and multiple edges are prohibited. The expected adjacency probabilities for that model are generally not given exactly by either expression alone; they depend on the degree sequence and the graph constraint. Therefore, a modularity score should be reported and interpreted with its baseline convention in mind.

Weighted Graphs and Alternative Partitions

For a weighted graph, let \(W=\sum_{i<j}w_{ij}\) be total edge weight, \(s_i=\sum_j w_{ij}\) the strength of vertex \(i\), \(L_c\) the total weight of edges internal to \(c\), and \(S_c=\sum_{i:c_i=c}s_i\). The standard weighted formula follows the same logic: compare the observed fraction \(L_c/W\) with the baseline fraction \((S_c/(2W))^2\). The weights must be on a meaningful, nonnegative scale for this interpretation to apply.

Interpreting, Diagnosing, and Comparing Modularity

For a fixed graph and the standard baseline, a larger \(Q\) indicates that a larger excess of edge weight lies within communities relative to the degree-based reference. A score near zero indicates little net excess under this comparison; a negative score means the partition has less within-community weight than the baseline predicts in aggregate. These descriptions are relative, not absolute quality labels. Scores should not be compared uncritically across graphs with different construction choices, edge weights, or null-model conventions.

Modularity also differs from simply maximizing the number or fraction of internal edges. A raw within-edge count ignores how many edges are expected from the degree totals. A cut-based criterion instead focuses directly on edges crossing community boundaries, sometimes relative to community size or volume. Such criteria answer related but different questions; modularity’s defining feature is subtracting the degree-based expected contribution. Neither a high modularity score nor a small cut alone establishes that the partition corresponds to a biological mechanism.

Useful checks include verifying that the adjacency matrix is symmetric, that the stated \(m\) or \(W\) agrees with the edge list, and that each vertex belongs to exactly one community. For weighted graphs, check that total weight and strengths use the same edge weights. A frequent arithmetic error is to count each undirected edge once in \(L_c\) but then treat the adjacency sum as if it counted it once; the matrix formula counts it twice, which is why the community formula uses \(L_c/m\), not \(L_c/(2m)\).

A further pitfall is to say, “The configuration model’s exact expected adjacency is \(k_i k_j/(2m)\), so modularity is the exact excess over that model.” For distinct vertices under finite uniform stub pairing, this is not correct: the exact expectation is \(k_i k_j/(2m-1)\). The correction is to describe \(k_i k_j/(2m)\) as the standard modularity baseline (or a large-graph approximation in this context) and to keep it distinct from exact finite stub-pairing expectations. For weighted graphs, likewise, use the standard strength-based modularity baseline rather than claiming that an unweighted stub-pairing derivation applies unchanged.

Finally, modularity is a summary of a given partition, not a complete diagnostic of the graph or a measure of uncertainty. Different partitions can have similar scores, and a score alone does not identify which vertices are unstable or explain why a grouping arose. It is most informative when the graph construction, partition, and baseline are all reported clearly.