algorithm - 使用 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 时，reducer 将如何知道每个页面的传出链接数。这是否需要在某些外部数据源中查找？

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 中你应该输出外链而不是内链，正如 intenret 上的一些文章所建议的那样。这样连续的迭代也将有外链作为映射器的输入。

请注意，来自同一页面的具有相同地址的多个外链算作一个。另外，不要计算循环(链接到自身的页面)。

阻尼系数通常为 0.85，但您也可以使用其他值。