Divisive heuristic for modularity density maximization

• We propose a divisive heuristic for modularity density maximization.
• We derive some reformulations for the optimal splitting problem.
• We identify the best formulation using statistical tests.
• The heuristic provides near-optimal solutions in terms of modularity density value.

In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. We report computational results of the eight algorithms (four reformulations with two different symmetry breaking strategies) obtained on some instances from the literature. Statistical tests show that the best model in terms of computational time is the one that is obtained with a dual reformulation of the bilinear terms arising in the objective function. Moreover, the hierarchical divisive heuristic provides generally near-optimal solutions in terms of modularity density.