用 Spark 实现 PageRank 算法

运行环境

  • Deepin Linux 16.04 x64
  • Spark 2.1.0
  • Scala 2.11.11
  • Open JDK 8
  • IDEA 2017.1 + Maven


PageRank算法

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

它按如下步骤进行计算:

1. 将每个页面的排序值初始化为1.0。

2. 在每次迭代中,对页面p,向其每个相邻页面(有直接链接的页面)发送一个值为rank(p)/numNeighbors(p)的贡献值。

3. 将每个页面的排序值设为0.15 + 0.85 * contributionsReceived。

最后两个步骤会重复几个循环,在此过程中,算法会逐渐收敛于每个页面的实际PageRank值。在实际操作中,收敛通常需要大约10轮迭代。


Scala Code


代码说明

首先对当前的ranksRDD和静态的linkRDD进行一次join()操作,来获取每个页面ID对应的相邻页面列表和当前的排序值,然后使用flatMap创建出“contributions”来记录每个页面对各个相邻页面的贡献。然后再把这些贡献值按照页面ID(根据获得共享的页面)分别累加起来,把该页面的排序值设为0.15 + 0.85 * contributionsReceived。


运行结果

发表评论

电子邮件地址不会被公开。