# 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 for the improvements to your question! Can you edit your question to make it self-contained by providing a definition of $M(G)$? Is it the number of edges where both endpoints of the edge have the same color? In your matrix formulation, the entries of the matrix don't seem to affect the answer; is that really what you intended? – D.W. Jun 25 '20 at 21:33
• @D.W. - I fixed it. Thanks. – Yanirmr Jun 26 '20 at 5:51

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)|>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$$.
• @Yanirmr, see edited answer. Your version does have such a constraint; if $M(G)=0$, then that imposes such a constraint. – D.W. Jun 26 '20 at 7:15