Rendre la coloration de graphe moins stricte

Question

J'expérimente avec l'algorithme graph coloring. C'est une façon de colorer les nœuds d'un graphe de telle sorte que pas 2 nœuds adjacents aient la même couleur.

Supposons que je les données suivantes que je veux « couleur » (attribuer à des groupes), où chaque mot est un nœud:

1. chat noir
2. chat gris
3. chien gris
4. chien noir

Je me attends les groupes suivants:

• chat, chien
• noir, gris

Mais si j'ajouter le nom de mon 4ème animal, qui est grey (comme la couleur)?
Ainsi, la 4ème ligne devient:

1. chien gris noir

L'algorithme de coloration ne pouvait pas distinguer entre les couleurs et les noms, donc black et grey se terminerait en différents groupes.

Comment est-ce que je pourrais ajuster l'algorithme pour qu'il devienne "moins strict"? Comme: Seulement si 2 nœuds apparaissent ensemble à plus de 90%, considérez-les comme adjacents et placez-les dans le même groupe.

Remarque: L'exemple que j'ai fourni est simplifié. Je ne peux pas simplement regrouper mes mots par name ou color, donc j'ai besoin d'une approche plus générale.

Answer 1

(Espérant bien compris votre question - votre exemple ne pas vraiment aider)

donc actuellement que vous produisez le graphique suivant à être de couleur à partir de vos données d'entrée:

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

maintenant vous pouvez affecter un libellé entier à chaque arête en comptant la fréquence à laquelle la paire correspondante apparaît ensemble dans un élément de liste. Ensuite, vous définissez un seuil inférieur et supprimez tous les bords étiquetés avec un nombre plus petit. Si vous colorez maintenant le graphique résultant, ces paires "rares" sont de nouveau autorisées à avoir une couleur commune.