Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner
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 study the problem of
finding clusterings with maximum modularity, thus providing theoretical
foundations for past and present work based on this measure. More
precisely, we prove the conjectured hardness of maximizing modularity
both in the general case and with the restriction to cuts, and give an
Integer Linear Programming formulation. This is complemented by first
insights into the behavior and performance of the commonly applied
greedy agglomaration approach.
This work has appeared in part as an
extended abstract at WG 2007.
| Download: |
|