Software Clustering

Software clustering is the problem of recovering or prescribing the modular structure of a software system. For three decades it was studied as an optimization problem over a dependency graph. IVP reframes it: the difficulty of the problem is not an intrinsic feature of modularisation, but a consequence of doing it without a semantic criterion.

This page explains what IVP concludes about software clustering — why the traditional problem is hard, how IVP dissolves that hardness, and what the shift costs.

1 The traditional problem is NP-complete

Classical software clustering treats modularisation as an optimization problem: given a dependency graph, find the partition of elements that maximises cohesion and minimises coupling.

Mitchell and Mancoridis established in 2006 that this problem is NP-complete [1]. The field responded with metaheuristic search — hill-climbing, genetic algorithms, weighted graph partitioning — each searching for structurally good partitions that, in the worst case, cannot be found exactly in polynomial time.

The hardness is real, but it characterises the difficulty of partitioning without a semantic criterion, not an inherent difficulty of modularisation itself. Without knowing why elements change together, the optimiser cannot distinguish a well-motivated partition from a coincidental one. It must search exponentially many groupings, with no basis for preferring one structurally plausible partition over another.

2 What “cohesion” means in clustering

Classical clustering does not define cohesion by intent. It defines it operationally, as the internal connectivity of a cluster.

Given the dependency graph and a candidate partition, count for each module the edges inside it (cohesion) and the edges that cross its boundary (coupling). Every objective in the field is built on those two counts:

Modularisation quality (MQ). The cluster factor CF(M) = μ / (μ + ½·ε) combines the counts, and MQ averages it over the modules. TurboMQ weights edges by shared source file for multi-file systems. [2]
Modularity. The Newman–Girvan objective replaces the raw internal count with the excess of internal edge mass over a degree-preserving null model. [3] Optimising it is strongly NP-complete. [4]
Pattern-based clustering. ACDC recognises a subsystem as a body that dominates a cluster, then adopts orphans by connectivity — no scalar, but the same criterion of internal connectivity. [5]
Association-matrix clustering. Similarity is computed from shared data or calls, and cohesion is the sum of intra-cluster similarities. [6] [7]
Within-cluster compactness. Tools that borrow a data-clustering objective use the within-cluster sum of squares directly.

Cohesion and coupling therefore read the same graph. They differ only in which edges they count. A survey of the cohesion-metrics literature reaches the same conclusion from the metric side: cohesion metrics and coupling metrics examine the same graph and differ only in which partition of the edge set they report. [8]

3 IVP supplies the missing criterion

IVP provides the semantic criterion the traditional problem lacks.

Every element is governed by one or more change drivers: external conditions that, when they change, require the element to be modified. The change-driver assignment $\Gamma : E \to \mathcal{P}(C)$ maps each element to its set of governing drivers. The IVP partition $\mathcal{P}_\Gamma = E / \tilde{\Gamma}$ — grouping elements with identical driver assignments — is the modularisation that minimises both module-touch count per driver activation and within-module contamination cost.

4 Given Γ, clustering is polynomial

Once $\Gamma$ is in hand, no search is needed. Each element already carries its own module membership in $\Gamma(e)$ : two elements belong to the same module precisely when they share the same driver-assignment set. The bound $O(n \cdot d_{\max} \log d_{\max})$ falls out of the mechanics of that grouping, not from any deep theorem — you can count the operations yourself.

Deriving the cost, step by step, using the six-step application procedure:

Identify the elements (step 1). The analysis has $n = |E|$ elements to place. Every element appears once in the pass.
Map drivers to elements (step 3). Each element $e$ carries its assignment set $\Gamma(e)$ , of size $|\Gamma(e)| \le d_{\max}$ . Set equality does not depend on the order of its members, so each element needs a canonical form before it can serve as a grouping key.
Canonicalise each element’s key (step 5, preparation). Sorting the drivers inside each set makes every element’s key unambiguous: $\{a, b\}$ becomes the same key as $\{b, a\}$ . Sorting one set of size at most $d_{\max}$ costs at most $d_{\max} \log d_{\max}$ operations. Across all $n$ elements this is $O(n \cdot d_{\max} \log d_{\max})$ .
Group by identical key (step 5, main pass). Elements that share a driver-assignment set produce the same canonical key and therefore hash to the same bucket. Inserting one element costs $O(d_{\max})$ — hashing the set and comparing it against the keys of existing buckets. Across all $n$ elements this is $O(n \cdot d_{\max})$ .
Read off the modules. Each bucket is one equivalence class — one module. The number of modules is the number of distinct keys, never more than $n$ . Emitting them costs $O(n)$ .

Step 3 dominates the total: hashing (step 4) is $O(n \cdot d_{\max})$ and read-out (step 5) is $O(n)$ , while sorting is the only step carrying a $\log d_{\max}$ factor, so it sets the rate. So the whole pass is

$O(n \cdot d_{\max} \log d_{\max})$

When $d_{\max}$ is bounded by a constant — the practical case, where no element answers to more than a handful of drivers — each element’s work is one small sort and one hash, so step 3 costs $O(n)$ and the whole pass simplifies to $O(n)$ .

The result is deterministic. Every module in the IVP partition satisfies maximal causal cohesion $H_\text{causal}(M) = (1, 1)$ , and no other partition achieves $(1, 1)$ for all modules.

The same problem is strongly NP-complete over the dependency graph alone and polynomial when the driver assignment is supplied. The complexity class tracks the availability of the semantic criterion.

5 Clustering is not IVP

The output of clustering and the output of IVP share a shape: both partition the elements into modules. The relation that defines the partition differs, and the relation is the content.

Clustering partitions by graph connectivity (or by co-change similarity). Elements go together when they connect.
IVP partitions by Γ-equality. Elements go together when they share the same change drivers.

When dependencies track drivers, the two relations induce the same partition, and clustering acts as a search for the IVP partition. When they diverge, they diverge in both directions. An element that responds to two drivers is adjacent to both driver groups; a connectivity objective keeps it with one of them, while IVP isolates it. Two renderers for the same format that never call each other carry no edge between them; a connectivity objective separates them, while IVP joins them. Neither error is visible from the dependency graph, because both are defined relative to a Γ the graph does not carry.

This is why IVP does not derive from clustering, and does not replace it as a search method. IVP supplies the criterion the clustering objective lacks; clustering supplies a heuristic that approximates it when the criterion is not yet known. The clustering objective scores a partition by the same quantity it optimises — internal edge density — so it cannot say whether the partition is right. IVP is the independent criterion that the cohesion survey found missing from the literature. [8]

One clustering signal samples a different relation and is worth distinguishing, though it is not a better-measured one. Co-change groups elements that historical commits modified together. [9] A call edge records a standing interaction that a change may never exercise; a co-change records an actual modification, so co-change bears on the same question a change driver answers — what varies together — where connectivity does not. That is an alignment of modality, not of accuracy. Co-change fires both when a shared condition forces two elements to change and when a change to one element propagates to a dependent element, and it also fires on commit batching and on refactoring churn. Its error runs in both directions, and its size is not measurable from the co-change data alone. Co-change is a different proxy, not an established better one.

The confound has a direction. Shared-driver pairs co-change symmetrically; change propagation is one-directional, from the element depended upon to the element that depends on it. The directed conditional frequencies therefore carry more than a symmetric co-change count — but only as a filter that rules pairs out. Symmetry is necessary for driver-equivalence, not sufficient (mutual dependencies and commit batching produce it for the wrong reason), and asymmetry alone cannot separate genuine propagation from one element carrying every driver of the other.

6 The cohesion-coupling tension dissolves

The classical imperative — “maximise cohesion, minimise coupling” — treats the two as a trade-off to be balanced with weights. Under IVP, the trade-off was an artifact of optimising without a criterion.

Once every module achieves maximal causal cohesion, the coupling that modularisation can eliminate is eliminated by the same construction that maximises cohesion. The normative decomposition simultaneously maximises cohesion and minimises avoidable coupling — one optimum, not two. The weights encoded a problem that a principled criterion removes rather than solves.

7 The hard part shifts to driver identification

The polynomial result is conditional on $\Gamma$ being known. The complexity of the modularisation problem depends on what information is available:

$\Gamma$ fully known — polynomial: $O(n \cdot d_{\max} \log d_{\max})$ .
$\Gamma$ partially known — a mix: polynomial for the assigned elements, the traditional hard case for the rest.
$\Gamma$ entirely unknown — the NP-complete traditional case.

The polynomial advantage is therefore proportional to the completeness of the driver analysis. The hard part shifts from combinatorial search to driver identification — an epistemic problem that domain analysis must address.

The shift is an improvement, not a cost-shifting trick. Driver identification yields reusable knowledge about the domain. Partition search yields a configuration that is discarded on every requirements change.

8 Structural clustering returns as a hypothesis generator

When change drivers resist identification, structural clustering does not vanish — it changes role. It is demoted from design criterion to hypothesis generator.

Two reasons drive identification difficulty:

Epistemic. The change drivers exist and are well-defined, but the analyst cannot see them — missing domain expertise, absent artifacts, an inherited system with no design records. The drivers are there to be found.
Structural. The domain itself resists a clean decomposition — dense driver overlap, single-authority greenfield systems, rapidly changing driver sets. No sharp partition exists to recover.

Structural clustering helps with the first and not the second. In the epistemic case, dependency density and co-change history carry indirect evidence about the hidden driver structure and can be mined for it. A cluster the algorithm produces is a question worth asking: these elements are structurally close — is there an external condition whose activation would require all of them to change together? In the structural case, the underdetermination is real: no method recovers a sharp partition, because none exists.

9 Scope and limitations

The polynomial result holds when $\Gamma$ is known. The IVP advantage narrows in three cases:

Single-authority greenfield systems — all elements governed by a single driver; the partition is one module, and the analysis is trivial.
Systems with dense driver overlap — many elements with large, overlapping driver sets; the module count is genuinely large because the domain’s change structure is entangled.
Systems in rapid-change domains — driver assignments change frequently; the partition must be recomputed, and while each update is polynomial, the cumulative cost may be non-trivial.

Driver-equivalence does not put every element in its own module. Two elements share a module precisely when they share a driver assignment, and in any real system many elements do. The number of modules is the number of distinct driver-assignment sets, not the number of elements.

10 Where the proofs live

The claim that the Γ-equivalence partition is the unique partition achieving maximal causal cohesion for all modules, and that the cohesion-coupling tension dissolves, follows from the partition result proved in the published paper on the Independent Variation Principle [10], with the causal cohesion metric developed in the paper on causal cohesion [11] and the cost-minimum of the partition in the paper on change propagation and maintenance cost [12].

The formal development. The definitions, theorems, and proofs behind this page are published in:

Cohesion Metrics: A Survey of the Literature — Zenodo, 2026 — doi:10.5281/zenodo.21703227
The Independent Variation Principle — Zenodo, 2026 — doi:10.5281/zenodo.20794332
Causal Cohesion — Zenodo, 2026 — doi:10.5281/zenodo.21703156
Why Minimizing Change Propagation Minimizes Maintenance Cost — Zenodo, 2026 — doi:10.5281/zenodo.21362542

All published papers

References

[1]

B. S. Mitchell and S. Mancoridis, “On the automatic modularization of software systems using the Bunch tool,” IEEE Transactions on Software Engineering, vol. 32, no. 3, pp. 193–208, 2006.

[2]

S. Mancoridis, B. S. Mitchell, C. Rorres, Y.-F. Chen, and E. R. Gansner, “Using automatic clustering to produce high-level system organizations of source code,” in Proceedings of the 6th international workshop on program comprehension (IWPC), IEEE, 1998, pp. 45–52.

[3]

M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, no. 2, p. 026113, 2004.

[4]

U. Brandes et al., “On modularity clustering,” IEEE Transactions on Knowledge and Data Engineering, vol. 20, no. 2, pp. 172–188, 2008.

[5]

V. Tzerpos and R. C. Holt, “ACDC: An algorithm for comprehension-driven clustering,” in Proceedings of the 7th working conference on reverse engineering (WCRE), IEEE, 2000, pp. 258–267.

[6]

T. A. Wiggerts, “Using clustering algorithms in legacy systems remodularization,” in Proceedings of the 4th working conference on reverse engineering (WCRE), IEEE, 1997, pp. 33–43.

[7]

N. Anquetil and T. C. Lethbridge, “Experiments with clustering as a software remodularization method,” in Proceedings of the 6th working conference on reverse engineering (WCRE), IEEE, 1999, pp. 235–255.

[8]

Y. Loth, “Cohesion metrics: A survey of the literature.” Zenodo, Jul. 2026. doi: 10.5281/zenodo.21703227.

[9]

T. Stana and I. Sora, “Improving software architecture recovery through co-change augmented clustering,” IEEE Access, vol. 13, pp. 14112–14131, 2025, doi: 10.1109/ACCESS.2025.3535160.

[10]

Y. Loth, “The independent variation principle.” Zenodo, Jun. 2026. doi: 10.5281/zenodo.20794332.

[11]

Y. Loth, “Causal cohesion.” Zenodo, Jul. 2026. doi: 10.5281/zenodo.21703156.

[12]

Y. Loth, “Why minimizing change propagation minimizes maintenance cost.” Zenodo, Jul. 2026. doi: 10.5281/zenodo.21362542.