使用MapReduce实现PageRank

Question

我正试图解决使用MapReduce实现PageRank的理论问题.

我有以下三个节点的简单场景:AB C.

邻接矩阵在这里:

A { B, C }
B { A }

例如,PageRank for B等于:

(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 )

重要的是,在减少中你应该输出外链而不是链接,正如一些关于内容的文章所暗示的那样.这样,连续迭代也将具有作为映射器输入的外链.

请注意,同一页面中具有相同地址的多个外链都计为一个.此外,不要计算循环(链接到自身的页面).

阻尼系数传统上为0.85,尽管你也可以使用其他值.

Answer 2

我们迭代地评估 PR。PR(x) = Sum(PR(a)*weight(a), in_links 中的 a) 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)

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