A ground truth contest between modularity maximization and modularity density maximization

摘要

Computational techniques for network clustering identification are critical to several application domains. Recently, Modularity Maximization and Modularity Density Maximization have become two of the main techniques that provide computational methods to identify network clusterings. Therefore, understanding their differences and common characteristics is fundamental to decide which one is best suited for a given application. Several heuristics and exact methods have been developed for both Modularity Maximization and Modularity Density Maximization problems. Unfortunately, no structured methodological comparison between the two techniques has been proposed yet. This paper reports a ground truth contest between both optimization problems. We do so aiming to compare their exact solutions and the results of heuristics inspired in these problems. In our analysis, we use branch-and-price exact methods which apply the best-known column generation procedures. The heuristic methods obtain the highest objective function scores and find solutions for networks with hundreds of thousands of nodes. Our experiments suggest that Modularity Density Maximization yields the best results over the tested networks. The experiments also show the behavior and importance of the quantitative factor of the Modularity Density Maximization objective function.