Comparison of Graph Clustering Algorithms for Recovering Software Architecture Module Views

In the domain of software architecture recovery, classical clustering algorithms have been used to recover module views, while new ones have been proposed to tackle specific software architecture issues. Nonetheless, little information concerning their empirical evaluation in this context is presently available. This paper presents an empirical study that evaluates four clustering algorithms according to three previously proposed criteria: extremity of cluster distribution, authoritativeness, and stability, which were measured against consecutive releases of four different systems. Our results suggest that the k-means algorithm performs best in terms of authoritativeness and extremity and that the modularization quality algorithm produces more stable clusters. They also point out that fully automated clustering techniques alone cannot recover module views in a sensible way, but may provide a reasonable first step to speed up an expert-assisted architecture recovery process.