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


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
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2006
Sprache Englisch
Identifikator ISSN: 1432-7864
KITopen-ID: 1000005777
Verlag Universität Karlsruhe, Karlsruhe
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page