Dense and sparse graph partition

In a graph G=(V,E)G=(V,E), the density is the ratio between the number of edges |E||E| and the number of vertices |V||V|. This criterion may be used to find communities in a graph: groups of highly connected vertices. We propose an optimization problem based on this criterion; the idea is to find the vertex partition that maximizes the sum of the densities of each class. We prove that this problem is NP-hard by giving a reduction from graph-kk-colorability. Additionally, we give a polynomial time algorithm for the special case of trees.