MapReduce实现的PageRank原理

PageRank手工计算得出的值见帖子 http://f.dataguru.cn/thread-17158-1-1.html 这个值有助于我们验证下面MR计算是不是正确
首先假设有两个节点A和B 原始矩阵如tiger老师的幻灯片第九页 a=1
网页1和2保存在节点A上 网页3和4保存在节点B上
由于A在A上很容易计算1和2的出链 根据MR的本地运算的思想，网页1和2的处理必在A上完成，B也同理
那么我们可以设计Map函数，这个函数的作用有两：1、得到源矩阵 2、用源矩阵乘以列向量
得到在A上需要计算的源矩阵：
0 0
1/3 0
1/3 1/2
1/3 1/2
同理在B节点上要计算的源矩阵：
0 0
0 1
0 0
1 0
基于矩阵的乘法规则 我们假设一个列向量q00={{1},{1}} q10={{1},{1}}
把q0和q1分别发送到节点A和节点B上 然后进行计算 我们姑且把计算出来的向量叫做qa和qb：
在A上：
0*1+0*1 0
1/3*1+0*1 1/3
qa= 1/3*1+1/2*1 = 5/6
1/3*1+1/2*1 5/6


在节点B上：
0*0+0*1 0
0*1+1*1 1
qb=0*1+0*1 = 0
1*1+0*1 1


然后通过网络把qa和qb发送到执行reduce函数执行的节点上 reduce函数的作用也有两个：1、合并计算结果 2、进行排序输出


0
4/3
q1 = qa+qb= 5/6
11/6


发现这个q1正是我们手工计算时的第一轮迭代的结果，下面的步骤就简单了
那就是把这个q1分发到A和B进行计算新的qa和qb 这是q00={{0,4/3}} q10={{5/6,11/6}}
计算后：
0*0+0*4/3 0
1/3*0+0*4/3 0
qa= 1/3*0+1/2*4/3 = 4/6
1/3*0+1/2*4/3 4/6






0*5/6+0*11/6 0
0*5/6 +1*11/6 11/6
qb= 0*5/6 +0* 11/6 = 0
1*5/6 +0* 11/6 5/6


0
11/6
q2=qa+qb= 4/6
9/6


和我们手工计算的q2相同，如果反复进行运算 知道得到一个理想值，这就是用MR实现PageRank的原理了！