Optimization Online


MILP formulations for the modularity density maximization problem

Alberto Costa (costa***at***lix.polytechnique.fr)

Abstract: Cluster analysis refers to finding subsets of vertices of a graph (called clusters) which are more likely to be joined pairwise than vertices in different clusters. In the last years this topic has been studied by many researchers, and several methods have been proposed. One of the most popular is to maximize the modularity, which represents the fraction of edges within clusters minus the expected fraction of such edges in a random graph with the same degree distribution. However, this criterion presents some issues, for example the resolution limit, i.e., the difficulty to detect clusters having small sizes. In this paper we focus on a recent measure, called modularity density, which improves the resolution limit issue of modularity. The problem of maximizing the modularity density can be described by means of a 0-1 NLP formulation. We derive some properties of the optimal solution which will be used to tighten the formulation, and we propose some MILP reformulations which yield an improvement of the resolution time.

Keywords: Clustering; Mixed integer linear programming; Modularity density maximization; Reformulations

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

Category 2: Network Optimization

Citation: http://www.sciencedirect.com/science/article/pii/S0377221715002052


Entry Submitted: 10/09/2014
Entry Accepted: 10/10/2014
Entry Last Modified: 03/16/2015

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