使用mapreduce计算pagerank时如何迭代

Question

当我尝试使用 mapreduce 实现 PageRank 时，我遇到了一些问题。 我想引用这里的代码https://stackoverflow.com/a/5029780/1117436来描述问题。

map ((url,PR), out_links) //PR = random at start
for link in out_links
  emit(link, ((PR/size(out_links)), url))

reduce(url, List[(weight, url)):
   PR =0
   for v in weights
   PR = PR + v
   Set urls = all urls from list

 emit((url, PR), urls)

在上面的过程中，很明显map过程的输入的第二个参数是url的Out链接，但是reduce过程的输出的第二个参数似乎是url的In链接。那么这些代码如何迭代工作呢？

那么我想问的是如何编写代码才能使pagerank算法正常工作？

更新：我认为这个答案解决了我的问题。 https://stackoverflow.com/a/13568286/1117436

Answer 1

您可以使用 MapReduce 实现迭代算法，但这可能不是最好、更有效的方法（因为每次迭代都会将内容移动到 HDFS/磁盘）。

话虽如此，如果您有兴趣了解如何使用 MapReduce 实现 PageRank 等功能，请查看此处：

• https://github.com/castagna/mr-pagerank/

从PageRank.java

如果你有兴趣，你可以看看一堆旧的（即2009）幻灯片在这里：

• https://github。 com/castagna/mr-pagerank/blob/master/docs/pagerank-huguk-2009.pdf

现在，您可以通过 Pregel 克隆实现/运行 PageRank 获得更多乐趣例如 Praveen 已经向您建议的 Apache Giraph。

Answer 2

已经有几个图形处理框架。

查看可用于图形处理的 Apache Giraph。 Giraph 基于 MR。 GoldenOrb 正处于非常早期的阶段。另外，请查看 Apache Hama，它是 BSP，它有自己的计算引擎，不是基于 MR 的，而是使用 HDFS 进行存储。 Hama 还可以用于进行图形处理。