如何分布式计算PageRank？

Question

我理解PageRank的概念，并已经实现过它（阅读了《编程集体智慧》一书）。

但是我读到它可以分布在多台服务器上（我猜Google正在这样做）。 我有点困惑，因为据我所知，你需要整个图才能对其进行PageRank，因为每个排名都是相对于其他排名的。

我找到了维基百科文章，但它并没有解释得很清楚。

有什么方法可以实现这个？ 还有，额外的问题：分布式PageRank的技术是否只适用于PageRank，还是可以应用于应用于图上其他机器学习算法的方法？

- Lostsoul

Answer 1

计算PageRank的最先进方法是使用Google Pregel框架。我相信他们现在有更复杂的东西，但那是最新发布的努力。

您可以在研究博客中阅读更多详细信息。 或者在这里阅读已发布的论文。

我正在开发一个名为Apache Hama的开源版本的批量同步并行范例。还有Apache Giraph专注于图形用例和许多其他用途。

正如mfrankli提到的那样，还有MapReduce框架（例如Apache Hadoop）可用于计算PageRank，但对于迭代算法来说效率不高。

值得注意的是，MapReduce和BSP都是批处理解决方案，因此它们可用于重新计算完整Web图的PageRank。由于Google更新比批处理算法快得多，因此您可以预期它们经常在子图上重新计算PageRank。

- Thomas Jungblut

Answer 2

Let

| 0 0 0 1 0 |
| 0 0 0 1 0 |
| 0 0 0 1 1 |
| 1 1 1 0 0 |
| 0 0 1 0 0 |

假设有一个邻接矩阵（或图）。然后在PageRank中，转移矩阵M将会是：

| 0 0   0 1/3 0 |
| 0 0   0 1/3 0 |
| 0 0   0 1/3 1 |
| 1 1 1/2   0 0 |
| 0 0 1/2   0 0 |

这段文字是关于编程的，需要翻译成中文。内容是：该矩阵是列随机、不可约和非周期性的。MapReduce从这里开始。Mapper的序列化输入将会是这样的。

1 -> 4
2 -> 4
3 -> 4 , 5
4 -> 1 , 2 , 3
5 -> 3

"并且映射器将会发出以下内容："

< 1 , [4] >
< 4 , 1 >

< 2 , [4] >
< 4 , 1 >

< 3 , [4 , 5] >
< 4 , 1/2 >
< 5 , 1/2 >

< 4 , [1, 2, 3] >
< 1 , 1/3 >
< 2 , 1/3 >
< 3 , 1/3 >

< 5 , [3] >
< 3 , 1 >

Mapper的输出将按键分组并由reducer获取。如果我们有5个reducers，它会像这样：

R1 takes [4]       , 1/3           then computes 1/5*(1/3)           =  2/30
R2 takes [4]       , 1/3           then computes 1/5*(1/3)           =  2/30
R3 takes [4, 5]    , 1/3 , 1       then computes 1/5*(1/3 + 1)       =  8/30
R4 takes [1, 2, 3] ,   1 , 1 , 1/2 then computes 1/5*(  1 + 1 + 1/2) = 15/30
R5 takes [3]       , 1/2           then computes 1/5*(1/2)           =  3/30

现在第一次（幂）迭代已经结束。在接下来的reduce作业中，reducer将会像mapper一样发出信号，但是计算出的PR将会被用来代替1:

< 1 , [4] >
< 4 , 2/30 >

< 2 , [4] >
< 4 , 2/30 >

< 3 , [4 , 5] >
< 4 , 4/30 >
< 5 , 4/30 >

< 4 , [1, 2, 3] >
< 1 , 5/30 >
< 2 , 5/30 >
< 3 , 5/30 >

< 5 , [3] >
< 3 , 3/30 >

重复执行减少工作，直到它足够收敛或者您满意为止。

- ghchoi

Answer 3

MapReduce提供了一些有趣的背景知识，可能会让你清楚如何并行化这个任务。

- mfsiega

---

Mapreduce计算PageRank效率过低。 - Thomas Jungblut

《使用MapReduce进行数据密集型文本处理》（http://lintool.github.com/MapReduceAlgorithms/index.html）包含许多MapReduce算法，包括PageRank。正如其他人所提到的，MapReduce不是PageRank的有效实现方式。这篇论文（http://arxiv.org/abs/1203.2081）比较了MapReduce和BSP。 - Praveen Sripati