Q:

NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the size of every part is the same, i.e., $k$. The goal is to maxmize the sum of the shared neighbors of every part, which can be difined as:
\begin{gather}
    \sum_{i=1}^m SN_{i}\\
    s.t. \quad\qquad SN_{i} = \cap_{v_i \in P_i} Nei(v_i)\\
    |P_i| = k\\
    \qquad \sum_{i=1}^m |P_i| = nk
\end{gather}
where $SN_{i}$ is the shared neighbours of the nodes in part $P_i$. For convenience, we regard that the node is the neighbour of itself.
I think the problem is np-hard. In my view, we can construct a specific graph which contains n k-clique. We then think about it as a clique-cover problem. However, I think the solution is a little strange... How should we prove it? 
Thanks in advance!!! 

A:

You can notice that $SN_i$ is maximum if $P_i$ is a clique of size $|P_i|$.
So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts $P_i$ have the same size.
But the problem of partitioning a graph into 3 cliques of the same size is still NP-complete.
Indeed 3-COLORING remains NP-complete even if we require that all color classes have the same size (I'll call it EQUAL SIZE 3-COLORING). A quick proof idea is: given $G$ make 3 copies of it $G_1, G_2, G_3$, pick the same node $v$ in each copy of $G$: ($v_1, v_2, v_3 $) and "link" them to form a clique $K_3$. $G$ is 3 colorable if and only if $G' = G_1 \cup G_2 \cup G_3 \cup K_3$ is 3 colorable with equal size color classes.
But EQUAL SIZE 3-COLORING a graph $G$ with $3n$ nodes is equivalent to find 3 cliques of size $n$ in its dual $\bar G$. Which is also equivalent to partition $\bar G$ into 3 parts with a total sum $\sum SN_i = 3n$ 

