我理解 pagerank 背后的想法并实现了它(在阅读“编程集体智慧”一书时)。
但我读到它可以分布在多个服务器上(我猜谷歌正在这样做)。我有点困惑,因为根据我的理解,您需要整个图表才能对其进行页面排名,因为每个排名都与其他排名相关。
我找到了wiki 文章,但没有解释太多。
关于这怎么可能的任何建议?此外,还有一个额外的问题:进行分布式 pagerank 的技术是 pagerank 独有的,还是可以将所使用的方法应用于应用于图形的其他机器学习算法?
我理解 pagerank 背后的想法并实现了它(在阅读“编程集体智慧”一书时)。
但我读到它可以分布在多个服务器上(我猜谷歌正在这样做)。我有点困惑,因为根据我的理解,您需要整个图表才能对其进行页面排名,因为每个排名都与其他排名相关。
我找到了wiki 文章,但没有解释太多。
关于这怎么可能的任何建议?此外,还有一个额外的问题:进行分布式 pagerank 的技术是 pagerank 独有的,还是可以将所使用的方法应用于应用于图形的其他机器学习算法?
计算 PageRank 的最先进方法是使用 Google Pregel 框架。我很确定他们现在有更复杂的东西,但这是最新发布的成果。
您可以在研究博客中阅读有关它的更多详细信息。或者在这里阅读已发表的论文。
我正在开发一个名为Apache Hama的Bulk Synchronous Parallel范例的开源版本。还有Apache Giraph,它只专注于图形用例和许多其他用例。
就像 mfrankli 提到的,还有 MapReduce 框架(例如 Apache Hadoop)可以用来计算 PageRank,但它对于迭代算法效率不高。
值得注意的是,这两种解决方案(MapReduce 和 BSP)都是批处理解决方案,因此它们可用于重新计算整个 webgraph 的 PageRank。由于 Google 更新比批处理算法快得多,因此您可以预期它们会频繁地重新计算子图上的 PageRank。
让
| 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 从这里开始。映射器的序列化输入将类似于
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 输出将按 key 分组并由 reducer 获取。如果我们有 5 个减速器,它会是这样的:
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 作业中,reducers 将像 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 >
重复 reduce 工作,直到它足够收敛或您满意为止。
MapReduce提供了一些有趣的背景,并且可能会弄清楚您将如何并行化此任务。