大数据方法论之PageRank的Map-Reduce计算

大家可能都熟悉Google的Page Rank算法，那么如何通过Map-Reduce的方式实现这个算法呢？

Page Rank算法遵循的是平时我们浏览网页的时候的随机游走模型：

• 用户从任意一个网址开始浏览网页

• 如果某个网页有N个链接，则用户很大的可能是随机选择一个链接继续浏览

• 当某个网页没有链接，则用户会任意选择一个网页进行浏览

• 在任何一个网页，用户都存在一定的可能性，任意选择另外一个网页进行浏览 (远程跳转)

对于如图中的网页的相互关系，如何鉴别那个网页更加的好呢？

其实就是让链接来”投票”

一个页面的得票数由所有链向它的页面的重要性來决定，到一个页面的超链接相当于对该页投一票。

如下面的公式所示

这个公式可以通过矩阵运算得到。

然而网页之间的关系是有环的，所以第一次运算完毕之后，得到的向量会影响第二次的运算，如此下去进行N次运算，可能结果才能稳定下来。

可能你会疑问，能够稳定下来么？

如果做一个实验，用excel画一个图，你会发现，是会越来越取向稳定的。

我们管这种趋于稳定的状态叫做收敛。

为了更好的收敛，我们对于计算PageRank的公司稍作修改