Graph-Clustering-Algorithmen, die negative Gewichte berücksichtigen

8

Ich habe eine Diagramminstanz mit gewichteten gerichteten Kanten, deren Werte im Bereich [-1,1] liegen können. Ich muss Clustering in diesem Diagramm durchführen, um Gruppen herauszufinden, in denen Eckpunkte stärker korreliert sind.

Ich habe nach mehreren Algorithmen gesucht, die auf Clustering oder Community-Erkennungsgraphen basieren, aber die meisten funktionieren aufgrund der negativen Gewichte nicht. Bis jetzt habe ich Spinglass angewendet (es wird in der Igraph- Bibliothek so genannt , es ist ein Algorithmus, der auf dem Potts-Modell basiert), der sowohl mit positiven als auch mit negativen Gewichten zu funktionieren scheint.

Gibt es andere Algorithmen für das Clustering oder die Community-Erkennung von Diagrammen mit negativen und positiven Kantengewichten?

Update: Die Kantengewichte stellen Korrelationen dar. 1 bedeutet, dass zwei Eckpunkte stark korreliert sind, -1, die umgekehrt korreliert sind, und 0 bedeutet, dass sie unabhängig sind.

correlation clustering graph-theory networks igraph Ewybe
quelle
Was bedeuten die Gewichte?
Eliasah
@eliasah Ich habe ein Update gemacht, um das zu erklären
Ewybe
Haben Sie versucht, eine andere Waage zu verwenden? Dies könnte eine gute Lösung sein, wenn eine reguläre Clustering-Methode verwendet wird, die auf dem Algorithmus für die Zentralität zwischen zwei Beispielen basiert.
Eliasah
@eliasah Das Skalieren dieser Daten kann nicht so einfach sein, weil ich daran interessiert bin, die Bedeutung der Korrelation
beizubehalten
1
Wird für das Clustering das Vorzeichen der Korrelation wirklich benötigt? Inverse Korrelation ist auch eine ziemlich starke Beziehung. Siehe meine Antwort unten.
Hat aufgehört - Anony-Mousse

Antworten:

2

Haben Sie versucht, die Werte auf [0; 2] abzubilden?

Dann können viele Algorithmen funktionieren.

Betrachten Sie zB Dijkstra: Es erfordert nicht negative Kantengewichte, aber wenn Sie das Minimum ader Kanten kennen, können Sie es ausführen x-aund den kürzesten zyklusfreien Pfad erhalten.

Update: Bei Korrelationswerten sind Sie möglicherweise entweder an den absoluten Werten interessiert abs(x)(was die Stärke der Korrelation ist!) Oder Sie möchten den Graphen vorübergehend in zwei Teile aufteilen: zuerst nur die positiven Korrelationen, dann die negativen Korrelationen Nur wenn das Vorzeichen für das Clustering so wichtig ist und die vorherigen Ansätze nicht funktionieren.

Hat aufgehört - Anony-Mousse
quelle
Das habe ich irgendwie vorgeschlagen, er sagte, dass er "die Bedeutung der Korrelation verlieren wird". Was denkst du darüber?
Eliasah
Mit seiner aktualisierten Beschreibung funktioniert abs (x) möglicherweise noch besser.
Hat aufgehört - Anony-Mousse
Trotzdem halte ich [0,2] für repräsentativer. Gewichtete Graphen haben normalerweise eine sehr große Bedeutung in diesen Angelegenheiten, um Zentralität, Entfernung, Durchmesser usw. zu berechnen
eliasah
1
Das bedeutet nicht, dass Sie danach nicht diskriminieren können. Haben Sie es versucht , können die Ergebnisse noch nützlich sein?
Hat aufgehört - Anony-Mousse
1
Versuchen Sie dann den anderen Ansatz - positive und negative Cluster getrennt zu finden.
Hat aufgehört - Anony-Mousse
1

Ja, es gibt einen Algorithmus namens "Affinity Propagation", der mit negativen Gewichten arbeitet. Ich glaube, dass dies in sklearn implementiert ist (siehe die Dokumentation hier ). Eine Referenz für das, was sich hinter den Kulissen abspielt, finden Sie hier .

Hoffe das ist was du suchst!

Squattyroo
quelle
Ich kannte diesen Algorithmus nicht, er scheint eine gute Lösung zu sein. Ich werde es auf jeden Fall versuchen. Vielen Dank.
Ewybe
Soweit ich weiß, kann das Affinity Propagation Clustering nicht gleichzeitig positive und negative Korrelationen berücksichtigen und diese auch trennen. Im Übrigen halte ich die Aufgabe für widersprüchlich.
Micans
0

Mir scheint, das von Ihnen beschriebene Problem ist als Korrelationsclustering-Problem bekannt . Diese Informationen sollen Ihnen bei der Suche nach Implementierungen helfen, z.

Beachten Sie, dass einige Community-Erkennungsalgorithmen ebenfalls geändert wurden, um signierte Netzwerke zu verarbeiten, z. B. Amelio'13 , Sharma'12 , Anchuri'12 usw. Ich konnte jedoch keine öffentlich verfügbare Implementierung finden.

Vincent Labatut
quelle
0

Schauen Sie sich diesen Code an , er ist ziemlich skalierbar, arbeitet mit positiven und negativen Flanken und löst das Korrelationsclustering (CC) als Sonderfall (r = 0). Für den Fall von CC (Maximieren positiver Verbindungen und Minimieren negativer Verbindungen innerhalb von Clustern) würde ich jedoch andere Methoden vorschlagen, die auf die Lösung dieses Ziels spezialisiert sind.

Zur Veranschaulichung berücksichtigt das Korrelationsclustering (anders als in der Community Detection-Literatur) nicht die positive Dichte von Clustern. Wenn also ein Netzwerk keine oder nur wenige negative Bindungen aufweist (die meisten Fälle in der realen Welt), wird das gesamte Netzwerk in einem großen Netzwerk zusammengefasst Cluster.

Esmailian
quelle