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

此文已由作者刘超授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验

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

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

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

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

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

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

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

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

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

如下面的公式所示

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

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

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

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

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

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

增加一个阻尼系数，通俗的理解阻尼系数，就是说当你现在在B,C,D网页的时候，除了沿着里面的连接到达A之外，还有一种随机的方式，在当前的页面看烦了，之间输入A的网址跳到A。

当有了这个阻尼系数之后，PageRank就是一定能够收敛的了。

因为有定理：有限状态的不可约非周期马尔可夫链必存在平稳分布。

靠，这说的是啥，你不用管，反正存在平稳分布就是了。

还有一个补充定理：正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的。

在前面的矩阵里面，有为0的元素，所以其实不一定存在平稳分布，但是有了(1-d)，则所有的元素都是正的了，则这个矩阵就变成了不可约非周期的，所以一定存在平稳分布。

所以如果写一个Java程序做矩阵运算是这样的，但是如果网页数据量太大了，这样是算不过来的。

于是Map-Reduce就发挥了作用。

首先从爬取的网页里面，输出outlinks的库，在这个库中，保存了From->To的映射关系。

因为PageRank的计算是根据入链来的，因而要通过一个map-reduce程序，输出inlinks库，保存从To->From的映射关系。

然后通过两个库outlinks和inlinks进行合并，生成Node库，每个Node保存每个网页有多少是我链接别人的，有多少是别人链接我的，以及每个网页的score的初始值。

接下来基于初始的score值进行一个循环，不断的迭代。

在每个迭代中，首先Inverter会从outlinks库和nodes库进行合并并翻转，得到To->List<From, Score of From>的一个映射关系。

在每个迭代中，其次Analyzer会基于上面的映射关系和nodes库，计算To的这个网页的score，score(To)=sum(score(from))，也即将from的每个score加起来。

如此循环，直到收敛到一个稳定的score，则停止循环。

免费体验云安全(易盾)内容安全、验证码等服务

11.1—11.15云计算基础服务全场5折起

更多网易技术、产品、运营经验分享请点击。