Make Graph Coloring less strict

1
votes

I'm experimenting with the graph coloring algorithm. That is a way of coloring the nodes of a graph such that no 2 adjacent nodes have the same color.

Suppose I have the following data I want to "color" (assign to groups), where each word is a node:

  1. cat black
  2. cat grey
  3. dog grey
  4. dog black

I would expect the following groups:

  • cat, dog
  • black, grey

But what if I add the name of my 4th animal, which is grey (just like the color)?
So the 4th line becomes:

  1. dog black grey

The coloring algorithm couldn't distinguish between colors and names, so black and grey would end up in different groups.

How could I adjust the algorithm so that it becomes "less strict"?
Like: Only if 2 nodes appear in more than 90% together, consider them adjacent and put them in the same group.

Note: The example I provided is simplified. I can't just group my words by name or color, so I need a more general approach.

1
javascriptalgorithmgraphgraph-algorithmgraph-coloring

1 Answers

0
votes

(Hoping to get your question right - your example doesn't really help)

So currently you produce the following to-be-colored graph from your input data:

cat--black
 |   / |
 |  /  |
grey--dog

Now you could assign an integer label to each edge counting how often the corresponding pair appears together in a list item. Then you define some lower threshold and delete all edges labelled with a smaller number. If you now color the resulting graph, these "rare" pairs are again allowed a common color.