 MILP formulations for the modularity density maximization problemAlberto Costa European Journal of Operational Research, 2015, vol. 245, issue 1, 14-21 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 (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:245:y:2015:i:1:p:14-21 DOI: 10.1016/j.ejor.2015.03.012 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.