Comparaisons de similitudes entre des ensembles de nœuds dans des graphes

Bonjour tout le monde,

Je suis à la recherche d’idées afin d’effectuer des mesures statistiques pour comparer deux solutions. L’outil en question essaye de regrouper ensemble des nœuds dans un graphe. Et je souhaiterais mesurer à quel point ce regroupement est similaire à ce que fournit un autre outil.

Des exemples seront sans doute plus concret; supposons que je possède 3 éléments: A, B, C.

• 1er cas = les mêmes: Outil 1 dit que A, B & C sont ensemble ainsi que l’outil 2 => parfait !
• 2e cas = en +: Outil 1 dit que A, B sont ensemble (et C isolé) tandis que l’outil 2 dit que ce sont 3 ensembles différents.
• 3e cas = en -: Outil 1 dit que ce sont 3 ensembles différents et outil 2 dit que B et C sont ensemble.
• 4e cas = en + et en -: Outil 1 dit que: A, B sont ensemble (et C isolé) tandis que l’outil 2 dit que B et C sont ensemble.

Intuitivement, j’ai pensé à un notion de type: 'Jaccard Index’, mais je souhaiterais avoir une unité banane sur tous les cas. Un truc qui mesure tous les groupements au sein d’une même population qui passerait à la fois au travers de l’outil 1 et de l’outil 2. Je pensais partir vers un truc de type: 'Mutual information score' mais je ne sais pas si vous auriez d’autres recommandations à proposer. Ce qui serait vraiment parfait, c’est d’avoir des mesures de type: precision/recall, pour savoir si on essaye de minimiser les regroupements 'erronés’ (vrai négatif) ou maximiser les regroupements qu’on a manqué (faux positif).

Ici, on connaît chacun des éléments mais pas les 'classes’, si elles sont données à une permutation près, c’est bon. Je pense qu’on peut formuler cela comme une mesure du partitionnement.

Merci d’avance pour vos réponses !

Je ne suis pas sur d’avoir suivi, mais tentons cette réponse.

Tu as la situation A, par exemple ((1,2,3)(4,5)(6,7,8,9)), et tu as la situation B, par exemple ((1,2,3,4)(5,6,7)(8,9)), et tu cherches à calculer une certaine 'Distance' entre ces 2 situations.

On peut envisager un 'jeu’, et la règle de ce jeu, ce serait d’aller de A à B, avec les mouvements suivants : A chaque mouvement, on peut prendre une poignée de nombres dans un des sous-groupes, et soit créer un nouveau groupe avec cette poignée, soit ajouter cette poignée à un sous-groupe existant.

Et le but du jeu, c’est évidemment d’aller de la situation A à la situation B en un minimum de mouvements.

Par exemple à partir de ((1,2,3)(4,5)(6,7,8,9)), on déplace le 4, et on arrive à ((1,2,3,4)(5)(6,7,8,9)), puis on déplace la paire (6,7) et on arrive à ((1,2,3,4)(5,6,7)(8,9)) ; il fallait donc 2 mouvements pour aller de la position A à la position B.

La distance entre ces 2 positions était de 2.

Si c’est effectivement la règle que tu veux implémenter, il ne reste qu’à la programmer