Divisive heuristic for modularity density maximization

作     者：Costa, Alberto Kushnarev, Sergey Liberti, Leo Sun, Zeyu 

作者机构：Natl Univ Singapore Singapore 117548 Singapore Swiss Fed Inst Technol Future Resilient Syst Program Singapore Singapore Singapore Univ Technol & Design Singapore Singapore Ecole Polytech CNRS LIX F-91128 Palaiseau France 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2016年第71卷第Jul.期

页      面：100-109页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：SUTD-MIT International Design Center [IDG21300102] NRF's Campus for Research Excellence and Technological Enterprise (CREATE) programme [FI 370074011] 

主　　题：Clustering Modularity density maximization Multilinear terms Reformulation Heuristic 

摘      要：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. (C) 2016 Elsevier Ltd. All rights reserved.