Coloring graph with constraints on assortativity I have come across the following problem and I would love for your thoughts on an optimal solution or approximate calculations worth trying.
The formulation of the problem in the form of graph theory:
Given a weighted graph $G=(V, E)$. In addition, we have $C$ colors and $f([C_1, ...C_n])$ the distribution function of vertices in the graph by color (That is, how many nodes of each color are in the graph). Also given an assortativity parameter, $M$. In general, assortativity is the tendency of nodes in the graph to attach to others that are similar in some way. For simplicity, set it to be the number of edges between vertices of the same color (Originally it is a little more sophisticated calculation. But unnecessary for our needs.).
Now, I want to color the graph such that the constraint on the number of vertices of each color is met and in addition, we minimize the expression: $|M-M(G)|$ (recall,  $M$ is the desired parameter and $M(G)$ is the parameter as it is calculated on the given coloring). Of course, we are not only interested in the minimum value, but also the coloring that created it.
This problem also has a parallel formulation for matrices:
Given symmetric matrix $A$ ($n\times n$) - this is the adjacency matrix of the above graph. The value of the entry $A_{ij}$ is set to equal the weight of the edge $(i,j)$. Here, too, we are given a distribution function of the rows and the columns in the matrix by color. As before, we have an assortativity parameter, $M$.
Now, let's try to find symmetric coloring of rows and columns in the matrix (if any line is colored in a certain color, so is the corresponding column) such that the constraint on the number of rows and columns of each color is met.
In addition, we will try to minimize the expression: $|M-\Sigma(A_{i,j}|\text{where column } i \text{ and row } j \text{ are in same color})|$ (which means, the difference between the desired $M$ and the sum of all entries that their colum and their row are in same color).
Epilogue:
I know that both formulas are completely equal. I hope the two different perspectives help me and others to think about different directions to solve the problem.
For the sake of curiosity, I will say that this problem is part of a challenge I face and it is to generate pseudo-synthetic social networks with real-life constraints. This is a problem that I formulated and not part of an article or a home exercise.
Thanks in advance.
Your problem is NP-hard.  Consider the special case where $M=0$; then your problem is as hard as the graph coloring problem, which is NP-hard. (Ok, with an additional constraint on the distribution function, but it will still be NP-hard.)  In particular, if $M=0$ and the graph is $C$-colorable, then the optimal solution have $|M-M(G)|=0$; if the graph is not $C$-colorable, then the optimal solution will have $|M-M(G)|&gt;0$.  So, if we could find the optimal solution for your problem for arbitrary $M$, we could determine whether the graph is $C$-colorable by setting $M=0$, finding the optimal solution, and checking whether $|M-M(G)|=0$.
One possible approach to finding an approximate solution would be to try local search or simulated annealing.