This paper studies the problem of finding clusterings with maximum modularity, providing theoretical foundations for past and present work based on this measure. Modularity is a quality measure for graph clusterings, defined as the difference between the number of edges within clusters and the expected number of edges if the graph were randomly partitioned. The authors prove the conjectured hardness of maximizing modularity in both the general case and the restriction to cuts, and provide an integer linear programming formulation for optimization. They also analyze the performance of the greedy agglomerative approach, showing that it can have an approximation factor of two in some cases. The paper also discusses the behavior of modularity in various graph structures, including cliques and cycles, and shows that the quality of greedy clusterings can heavily depend on the tie-breaking strategy used. The authors conclude that modularity maximization is NP-complete, and that the greedy algorithm is unlikely to be optimal. The paper also provides examples where the greedy algorithm fails to find the optimal clustering.This paper studies the problem of finding clusterings with maximum modularity, providing theoretical foundations for past and present work based on this measure. Modularity is a quality measure for graph clusterings, defined as the difference between the number of edges within clusters and the expected number of edges if the graph were randomly partitioned. The authors prove the conjectured hardness of maximizing modularity in both the general case and the restriction to cuts, and provide an integer linear programming formulation for optimization. They also analyze the performance of the greedy agglomerative approach, showing that it can have an approximation factor of two in some cases. The paper also discusses the behavior of modularity in various graph structures, including cliques and cycles, and shows that the quality of greedy clusterings can heavily depend on the tie-breaking strategy used. The authors conclude that modularity maximization is NP-complete, and that the greedy algorithm is unlikely to be optimal. The paper also provides examples where the greedy algorithm fails to find the optimal clustering.