使用MapReduce实现PageRank

Question

我正在尝试理解使用MapReduce实现PageRank的一个问题。

我有以下简单场景，三个节点：A、B、C。

邻接矩阵如下：

A { B, C }
B { A }

例如，B的PageRank等于：

(1-d)/N + d ( PR(A) / C(A) ) 

N     = number of incoming links to B
PR(A) = PageRank of incoming link A
C(A)  = number of outgoing links from page A

我对所有原理图以及映射器和减少器的工作方式都很满意，但我无法理解在减少器计算时，如何知道C（A）的值。 当减少器通过聚合链接到B的传入链接来计算B的PageRank时，如何知道每个页面的发出链接数量。 是否需要在某些外部数据源中查找？

- Nick D.

---

可能会在以下网站上获得更好的答案：http://cstheory.stackexchange.com/ - Orbling

Answer 1

这里是伪代码：

map( key: [url, pagerank], value: outlink_list )
    for each outlink in outlink_list
        emit( key: outlink, value: pagerank/size(outlink_list) )

    emit( key: url, value: outlink_list )

reducer( key: url, value: list_pr_or_urls )
    outlink_list = []
    pagerank = 0

    for each pr_or_urls in list_pr_or_urls
        if is_list( pr_or_urls )
            outlink_list = pr_or_urls
        else
            pagerank += pr_or_urls

    pagerank = 1 - DAMPING_FACTOR + ( DAMPING_FACTOR * pagerank )

    emit( key: [url, pagerank], value: outlink_list )

在reduce中，重要的是输出外链而不是内链，正如互联网上的一些文章所建议的那样。这样连续的迭代也将外部链接作为mapper的输入。

请注意，同一页中具有相同地址的多个外部链接只计算为一个。另外，不要计算循环链接（页面链接到自身）。

阻尼系数传统上为0.85，尽管您也可以尝试其他值。

- gphilip

Answer 2

我们迭代地评估PR。PR(x) = Sum(PR(a)*weight(a), a在in_links中) by

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)

所以输出等于输入，我们可以一直这样做直到覆盖。

- yura

---

这里描述的算法是有缺陷的。Webgraph 是一个有向图，因此初始 PageRank 只会流向一个方向（到外部链接）。在 reducer 中，您输出页面的入链并在下一次迭代中使用它。这使得 PR “回流”。请注意，初始算法还计算阻尼因子，这对于正确建模“随机浏览”非常重要。 - gphilip