Przykładowa aplikacja w narzędziu GraphLab
W tej części analizujemy abstrakcję narzędzia GraphLab na przykładzie algorytmu PageRank. Algorytm PageRank jest dobrze znaną techniką proponowaną przez firmę Google służącą do określania rangi witryn internetowych zwracanych przez wyszukiwarkę. Zakładając, że do ważniejszych witryn internetowych może prowadzić więcej łączy z innych ważnych witryn internetowych, określa ważność strony przez liczenie i jakość łączy prowadzących do danej strony.
Algorytm PageRank ma różne implementacje, ale jego założenie można przedstawić za pomocą następującego równania:
$$R[i] = 0.15 + \sum_{j \in Nbr(i)}{w_{ji}} \times R[j]$$
$R[i]$ reprezentuje wartość PageRank strony $i$. $Nbr(i)$ jest zestawem stron wskazujących stronę $i$. $w_{ji}$ jest wagą skojarzoną z tym łączem, która jest zwykle definiowana jako odwrotność współczynnika łączy wychodzących strony $j$.
Jak można zauważyć, powyższe równanie jest cykliczne, dlatego wartości PageRank różnych stron mogą być wzajemnie zależne od siebie. Z tego względu proces obliczeniowy algorytmu PageRank często zaczyna się od zestawu wartości początkowych, a każda strona iteracyjnie stosuje powyższe równanie w celu aktualizacji jej wartości, aż do osiągnięcia zbieżności.
W celu wykonania tego algorytmu przy użyciu narzędzia GraphLab najpierw należy zamapować problem na abstrakcję opartą na grafie. W przypadku algorytmu PageRank powinno to być intuicyjne. Wierzchołki grafu odpowiadają stronom, a krawędzie odpowiadają łączom do stron. Dodajemy również parametr dla wierzchołka — rangę strony — oznaczony jako $R[i]$. Teraz, gdy dane mają reprezentację w narzędziu GraphLab, rozkładamy operację wyrażoną w równaniu PageRank na kroki zbierania, stosowania i rozpraszania w abstrakcji narzędzia GraphLab:
Algorytm 3
Algorytm PageRank $(i)$ w narzędziu GraphLab wykonywany dla strony $i$
- Zbierz funkcję $(j, i)$ :
- return $w_{ji} \times R[j]$
- Sum $(a, b)$ , funkcja:
- return $(a + b)$
- Zastosuj funkcję $(i, \Sigma)$ :
- $R[i] = 0.15 + \Sigma$
- Funkcja punktowa $(i, j)$ :
- jeśli wartość $R[i]$ została zmieniona, wyzwól ponowne obliczanie $j$ (uaktywnienie)
W fazie zbierania strona $i $ przechodzi przez poszczególne krawędzie i zbiera odpowiednie wartości z sąsiednich elementów. Zebrane wartości zostaną zagregowane przy użyciu funkcji sumowania, która po prostu dodaje wszystkie wartości w obrębie krawędzi w tym algorytmie. Następnie strona $i$ wykonuje funkcję stosowania w celu zaktualizowania wartości PageRank przy użyciu sumy 0,15 i zagregowanego wyniku. Na koniec sprawdza, czy zaktualizowana wartość PageRank różni się od poprzedniej i przechodzi przez każdą z krawędzi, aby wyzwolić ponowne obliczenie jej sąsiednich elementów, jeśli wartość PageRank uległa zmianie. Algorytm PageRank będzie iteracyjnie uruchamiać funkcje GAS zdefiniowane powyżej dla wszystkich aktywnych wierzchołków, aż wartości powyżej określonej wartości progowej nie ulegną zmianie. Gdy nie ma więcej aktywnych wierzchołków, algorytm jest uznawany za zbieżny z wymaganym wynikiem.