Optimization Online


Divisive heuristic for modularity density maximization

Alberto Costa (costa***at***lix.polytechnique.fr)
Sergey Kushnarev (sergey_kushnarev***at***sutd.edu.sg)
Leo Liberti (liberti***at***lix.polytechnique.fr)
Zeyu Sun (zeyu_sun***at***mymail.sutd.edu.sg)

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.

Keywords: Clustering, Modularity density maximization, Multilinear terms, Reformulation, Heuristic

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Network Optimization

Citation: http://www.sciencedirect.com/science/article/pii/S0305054816000113?np=y


Entry Submitted: 09/22/2015
Entry Accepted: 09/22/2015
Entry Last Modified: 02/11/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society