大数据 | Spark中实现基础的PageRank

吴军博士在《数学之美》中深入浅出地介绍了由Google的佩奇与布林提出的PageRank算法，这是一种民主表决式网页排名技术。书中提到PageRank的核心思想为：

在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。

同时，该算法还要对来自不同网页的链接区别对待，排名越高的网页，则其权重会更高，即所谓网站贡献的链接权更大。

例如网页Y被X1，X2，X3，X4四个网页所链接，且这四个网页的权重分别为0.001，0.01，0.02，0.04，则网页Y的Rank值=0.01+0.02+0.03+0.04=0.071。但问题是，如何获得X1,X2,X3,X4这些网页的权重呢？答案是权重等于这些网页自身的Rank。然而，这些网页的Rank又是通过链接它的网页的权重计算而来，于是就陷入了“鸡与蛋”的怪圈。解决办法是为所有网页设定一个相同的Rank初始值，然后利用迭代的方式来逐步求解。

在《数学之美》第10章的延伸阅读中，有更详细的算法计算，有兴趣的同学可以自行翻阅。下面是PageRank的简单执行步骤：

• 首先假定所有网页的初始Rank值为1/N，N为所有网页的数量。
• 开始迭代。每次迭代，则页面p会将r/n的值发送给所有链接了p页面的邻居页面。其中，r为当前页面的rank值，n为链接了当前页面的邻居页面数。该值实则就是当前页面p这次迭代的贡献者（contribution)。
• 每次迭代结束时，都对最终获得的contributions进行求和。假设每个contribution为c(i)，则可以通过公式α/N + (1-α)∑c(i)获得每个页面的rank值。其中，α是一个常数值，可以认为是一个调优参数（tuning parameter），N为所有页面的数量。

究竟应该迭代多少次呢？由于PageRank实则是线性代数中的矩阵计算，佩奇和拉里已经证明了这个算法是收敛的。当两次迭代获得结果差异非常小，接近于0时，就可以停止迭代计算。《数学之美》中提到：“一般来讲，只要10次左右的迭代基本上就收敛了。”