Reformulation of a model for hierarchical divisive graph modularity maximization

Sonia Cafieri (), Alberto Costa () and Pierre Hansen ()

Annals of Operations Research, 2014, vol. 222, issue 1, 213-226

Abstract: Finding clusters, or communities, in a graph, or network is a very important problem which arises in many domains. Several models were proposed for its solution. One of the most studied and exploited is the maximization of the so called modularity, which represents the sum over all communities of the fraction of edges within these communities minus the expected fraction of such edges in a random graph with the same distribution of degrees. As this problem is NP-hard, a few non-polynomial algorithms and a large number of heuristics were proposed in order to find respectively optimal or high modularity partitions for a given graph. We focus on one of these heuristics, namely a divisive hierarchical method, which works by recursively splitting a cluster into two new clusters in an optimal way. This splitting step is performed by solving a convex quadratic program. We propose a compact reformulation of such model, using change of variables, expansion of integers in powers of two and symmetry breaking constraints. The resolution time is reduced by a factor up to 10 with respect to the one obtained with the original formulation. Copyright Springer Science+Business Media New York 2014

Keywords: Clustering; Compact reformulation; Divisive hierarchical heuristic; Modularity maximization (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-012-1286-z (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:222:y:2014:i:1:p:213-226:10.1007/s10479-012-1286-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-012-1286-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().