Key points are not available for this paper at this time.
Die Graphpartitionierung wird in vielen realen Anwendungen wie Betrugserkennung und Analyse sozialer Netzwerke weit verbreitet, um das verteilte Graphcomputing auf großen Graphen zu ermöglichen. Allerdings gelingt es bestehenden Arbeiten nicht, die Rechen- und Kommunikationskosten auf Maschinen mit unterschiedlicher Leistung (einschließlich Rechenkapazität, Netzwerkbandbreite und Speicherkapazität) auszubalancieren, da sie nur den Replikationsfaktor berücksichtigen und die Unterschiede der Maschinen in realistischen Rechenzentren vernachlässigen. In diesem Papier schlagen wir einen allgemeinen Graphpartitionierungsalgorithmus namens WindGP vor, der eine schnelle und qualitativ hochwertige Kantenpartitionierung auf heterogenen Maschinen unterstützen kann. WindGP entwirft neuartige Vorverarbeitungstechniken, um die Metrik zu vereinfachen und die Rechenkosten entsprechend den Eigenschaften der Graphen und Maschinen auszugleichen. Außerdem wird ein Best-First-Suchalgorithmus anstelle von BFS und DFS vorgeschlagen, um Cluster mit hoher Kohäsion zu erzeugen. Darüber hinaus passt WindGP die Partitionsergebnisse durch anspruchsvolle lokale Suchmethoden adaptiv an. Umfangreiche Experimente zeigen, dass WindGP alle gängigen Partitionierungsmethoden um das 1,35- bis 27-fache übertrifft, sowohl bei dichten als auch bei spärlichen verteilten Graphalgorithmen, und eine gute Skalierbarkeit hinsichtlich der Graphgröße und der Maschinenanzahl aufweist.
Zeng et al. (Fr,) haben diese Frage untersucht.