我正在尝试解决使用 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 将如何知道每个页面的传出链接数量。这是否需要在某些外部数据源中查找?
这是一个伪代码:
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上的一些文章所建议的那样。这样,连续迭代也将具有外链接作为映射器的输入。
请注意,同一页面中具有相同地址的多个外链计为 1。另外,不要计算循环(链接到自身的页面)。
阻尼系数传统上为 0.85,但您也可以使用其他值。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)