Wie werden die Gewichte effizient gemäß der Adjazenzmatrix aktualisiert?

Question

Ich habe eine sehr große Grafik. wo gibt es Verbindungen zwischen den Knoten. Jede Kante hat anfänglich Gewicht 1. Ich muss die Gewichte der Kanten gemäß der transformierten Adjazenzmatrix aktualisieren.

Wo A Adjcency Matrix. Das neue Gewicht in den Knoten (i, j) wird durch M (i, j) gegeben.

Ich muss dies in Graphx tun. Wie gehe ich dazu?

Mein Ansatz: Finden Sie alle benachbarten Knoten für jeden Knoten und die innere Join them.in Paar. Aktualisieren Sie dann die Gewichtungen jedes Knotens.

Aber ich bin etwas verwirrt darüber, effizienten Code in Graphx zu schreiben. Wie gehe ich weiter? Snaps von Code wird geschätzt.

Answer 1

Ein Beispiel für die effiziente Verarbeitung von dünn besetzten Matrizen mit GraphX ​​finden Sie im Quellcode für die Implementierung von SVD ++ in GraphX.

https://github.com/apache/spark/blob/branch-1.6/graphx/src/main/scala/org/apache/spark/graphx/lib/SVDPlusPlus.scala

Grundsätzlich verwendet es nur aggregateMessages(), und so eine Nachricht pro Nicht-Null-Eintrag in der Adjazenzmatrix wird zu dem benachbarten Scheitelpunkt gesendet - dadurch vermeidet auch unter Berücksichtigung (Verarbeitung) die nullwertigen Einträge der Adjazenzmatrix.

EDIT (weitere Informationen):

Zuerst müssen Sie planen, was an jedem Eckpunkt gespeichert werden wird, und auch, wie du gehst, um diese Informationen zu sammeln M (i, j) in produzieren das Ende. Beachten Sie, dass die beiden Normen im Nenner, | A (:, i) | und | A (:, j) | werden wiederholt verwendet. Wenn im Graphen n Knoten vorhanden sind (dh, wenn A eine nxn-Matrix ist), dann gibt es nur n | A (:, i) | 's, obwohl es n M (i, j)' gibt. s berechnet werden.

Ein guter Plan wäre, dass jeder Eckpunkt i zwei Vektoren speichert (z.B. in einem Tuple2 von zwei Array [Double] s): | A (:, i) | und [, ...,] (nenne das eine Vi). Dann würden Sie am Ende M berechnen, indem Sie diese Information aus Ihrem graph.vertices() extrahieren und kombinieren, um M zu erzeugen.

| A (:, i) | ist einfach. Für jeden Scheitelpunkt i ist das nur die Anzahl der eingehenden Kanten. (Denken Sie darüber nach, was es bedeutet, dass A eine Adjazenzmatrix ist und ein Diagramm zeichnet.)

Vi ist etwas kniffliger, aber nicht übermäßig. Zuerst müssen wir für jeden Eckpunkt einen Vektor und nicht nur eine einzelne Zahl wie für | A (:, i) | Und jede Komponente dieses Vektors der Länge n wird bis zu potentiell n Eingaben benötigen.

Wenn wir zurück zu der Bedeutung hinter der Adjazenzmatrix gehen, um die jte Komponente von Vi zu berechnen (was wäre, das ist eine Summe von n Produkten), brauchen wir nur eine 1 hinzuzufügen, wenn ein Knoten k eine Kante hat sowohl ich als auch j. Daher können Sie aggregateMessages zweimal hintereinander verwenden, um benachbarte Scheitelpunkte entlang von Kanten rückwärts zu übertragen. Um eine wirklich lose Terminologie zu verwenden: zuerst von den j-Scheitelpunkten zu den k-Scheitelpunkten und dann von den k-Scheitelpunkten zu den i-Scheitelpunkten. Auf diese Weise kennt jeder Eckpunkt alle seine Nachbarn innerhalb von zwei Hops (und es ist OK für jeden Eckpunkt, so viele Informationen zu akkumulieren, wenn A spärlich ist). Auf diese Weise können Sie Vi berechnen.