KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
URN: urn:nbn:de:swb:90-57774

On Modularity - NP-Completeness and Beyond

Brandes, Ulrik; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikolski, Zoran; Wagner, Dorothea


Modularity is a recently introduced quality measure for graph
clusterings. It has immediately received considerable attention
in several disciplines, and in particular in the complex
systems literature, although its properties are not well
understood. We here present first results on the computational
and analytical properties of modularity. The complexity status
of modularity maximization is resolved showing that the
corresponding decision version is NP-complete in the strong
sense. We also give a formulation as an Integer Linear Program
(ILP) to facilitate exact optimization, and provide results on
the approximation factor of the commonly used greedy algorithm.
Completing our investigation, we characterize clusterings with
maximum Modularity for several graph families.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2006
Sprache Englisch
Identifikator ISSN: 1432-7864
KITopen ID: 1000005777
Verlag Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2006,19
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page