Exact computational solution of Modularity Density Maximization by effective column generation

Modularity Density Maximization (MDM) is associated with clustering problems in networks. MDM is an alternative to the resolution limit issue of the Modularity Maximization problem. Several reports in the literature have described mathematical programming models for MDM which solve instances of at most 40 nodes. In this context, this paper presents six new column generation methods that find exact solutions for the MDM problem. These methods use exact and auxiliary heuristic problems and an initial variable generator. Our methods show clear improvements over current results. Comparisons between our proposed methods and state-of-the-art algorithms are also carried out. Our results show that (i) two of our methods surpass the exact state-of-the-art algorithms in terms of time, and (ii) our methods provide optimal values for larger instances than current approaches can tackle.