1）Page Rank 计算


公式： q=Gq


G=0     0     0     0


  1/3   0     0     1


  1/3  1/2    0     0


  1/3  1/3    1     0


page rank :反复 map 映射 -> reduce汇总 ->再次 map 映射 -> 再次 reduce汇总 -> 反复三次 感觉就行了，理论上一直递归下去会是一个收敛值


参数：

q 特征向量：1  1  1  1


根据 q 【next】 = a * s * q + (1-a)/n * U *q


a 偏移量 0.5  0.5  0.5  0.5


n 节点数 4


u 1 1 1 1


  1 1 1 1


  1 1 1 1


s 当a阿尔法=1时 G=S


float[] pr_cur={0.5f,0.5f,0.5f,0.5f};


计算


（1）0.0


（2）0.79999995


（3）0.39999998


（4）0.79999995


有朋友帮忙同样参数，使用R语言得出page rank ：[1] 0.1250000 0.3141026 0.2243590 0.3365385  朋友的理论是特征向量加起来不能大于1，不知道是否正确


2)按照map-reduce的思想，现在假设有物理节点A，B参与计算，其中网页1、2保存于A，网页3、4保存于B，试述完整的pagerank计算过程


现在我们有2个节点，有4个页面page，我们现在分析出网页有那些外链指向出来


Map


初始特征向量 1  1  1  1


第一个节点有1 2列   把1   1   送过来


第二个节点有3 4列   把1   1   送过来



Google 外链向量


   _                 _


  |0     0     0     0|


  |1/3   0     0     1|


  |1/3  1/2    0     0|


  |1/3  1/3    1     0|



1 * 第一个列[0 1/3 1/3 1/3] + 1 * 第二个列[0 0 1/2 1/3] = 算出一个向量  这是第一个节点(A)


1 * 第三个列[0 0 0 1] + 1 * 第四个列[0 1 0 0] = 算出一个向量  这是第二个节点的(B)


Reduce


我们把每个节点上算出的向量，统统发送给一个目标节点，把这些向量全部加起来，得到一个汇总向量，这就是第一次迭代出来特征向量q1


再把q1重新分配到各个节点在算一次每个列的和，在汇总到目标节点，得到一个汇总向量，这就是第二次迭代出来特征向量q2，就这样一直迭代下去直到收敛为止！



Map 把特征向量映射到每一个节点，每一个节点只计算自己的向量负荷，实现了分布式计算，平摊了整体负载


Reduce 每个节点上算出的向量，统统发送给一个目标节点，把这些发送过来的向量全部加起来，得到一个汇总向量，多次迭代后就计算出了page rank值了。



映射思想


根据公式 q=gq


初始特征向量 1  1  1  1



A节点可以计算出q1  q2的值


q1= 1*0+1*1/3+1*1/3+1*1/3=5/3


q2= 1*0+1*0+1*1/2+1*1/3=5/6



B节点可以计算出q3  q4的值


q3= 1*0+1*0+1*0+1*1=1


q4= 1*0+1*1+1*0+1*0=1



汇总思想

把A节点q1 q2 和 B节点q3 q4 发送到目标节点生成汇总向量，这就是第一次迭代出来特征向量q


q= { q1 q2 q3 q4 }={ 5/3 5/6 1 1 }


这是一次完整的map_reduce计算过程,然后把这个q再重新分配到每个节点上map运算



第二次迭代


q1= 5/3*0+5/3*1/3+5/3*1/3+5/3*1/3=1.67


q2= 5/6*0+5/6*0+5/6*1/2+5/6*1/3=0.693


q3= 1*0+1*0+1*0+1*1=1


q4= 1*0+1*0+1*0+1*1=1



再次把A节点q1 q2 和 B节点q3 q4 发送到目标节点生成汇总向量，这就是第二次迭代出来特征向量q


q= { q1 q2 q3 q4 }={ 1.67 0.693 1 1 }



这是第二次map_reduce计算过程，如此反复迭代计算，最后设定一个较小的值，如果最后迭代的特征向量近似这个较小的值，那么就可以算是pagerank了


map_reduce想法：反复 map 映射 -> reduce汇总 ->再次 map 映射 -> 再次 reduce汇总 -> 一直递归下去会是一个收敛值

 

 

Leonarding
2012.8.23
天津&autumn
分享技术~收获快乐
Blog：http://space.itpub.net/26686207