pagerank如何以分佈式方式計算？

Question

我瞭解pagerank背後的想法並已實施（閱讀「編程集體智慧」一書時）。

但我看過它可以分佈在多個服務器上（因爲我猜Google是這樣做的）。我有點困惑，因爲根據我的理解，你需要整個圖表才能進行頁面排名，因爲每個排名都與其他排名相關。

我發現了wiki article但它沒有解釋太多。

有關這可能性的任何建議？另外，獎金問題：做pagerank專有的分佈式pagerank的技術還是可以應用於應用於圖形的其他機器學習算法的方法？

Answer 1

最先進的PageRank計算方法是使用Google Pregel框架。我很確定他們現在有更復雜的東西，但這是最新發布的成果。

您可以在research blog中查看關於它的更多詳細信息。 或閱讀已發表論文here。

我正在開發一個名爲Apache Hama的Bulk Synchronous Parallel範例的開源版本。還有Apache Giraph，它只關注圖形用例和其他許多圖形用例。

像mfrankli提到的一樣，還有MapReduce框架（例如Apache Hadoop），可以用來計算PageRank，但對迭代算法來說效率不高。

值得注意的是，這兩種解決方案（MapReduce和BSP）都是批處理解決方案，所以它們可以用來重新計算完整web圖的PageRank。由於Google更新比批量算法快得多，因此您可以期望他們經常重新計算子圖的PageRank。

Answer 2

MapReduce提供了一些有趣的背景，並可能會清楚你將如何並行化這項任務。