Community detection and analysis of community evolution in apache ant class collaboration networks

Abstract

In this paper we investigate community detection algorithms applied to class collaboration networks (CCNs) that represent class dependencies of 21 consecutive versions of the Apache Ant software system. Four community detection techniques, Girvan- Newman (GN), Greedy Modularity Optimization (GMO), Walktrap and Label Propagation (LP), are used to compute community partitions. Obtained community structures are evaluated using community quality metrics (inter- and intracluster density, conductance and expansion) and compared to package structures of analyzed software. In order to investigate evolutionary stability of community detection methods, we designed an algorithm for tracking evolving communities. For LP and GMO, algorithms that produce partitions with higher values of normalized modularity score compared to GN and Walktrap, we noticed an evolutionary degeneracy - LP and GMO are extremely sensitive to small evolutionary changes in CCN structure. Walktrap shows the best performance considering community quality, evolutionary stability and comparison with actual class groupings into packages. Coarse-grained descriptions (CGD) of CCNs are constructed from Walktrap partitions and analyzed. Results suggest that CCNs have modular structure that cannot be considered as hierarchical, due to the existence of large strongly connected components in CGDs. Copyright 2012 ACM.