PageRank基于Spark实现介绍

来源:转载

该算法为谷歌的拉里•佩奇命名。以迭代方式,根据外部文档指向一个文档的链接来更新每个文档的权重。每个文档给它的相邻文档提供r/n的权值,其中r是该文档的rank,n表示它的邻居文档个数。通过公式a/N +(1-a/N)*sum(ci) 来更新rank,其中N是文档的总个数,sum(ci)是接收到的权值总和,a可调参数。这样通过提供rank一个初始值,就可以进行迭代更新得到理想的rank,从而对文档排序

在Spark中可以这样实现PageRank

val links = spark.textFile(...).map(...).persist()//相邻页面列表保存于内存中供迭代使用

var ranks = // (url, rank) 给定rank初始值

for (i <- 1 to ITERATIONS) {

// 创建RDD键值对(targetURL, float)

//(url,(links,rank))=(url,(相邻页面,对应的rank))

val contribs = links.join(ranks).flatMap {

(url, (links, rank)) =>

links.map(dest => (dest, rank/links.size))//=(每个页面,贡献的权值)

}

ranks = contribs.reduceByKey((x,y) => x+y).mapValues(sum => a/N + (1-a)*sum)

}//reduceByKey()合并具有相同键的值,即对每个页面来说,将相邻页面的贡献的权值相加

参考 Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing

 

分享给朋友:
您可能感兴趣的文章:
随机阅读: