KIT | KIT-Bibliothek | Impressum | Datenschutz

On Modularity - NP-Completeness and Beyond

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

Abstract:

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.

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000005777
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2006
Sprache Englisch
Identifikator ISSN: 1432-7864
urn:nbn:de:swb:90-57774
KITopen-ID: 1000005777
Verlag Universität Karlsruhe, 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