Uneven Density and Community Boundaries

Why Density and Boundaries Do Not Tell the Whole Story

A graph can contain a tightly connected group next to a region with fewer internal edges, with only a few edges linking the two. It is tempting to conclude that the dense group must be one community and the sparse region another. But a community assignment depends not just on whether a boundary looks weak. It also depends on the objective being optimized, the sizes and degrees of the candidate groups, and the chosen resolution.

This tutorial compares two objectives for undirected graphs: modularity and the Constant Potts Model (CPM). Both evaluate partitions by comparing within-community connections against a reference, but they use different references. Consequently, the same graph and boundary can lead them to favor different assignments. The calculations below compare specific candidate partitions; they do not imply that every partition found by an algorithm is globally optimal.

A low boundary density means that relatively few possible edges across the boundary are present. It does not by itself determine whether merging the communities improves an objective. In particular, “few” may mean something different for two small groups than for two large groups, and modularity also accounts for vertex degrees across the whole graph.

Two Objectives, Two Reference Points

For a simple undirected graph with \(m\) edges, let \(A_{ij}\) be 1 when vertices \(i\) and \(j\) share an edge and 0 otherwise, and let \(k_i\) be the degree of vertex \(i\). The modularity of a partition is

Here \(c_i\) is the community assigned to vertex \(i\), \(\mathbf{1}(c_i=c_j)\) is 1 when the vertices share a community and 0 otherwise, and \(\gamma>0\) is the resolution parameter. The term \(k_i k_j/(2m)\) is the expected adjacency contribution under the configuration-model reference used by modularity. Thus modularity rewards within-community edges relative to a degree-based expectation. It is not simply a score for high internal density.

For candidate communities \(C\), the same modularity can be written using \(m_C\), the number of edges internal to \(C\), and \(K_C=\sum_{i\in C}k_i\), the sum of degrees in \(C\):

The CPM objective for this unweighted graph is

CPM rewards each internal edge and subtracts a penalty for each possible pair within a community. For a fixed partition, a community’s contribution is positive when its internal edge density exceeds \(\gamma\). Unlike modularity’s degree-based reference, CPM uses a pair-count penalty; its resolution parameter is on an edge-per-pair scale. The numerical values of \(\gamma\) in these two objectives are therefore not directly comparable.

Deriving the Merge Comparisons

Suppose communities \(A\) and \(B\) are separate in one candidate partition and merged in another. For modularity, merging changes the internal edge count from \(m_A+m_B\) to \(m_A+m_B+e_{AB}\), and changes the combined degree sum from separate terms to \(K_A+K_B\). Subtracting the separate score from the merged score gives

The merge improves modularity precisely when \(\Delta Q>0\). The first term is the observed boundary-edge contribution; the second is the degree-based penalty for combining the groups. This comparison depends on graph-wide \(m\) and on both groups’ degree sums, not only on their boundary density.

For CPM, the merge adds \(e_{AB}\) observed edges and introduces a penalty for all \(n_A n_B\) new possible pairs between the groups. Hence

The CPM merge improves the objective when \(e_{AB}/(n_A n_B)>\gamma\): the boundary density exceeds the chosen resolution. This clean threshold helps explain CPM’s response to group size, but it is only a comparison of these two partitions. Other possible splits or merges can still matter to the full optimization.

When the Same Boundary Produces Different Choices

Reading Local Density and Boundary Evidence

These comparisons suggest a disciplined way to interpret a graph partition. First measure the internal and boundary edge densities for the groups of interest. Then calculate the objective-specific merge change at the resolution actually used. A weak boundary may support keeping groups separate, but it is not a universal rule: in modularity, the relevant comparison includes degree sums and total graph size; in CPM, the boundary density is compared with \(\gamma\).

Local density can also point in different directions within one graph. A dense group may have many internal edges but also high degree, which raises modularity’s degree-based merge penalty with another group. A sparse group may have few internal edges, yet a sufficiently low CPM resolution can still make joining it to a neighbor favorable if the boundary density exceeds that resolution. Neither objective defines a community solely by being “dense” in an absolute sense.

For a practical check, calculate summaries for candidate boundaries rather than relying only on a graph drawing:

• Record \(n_A\), \(n_B\), \(m_A\), \(m_B\), and \(e_{AB}\), and calculate each within-group and boundary density.
• For modularity, also record \(K_A\), \(K_B\), and the graph-wide \(m\); evaluate \(\Delta Q\) at the chosen \(\gamma\).
• For CPM, compare \(e_{AB}/(n_A n_B)\) with the chosen \(\gamma\).
• Check whether a small change in resolution or a single boundary edge reverses the comparison. Such sensitivity is evidence that the assignment is conditional on modeling choices, not proof that one partition is biologically correct.

An edge-count comparison does not establish that a boundary corresponds to a biological separation. A graph can reflect choices made during cell representation and neighborhood construction, and a community objective only evaluates the graph it receives. A high-scoring partition is therefore a property of the graph and objective, not a causal or biological validation by itself.

Common Pitfalls and Alternatives

Pitfall: “There is only one edge between these two groups, so every community method must keep them separate.” This reasoning ignores group sizes, degree structure, and resolution. In the two-triangle example, modularity at \(\gamma=1\) favored separation while CPM at \(\gamma=0.1\) favored merging. The correction is to calculate the merge change for the particular objective and parameter, then describe the conclusion as conditional on those choices.

A related mistake is to treat a high internal density as sufficient evidence for a community. The triangle example has two internally complete groups, yet CPM can favor merging them. Conversely, a sparse group is not automatically absorbed: its boundary may be too weak under the selected objective. Internal and boundary densities are useful descriptions, not standalone decision rules.

Modularity and CPM are not the only ways to partition graphs. Flow-based methods such as Infomap evaluate how a random walk can be compressed, so their criterion is not the same as modularity’s degree-based null comparison or CPM’s pair-density threshold. The choice between objectives should follow the structure one wants to represent and be checked against plausible resolution choices. Repeated optimization from different initial conditions can reveal algorithmic variability, but agreement across runs does not remove an objective’s modeling assumptions.

Finally, a positive merge change for one pair does not prove that the resulting full partition is optimal. Other vertices may move, or other groups may split or merge. The calculations are exact comparisons between the stated alternatives; a clustering algorithm searches a much larger space and may use a heuristic. Interpret local calculations accordingly.