Algorithmes de regroupement de graphes qui prennent en compte les poids négatifs

8

J'ai une instance de graphique avec des bords dirigés pondérés dont les valeurs peuvent être dans la plage [-1,1]. J'ai besoin de faire un clustering sur ce graphique, afin de trouver des groupes dans lesquels les sommets sont plus corrélés.

J'ai cherché plusieurs algorithmes basés sur des grappes ou des graphiques de détection de communauté, mais la plupart d'entre eux ne fonctionnent pas en raison des poids négatifs. Jusqu'à présent, j'ai appliqué un algorithme de spinglass (c'est ce qu'on appelle dans la bibliothèque igraph , c'est un algorithme basé sur le modèle de Potts) qui semble fonctionner avec des poids positifs et négatifs.

Existe-t-il d'autres algorithmes pour effectuer le clustering ou la détection de communauté sur des graphiques qui ont des poids de bord négatifs et positifs?

Mise à jour: les poids de bord représentent des corrélations, 1 signifie que deux sommets sont fortement corrélés, -1 qui sont inversement corrélés et 0 signifie qui sont indépendants.

correlation clustering graph-theory networks igraph Ewybe
la source
Que représentent les poids?
eliasah
@eliasah J'ai fait une mise à jour afin d'expliquer cela
Ewybe
Avez-vous essayé d'utiliser une autre balance? Cela pourrait être une bonne solution en utilisant une méthode de clustering régulière basée sur l'algorithme de centralité d'interdépendance par exemple.
eliasah
@eliasah La mise à l'échelle de ces données ne sera peut-être pas si facile car je souhaite conserver le sens de la corrélation
Ewybe
1
Pour le clustering, le signe de la corrélation est-il vraiment nécessaire? La corrélation inverse est également une relation assez forte . Voir ma réponse ci-dessous.
A QUIT - Anony-Mousse

Réponses:

2

Avez-vous essayé de mapper les valeurs à [0; 2]?

De nombreux algorithmes peuvent alors fonctionner.

Prenons par exemple Dijkstra: il nécessite des poids de bord non négatifs, mais si vous connaissez le minimum ades bords, vous pouvez l'exécuter x-aet obtenir le chemin sans cycle le plus court.

Mise à jour: pour les valeurs de corrélation, vous pouvez soit être intéressé par les valeurs absolues abs(x)(ce qui est la force de la corrélation!) , Soit vous pouvez fractionner temporairement le graphique en deux: d'abord regrouper uniquement les corrélations positives, puis les corrélations négatives uniquement si le signe est si important pour le clustering et que les approches précédentes ne fonctionnent pas.

A QUIT - Anony-Mousse
la source
C'est en quelque sorte ce que j'ai suggéré, il a dit qu'il "perdrait le sens de la corrélation". Qu'est ce que tu penses de ça?
eliasah
Avec sa description mise à jour, abs (x) peut fonctionner encore mieux.
A QUIT - Anony-Mousse
Néanmoins, je pense que [0,2] est plus représentatif. Les graphiques pondérés ont généralement une très grande importance sur ces questions pour calculer la centralité, la distance, le diamètre, etc.
Eliasah
1
Cela ne signifie pas que vous ne pouvez plus discriminer par la suite. L'avez-vous essayé , les résultats peuvent toujours être utiles?
A QUIT - Anony-Mousse
1
Essayez ensuite l'autre approche - trouver séparément les groupes positifs et négatifs.
A QUIT - Anony-Mousse
1

Oui, il existe un algorithme appelé «propagation d'affinité» qui fonctionne avec des poids négatifs; Je crois que cela est implémenté dans sklearn (voir la documentation ici ). Une référence pour ce qui se passe dans les coulisses peut être trouvée ici .

J'espère que c'est ce que vous cherchez!

squattyroo
la source
Je ne connaissais pas cet algorithme, il semble être une bonne solution. Je vais certainement l'essayer. Je vous remercie.
Ewybe du
Pour autant que je sache, le clustering de propagation d'affinité ne pourra pas simultanément considérer les corrélations positives et négatives tout en les séparant. D'ailleurs, je pense que la tâche est contradictoire.
micans
0

Il me semble que le problème que vous décrivez est connu sous le nom de problème de regroupement de corrélation . Ces informations devraient vous aider à trouver certaines implémentations, telles que:

Notez que certains algorithmes de détection de communauté ont également été modifiés afin de traiter les réseaux signés, par exemple Amelio'13 , Sharma'12 , Anchuri'12 , etc. Cependant, je n'ai trouvé aucune implémentation accessible au public.

Vincent Labatut
la source
0

Jetez un œil à ce code , il est assez évolutif, fonctionne avec des bords positifs et négatifs et résout le regroupement de corrélation (CC) comme un cas spécial (r = 0). Cependant, pour le cas du CC (maximisation des liens positifs et minimisation des liens négatifs à l'intérieur des grappes), je suggérerais d'autres méthodes spécialisées dans la résolution de cet objectif.

Pour illustrer, le clustering de corrélation (contrairement à ce que la littérature sur la détection communautaire poursuit) ne prend pas en compte la densité positive des clusters, donc quand un réseau n'a pas ou peu de liens négatifs (la plupart des cas réels), tout le réseau est mis en un seul grand grappe.

Esmailian
la source