Beispielanwendung in GraphLab
In dieser Lerneinheit wird die Abstraktion von GraphLab exemplarisch anhand des PageRank-Beispiels erläutert. Der PageRank-Algorithmus ist eine bekannte Technik, die von Google erfunden wurde, um die Wichtigkeit der von der Suchmaschine zurückgegebenen Websites einzustufen. Ausgehend von der Annahme, dass wichtigere Websites wahrscheinlich öfter auf anderen wichtigen Websites verlinkt werden, bestimmt der Algorithmus die Wichtigkeit einer Seite, indem er die Anzahl und Qualität der Links zählt, die auf diese Seite verweisen.
PageRank verfügt über verschiedene Implementierungen, sein Konzept lässt sich jedoch mithilfe der folgenden Gleichung veranschaulichen:
$$R[i] = 0.15 + \sum_{j \in Nbr(i)}{w_{ji}} \times R[j]$$
$R[i]$ steht für den PageRank-Wert der Seite $i$. $Nbr(i)$ ist die Menge von Seiten, die auf die Seite $i$ verweisen. Und $w_{ji}$ ist eine Gewichtung, die diesem Link zugeordnet und normalerweise als Kehrwert des Outdegrees der Seite $j$ definiert ist.
Wie Sie vielleicht bemerkt haben, ist die obige Gleichung rekursiv, sodass die PageRank-Werte verschiedener Seiten voneinander abhängig sein können. Daher beginnt der Berechnungsprozess von PageRank oft mit einer Menge von Anfangswerten, und jede Seite wendet die obige Gleichung iterativ an, um ihren Wert zu aktualisieren, bis eine Konvergenz erreicht ist.
Um diesen Algorithmus mit GraphLab auszuführen, wird das Problem zunächst als graphbasierte Abstraktion abgebildet. Bei PageRank sollte dies intuitiv erfolgen; die Scheitelpunkte des Graphen entsprechen den Seiten, und die Kanten entsprechen den Links zu den Seiten. Außerdem wird ein scheitelpunktbezogener Parameter hinzugefügt, d. h. der als $R[i]$ bezeichnete Rang der Seite. Nun, da die Daten in GraphLab dargestellt werden, wird die in der PageRank-Gleichung ausgedrückte Operation in die Schritte Gather, Apply und Scatter der GraphLab-Abstraktion zerlegt:
Algorithmus 3
PageRank $(i)$-Algorithmus in GraphLab, Ausführung für Seite $i$
- Funktion Gather $(j, i)$:
- $w_{ji} \times R[j]$ zurückgeben
- Funktion Sum $(a, b)$:
- $(a + b)$ zurückgeben
- Funktion Apply $(i, \Sigma)$:
- $R[i] = 0.15 + \Sigma$
- Funktion Scatter $(i, j)$:
- wenn $R[i]$ geändert wurde, die Neuberechnung von $j$ auslösen (zu aktivieren)
In der Gather-Phase durchläuft die Seite $i$ ihre einzelnen Eingangskanten und sammelt die entsprechenden Werte von ihren Nachbarn. Die gesammelten Werte werden mithilfe der Summenfunktion kumuliert, wobei einfach alle Eingangskantenwerte in diesem Algorithmus addiert werden. Anschließend führt die Seite $i$ die Apply-Funktion aus, um ihren PageRank-Wert in die Summe 0.15 und das aggregierte Ergebnis zu aktualisieren. Zuletzt wird geprüft, ob sich der aktualisierte PageRank vom vorherigen PageRank unterscheidet. Dabei wird jede Ausgangskante durchlaufen, um bei einer Änderung des PageRank-Werts die Neuberechnung ihrer Nachbarn auszulösen. PageRank führt die oben definierten GAS-Funktionen iterativ für alle aktiven Scheitelpunkte aus, bis sich die Werte nicht über einen bestimmten Schwellenwert hinaus ändern. Wenn keine weiteren aktiven Scheitelpunkte mehr vorhanden sind, wird der Algorithmus als auf das erforderliche Ergebnis konvergiert erachtet.