Spark读书笔记:PageRank

PageRank算法是以Google的拉里·佩吉(LarryPage)的名字命名的,用来根据外部文档指向一个文档的链接,对集合中每个文档的重要程度赋一个度量值。该算法可以用于对网页进行排序,当然,也可以用于排序科技文章或社交网络中有影响的用户。

PageRank是执行多次连接的一个迭代算法。算法会维护两个数据集:一个由(pageID,linkList)的元素组成,包含每个页面的相邻页面的列表;另一个由(pageID,rank)元素组成,包含每个页面的当前排序值。它按如下步骤进行计算。

(1)将每个页面的排序值初始化为1.0。
(2)在每次迭代中,对页面p,向其每个相邻页面(有直接链接的页面)发送一个值为rank(p)/numNeighbors(p)的贡献值。
(3)将每个页面的排序值设为0.15+0.85*contributionsReceived。

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

Spark实现PageRank的代码

// 假设相邻页面列表以Spark objectFile的形式存储
val links = sc.objectFile[(String, Seq[String])]("links")
                  .partitionBy(new HashPartitioner(100))
                  .persist()
// val links = session.sparkContext.parallelize(Array(('A', Array('D')), ('B', Array('A')), ('C', Array('A', 'B')), ('D', Array('A', 'C'))))
// 将每个页面的排序值初始化为1.0;由于使用mapValues,生成的RDD // 的分区方式会和"links"的一样
var ranks = links.mapValues(v => 1.0)
// 运行10轮PageRank迭代
for(i <- 0 until 10) {
      val contributions = links.join(ranks).flatMap {
        case (pageId, (links, rank)) =>
          links.map(dest => (dest, rank / links.size))
      }
      ranks = contributions.reduceByKey((x, y) => x + y).mapValues(v => 0.15 + 0.85*v)
    }
// 写出最终排名
ranks.saveAsTextFile("ranks")

这就行了!算法从将ranksRDD的每个元素的值初始化为1.0开始,然后在每次迭代中不断更新ranks变量。在Spark中编写PageRank的主体相当简单:首先对当前的ranksRDD和静态的linksRDD进行一次join()操作,来获取每个页面ID对应的相邻页面列表和当前的排序值,然后使用flatMap创建出“contributions”来记录每个页面对各相邻页面的贡献。然后再把这些贡献值按照页面ID(根据获得共享的页面)分别累加起来,把该页面的排序值设为0.15+0.85*contributionsReceived。
虽然代码本身很简单,这个示例程序还是做了不少事情来确保RDD以比较高效的方式进行分区,以最小化通信开销:
(1)请注意,linksRDD在每次迭代中都会和ranks发生连接操作。由于links是一个静态数据集,所以我们在程序一开始的时候就对它进行了分区操作,这样就不需要把它通过网络进行数据混洗了。实际上,linksRDD的字节数一般来说也会比ranks大很多,毕竟它包含每个页面的相邻页面列表(由页面ID组成),而不仅仅是一个Double值,因此这一优化相比PageRank的原始实现(例如普通的MapReduce)节约了相当可观的网络通信开销。
(2)出于同样的原因,我们调用links的persist()方法,将它保留在内存中以供每次迭代使用。
(3)当我们第一次创建ranks时,我们使用mapValues()而不是map()来保留父RDD(links)的分区方式,这样对它进行的第一次连接操作就会开销很小。
(4)在循环体中,我们在reduceByKey()后使用mapValues();因为reduceByKey()的结果已经是哈希分区的了,这样一来,下一次循环中将映射操作的结果再次与links进行连接操作时就会更加高效。

参阅:Learning Spark

打赏支持:支付宝/微信,感谢赏口饭吃