Robustness analysis of network modularity

Abstract

Modules are commonly observed functional units in large-scale networks and the dynamics of networks are closely related to the organization of such modules. Modularity analysis has been widely used to investigate the organizing principle of complex networks. The information about network topology needed for such modularity analysis is, however, not complete in many real world networks. We noted that network structure is often reconstructed based on partial observation and therefore it is re-organized as more information is collected. Hence, it is critical to evaluate the robustness of network modules with respect to uncertainties. For this purpose, we have developed a robustness bounds algorithm that provides an estimation of the unknown minimal perturbation, which breaks down the original modularity. The proposed algorithm is computationally efficient and provides valuable information about the robustness of modularity for large-scale network analysis.