Extreme Degeneracies Characterize the Module Identification Problem for Complex Networks

Identifying modular structure in complex networks is a fundamental task for understanding the function, dynamics, robustness and evolution of complex biological, technological and social systems. Although widely used in practice, the accuracy of popular identification techniques, such as the one based on optimizing the quantity called modularity, remains poorly characterized. Here, we present a systemic and critical analysis of this method. We show analytically that in addition to the previously observed resolution limit, the modularity function $Q$ exhibits extreme degeneracies, admitting an exponential number of high-modularity but structurally distinct solutions. The presence of hierarchical structure, in which modules organize themselves into modules-of-modules and which is believed to characterize many real-world networks, further exacerbates this problem. We confirm our analytic results using numerical experiments on synthetic networks with either modular or hierarchical structure and on several real-world examples of metabolic networks. These results contradict the widely held assumption that the modularity function typically exhibits a clear global optimum, and imply that modules identified via modularity maximization are unlikely to be unique and should be interpreted with extreme caution. We conclude with a brief discussion of alternative avenues for accurately and objectively identifying modular structure.