| abstract |
Modularity is a recently introduced quality measure for graph
clusterings. Currently it is attracting wide attention in application
areas such as physics or biology. We take the first approach to capture
computational and analytical properties of this measure. In particular,
we present characterizations of clusterings with maximum modularity and
optimality results for certain graph families. The complexity status of
modularity maximization is resolved showing that the corresponding
decision version is NP-complete in the strong sense. Finally, we provide
a lower bound of 2 on the approximation factor of a commonly used greedy
algorithm.
|
