1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Jun 25 at 21:33
  • $\begingroup$ @D.W. - I fixed it. Thanks. $\endgroup$ – Yanirmr Jun 26 at 5:51
2
$\begingroup$

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$.

One possible approach to finding an approximate solution would be to try local search or simulated annealing.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for the answer. I did not understand why the problem is equivalent to a regular coloring graph problem. The classic problem has constraints on the colors that neighbors have, in my case - there is no such constraint. $\endgroup$ – Yanirmr Jun 26 at 7:12
  • $\begingroup$ @Yanirmr, see edited answer. Your version does have such a constraint; if $M(G)=0$, then that imposes such a constraint. $\endgroup$ – D.W. Jun 26 at 7:15
  • $\begingroup$ Got it. Thanks. $\endgroup$ – Yanirmr Jun 26 at 7:28
0
$\begingroup$
  • for specific values of M it is not necessarily NP-hard.
  • so if you have a constraint over M it might be useful.
  • also, you are asking for optimization and not the best solution (sometimes optimizing is as hard as solving, but it requires another argument).
  • and lastly, regarding NP, it might be practically solvable for large graphs with heuristics (we have SAT solvers)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (There are times where I am at odds with American English. The optimum is the best. Sadly, "optimize" has been used where improve would have avoided hyperbolism.) $\endgroup$ – greybeard Jun 27 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.