Divisive heuristic for modularity density maximization. (July 2016)

• Record Type: Journal Article
• Authors: Costa, Alberto; Kushnarev, Sergey; Liberti, Leo; Sun, Zeyu
• Is Part Of: Computers & operations research. Volume 71(2016)
• Page Start: 100
• Page End: 109
• Publication Date: 2016-07
• Subjects: Clustering -- Modularity density maximization -- Multilinear terms -- Reformulation -- Heuristic; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.01.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Abstract : Highlights: 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.