Effizienter Graph Clustering Algorithmus

20

Ich bin auf der Suche nach einem effizienten Algorithmus zum Auffinden von Clustern in einem großen Graphen (mit ca. 5000 Scheitelpunkten und 10000 Kanten).

Bisher verwende ich den Girvan-Newman-Algorithmus, der in der JUNG-Java-Bibliothek implementiert ist, aber es ist ziemlich langsam, wenn ich versuche, viele Kanten zu entfernen.

Können Sie mir eine bessere Alternative für große Diagramme vorschlagen?

mariosangiorgio
quelle
Hast du dir k-means angesehen?
Oded
Können Sie mir bitte einen Hinweis geben, um zu erfahren, wie man es in einem Diagramm verwendet?
mariosangiorgio
Ich bin auf die JUNG-Implementierung des VoltageClusterer umgestiegen und es ist definitiv schnell. jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/…
mariosangiorgio
1
Ist dies nicht besser für < cs.stackexchange.com > geeignet, da es sich eher um Informatik als um Softwareentwickler handelt?
Oeufcoque Penteano

Antworten:

13

Ich persönlich schlage Markov-Clustering vor . Ich habe es in der Vergangenheit mehrere Male mit guten Ergebnissen verwendet.

Die Affinitätsausbreitung ist eine weitere praktikable Option, die jedoch weniger konsistent zu sein scheint als die Markov-Clusterbildung.

Es gibt verschiedene andere Optionen, aber diese beiden sind sofort einsatzbereit und eignen sich gut für das spezifische Problem des Clustering von Diagrammen (die Sie als spärliche Matrizen anzeigen können). Die Distanzmessung, die Sie verwenden, spielt ebenfalls eine Rolle. Ihr Leben wird einfacher, wenn Sie eine geeignete Metrik verwenden.

Ich habe dieses Papier auf der Suche nach Leistungsbenchmarks gefunden. Es ist eine gute Übersicht über das Thema.

Nathan Rice
quelle
Danke, ich werde mir alle von Ihnen vorgeschlagenen Algorithmen ansehen.
mariosangiorgio
Korrektur: Diese Algorithmen benötigen als Eingabegewichte Ähnlichkeit, nicht Abstand. Die metrische Eigenschaft (Dreieck-Ungleichung) wird nicht berücksichtigt. Es kann nützlich sein, Gewichte so zu transformieren, dass sie in einen natürlichen Bereich fallen, z. B. für (Pearson) -Korrelationen wie hier beschrieben ( micans.org/mcl/man/clmprotocols.html#array ) und für BLAST E-Werte wie hier beschrieben ( micans.org/mcl/man/clmprotocols.html#blast ).
Micans
10

Hierarchisches Clustering

Dies wurde mir von einem Freund empfohlen. Laut Wikipedia :

Bei dieser Methode wird ein Ähnlichkeitsmaß definiert, das einen (normalerweise topologischen) Ähnlichkeitstyp zwischen Knotenpaaren quantifiziert. Häufig verwendete Kennzahlen sind die Kosinusähnlichkeit, der Jaccard-Index und der Hamming-Abstand zwischen den Zeilen der Adjazenzmatrix. Dann gruppiert man nach dieser Maßnahme ähnliche Knoten in Communities. Für die Durchführung der Gruppierung gibt es mehrere gängige Schemata. Die zwei einfachsten sind Einzelverbindungsclustering, bei dem zwei Gruppen dann und nur dann als separate Communitys betrachtet werden, wenn alle Knotenpaare in verschiedenen Gruppen eine Ähnlichkeit aufweisen, die unter einem bestimmten Schwellenwert liegt, und eine vollständige Verbindungsclusterung , bei dem alle Knoten in jeder Gruppe Ähnlichkeiten aufweisen, die größer als der Schwellenwert sind.

Markov Cluster

Dies ist, was ich in Ihrer Situation benutze. Es ist ein sehr nützlicher Algorithmus. Ich habe einen Link zu einem PDF über den Algorithmus gefunden. Es ist ein großartiger Algorithmus und mangels eines besseren Ausdrucks extrem "leistungsfähig". Probieren Sie es aus und sehen Sie.

Dynamisch
quelle
5

Ich denke, dass Sie für Ihr Problem hier eine Möglichkeit finden sollten, Scheitelpunktkanten auf einen Satz von Koordinaten für jeden Scheitelpunkt abzubilden. Ich bin mir nicht sicher, ob es einen besseren Weg gibt. Aber ich denke, Sie könnten damit beginnen, jeden Scheitelpunkt als Dimension darzustellen, und dann würde der Kantenwert für einen bestimmten Scheitelpunkt zu dem Wert, mit dem Sie für diese bestimmte Dimension arbeiten müssen. Danach können Sie eine einfache Euklid-Distanz machen und damit arbeiten.

viki.omega9
quelle
1
Nachdem ich ein bisschen nachgelesen hatte, fand ich das hier und ich denke, Sie sollten es sich ansehen.
viki.omega9