Partitionieren eines Graphen in k ähnliche Untergraphen

Question

Ich habe eine Grafik, die verbunden ist und die Kanten haben Gewichte auf ihnen. Je geringer das Gewicht zwischen einer Kante ist, desto näher sind die benachbarten Ecken. Ich möchte den Graph in k kleinere Untergraphen so teilen, dass Knoten in allen Untergraphen sehr ähnlich sind.

Mit anderen Worten, ich muss den Graphen Cluster. Kann jemand Clustering-Algorithmen vorschlagen, die für Graphen geeignet sind und weniger Zeitkomplexität haben (kleiner als O (n^2))?

Answer 1

Clustering ist ein schwieriges Problem, das exaclty nur durch rohe Gewalt gelöst werden konnte. Bei effizienten Algorithmen müssen Sie sich also auf einen heuristischen Ansatz verlassen. Falls Sie Ihr Problem als Vertex-Clustering-Aufgabe lösen können, können Sie versuchen, etwas wie k-means, aber es könnte bei großen Datenmengen langsam sein.

Für Grafik speziell würde ich vorschlagen, MCL Algorithmus auf Ihr Problem zu verwenden. MCL scheint in vielen Fällen effizient zu sein. Es verwendet eine randomisierte Strömungssimulation, um Cluster in gewichteten/ungewichteten Graphen zu erkennen. Grundlegende Idee ist, dass sich der Fluss innerhalb eines Clusters sammelt, während Verbindungen zwischen Clustern weniger stark sind gesättigt.