BookSectionincollectionspringerlink:10.1007/978-3-540-74839-7_12On Finding Graph Clusterings with Maximum Modularity2007BrandesUlrikDellingDanielGaertlerMarcoGörkeRobertHoeferMartinNikoloskiZoranWagnerDorotheaBrandstädtAndreasKratschDieterMüllerHaiko121-1324769 ISBN: 978-3-540-74838-0 DOI: 10.1007/978-3-540-74839-7_12SpringerBerlin / HeidelbergGraph-Theoretic Concepts in Computer ScienceGraph-Theoretic Concepts in Computer Sciencehttp://dx.doi.org/10.1007/978-3-540-74839-7_12Lecture Notes in Computer ScienceModularity 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.clustering, graph, modularity, theoryDepartment of Computer and Information Science, University of Konstanz