使用MapReduce实现PageRank

我试图让我的脑海里围绕一个与MapReduce实现PageRank的理论有关的问题。使用MapReduce实现PageRank

我有三个节点下面的简单情形：AB 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

我很满意所有的原理图以及mapper和reducer是如何工作的，但我不知道C（A）在计算时如何知道C（A）。在通过将传入链接聚合到B来计算B的PageRank时，缩减器将如何知道每个页面的传出链接的数量。这是否需要在某些外部数据源中查找？

来源

2011-02-17 Nick D.

可能可以得到更好的答案：http://cstheory.stackexchange.com/ – Orbling 2011-02-17 13:18:30

我们迭代评估PR。 PR（X）= SUM（PR（A）×体重（a）所示，在in_links）由

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)

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

来源

2011-02-17 13:50:33 yura

这里描述的算法是有缺陷的。 Webgraph是一个有向图，所以最初的PageRanks只能朝着一个方向（到outlinks）。在reducer中，您可以将链接输出到页面，并在下一次迭代中使用它。这使得PR“回流”。请注意，初始算法还会使用阻尼因子进行计算，这对正确建模“随机浏览”非常重要。 – gphilip 2012-11-26 14:58:39

A detailed explanation with Python code，Michael Nielsen。

来源

2011-02-17 23:21:41

下面是一个伪代码：

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)

重要的是，在降低你应该输出对外连结，而不是反向链接，如在intenret一些文章建议。这样连续的迭代也将有outlinks作为映射器的输入。

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

阻尼系数传统上是0.85，但您也可以使用其他值。

来源

2012-11-26 15:49:17 gphilip

使用MapReduce实现PageRank

回答

相关问题