Spark: Was ist die zeitliche Komplexität des in GraphX ​​verwendeten Algorithmus für verbundene Komponenten?

Question

GraphX ​​kommt mit einem algorithm for finding connected components eines Graphen.

Ich habe keine Aussage über die Komplexität ihrer Implementierung gefunden.

Im Allgemeinen kann das Auffinden verbundener Komponenten in linearer Zeit durchgeführt werden, z. B. durch eine Breitensuche oder Tiefensuche (siehe Wikipedia article). Dies setzt jedoch voraus, dass Sie den Graphen im Speicher behalten können. GraphX ​​implementiert einen verteilten Out-of-Core-Algorithmus, daher nehme ich an, dass es nicht vergleichbar ist.

Wissen Sie, wie ihr Algorithmus funktioniert und welche Komplexität vorliegt?

Answer 1

Ich behaupte, dass das primäre Ziel eines Graphen gegenüber einer Nicht-Graph-Lösung ist, die Anzahl der sequentiellen Schritte zu reduzieren, die zur Lösung des Problems erforderlich sind. Dies ist anders als die Komplexität - tatsächlich kann eine Graph-Lösung mehr CPU-Befehle insgesamt ausführen und dennoch die richtige Lösung sein, wenn sie die Anzahl der sequentiellen Schritte reduziert. In Bezug auf das Auffinden verbundener Komponenten weisen sowohl die Breiten- als auch die Tiefennäher-Ansätze dieselbe Anzahl von aufeinanderfolgenden Schritten auf - d. H. Einige Vielfache der Anzahl von Eckpunkten in dem Graphen. Dieselbe Logik muss sequentiell auf jeden Knoten angewendet werden. Das ist die ganze Lösung.

Auch wenn Ihr Diagramm zwei mehr oder weniger gleich große Cluster enthält, können Sie die Arbeit nicht in zwei Worker aufteilen und an einem Ende beginnen und sich in der Mitte treffen. Du weißt nicht, wo die Enden sind. Du weißt nicht, wo die Mitte ist.

Wenn Sie wissen, was Sie wissen, kommt heraus, Ihre Gesamtzahl der sequentiellen Schritte könnte auf die Hälfte reduziert werden. Wenn es hilft, können Sie darüber nachdenken, was das Beste ist, was Sie in Bezug auf sequenzielle Schritte tun können. Und es hängt vollständig von der Form Ihres Graphen ab.

Wenn Sie viele diskrete Cluster haben, die nicht angegliedert sind und kein Cluster größer als 10 Personen ist, dann ist das theoretisch Beste, was Sie tun können, 10 sequenzielle Schritte. Egal wie viel parallele Rechenleistung Sie hatten, das Beste, was Sie tun können, sind 10 sequentielle Schritte.

Ein Graphalgorithmus bringt Sie nicht nur näher an das theoretische Minimum heran - abhängig von der Form Ihrer Cluster schlägt es tatsächlich.

Wie funktioniert der Spark-Algorithmus? Es ist ziemlich einfach - jeder Knoten sendet nur seine VertexId an seine Nachbarn, und seine Nachbarn tun das gleiche. Jeder Knoten, der eine VertexId niedrigere als seine eigenen empfängt, sendet die nächste Runde; wenn nicht, wird der Vertex still.

Wenn Sie einen Cluster haben, in dem jeder der Eckpunkte mit jedem anderen Eckpunkt verbunden ist, dann weiß jeder nach einer Runde von Nachrichten, wer die niedrigste VertexID ist, und alle werden in der nächsten Runde still. Ein sequentieller Schritt, der gesamte Cluster.

Wenn andererseits jeder Scheitelpunkt im Cluster nur mit höchstens 2 anderen Scheitelpunkten verbunden ist, könnte es N sequenzielle Schritte dauern, bevor alle Scheitelpunkte wissen, wer das Minimum VertexID ist.

Offensichtlich sind die sequenziellen Schritte im Diagrammalgorithmus von unterschiedlicher Art und sogar von Diagramm zu Diagramm unterschiedlich. Ein gut verbundenes Diagramm erzeugt viele Nachrichten und verbraucht mehr Zeit, um sie zusammenzuführen usw. Aber es werden nicht so viele sequenzielle Schritte wie bei einem weniger gut verbundenen Graphen benötigt.

Lange Rede, kurzer Sinn, die Leistung der Graphenlösung hängt vollständig von der Form des Graphen ab, aber sie sollte viel, viel besser parallelisieren als eine Breiten- oder Tiefenlösung.