GraphX内置图算法3：页面排名
页面排名算法是由谷歌联合创始人Larry Page发明的。它通过计算输入边来确定顶点在图中的重要性。它被广泛用于分析web页面在web图中的相对重要性。它首先为每个顶点分配一个页面等级（PR）值为1。它将这个PR值除以输出边的数量，然后将结果添加到所有相邻顶点的PR值。重复这个过程，直到PR值的变化不再超过公差参数。
因为页面的PR值除以输出边的数量，所以页面的影响会根据它所引用的页面的数量按比例缩小。排名最高的页面是具有最少输出链接数量和最大输入链接数量的页面。PageRank还研究了指向目标页面的页面的重要性。因此，如果一个给定的web页面有来自高级页面的传入链接，那么它的排名将会被排得更高。
我们可以通过调用图的pageRank方法并传入公差参数来在图上运行页面排名算法。公差参数决定了页面等级值可以改变的数量，并且仍然被认为是收敛的。值越小意味着越精确，但是算法也需要更多的时间来收敛。计算结果是另一个图，其顶点包含PR值。
下面的代码从Wikispeedia的文章中找出10个排名最高的页面。
// 计算Page Rank：pageRank方法返回一个以pageRank为顶点属性、以标准化权重为边属性的图
// 第一个参数是收敛阈值或容差
// 第二个参数是可选的。它指定PageRank算法使用的随机重置概率(默认是0.15)
val ranked = wikigraph.pageRank(0.001)
// 自定义排序规则
val ordering = new Ordering[Tuple2[VertexId,Double]] {
def compare(x:Tuple2[VertexId, Double], y:Tuple2[VertexId, Double]):Int = x._2.compareTo(y._2)
}
// 查看Wikispeedia子集中的10个最高排名的页面
val top10 = ranked.vertices.top(10)(ordering)
top10.foreach(println)
输出内容如下所示：
(4297,43.7954539051477) (1568,29.519387497799176) (1433,29.090727549623015) (4293,28.60229929198179) (1389,22.334694754966097) (1694,22.146226641406027) (4542,21.690337661883046) (1385,20.48019474759793) (2417,20.22647356628089) (2098,18.556114930552365)
从输出结果中可以看出，top10数组现在包含了10个最高排名的页面的顶点ID和它们的PR值，但是我们仍然不知道这些ID属于哪个页面。这可以使用articles RDD来join连接这个数组，以找出这些最高排名的文章名称：
// 找出这些最高排名的文章名称：
spark.sparkContext.parallelize(top10)
.join(articles.map(_.swap))
.collect
.sortWith((x, y) => x._2._1 > y._2._1)
.foreach(println)
输出内容如下所示：
(4297,(43.7954539051477,United_States)) (1568,(29.519387497799176,France)) (1433,(29.090727549623015,Europe)) (4293,(28.60229929198179,United_Kingdom)) (1389,(22.334694754966097,English_language)) (1694,(22.146226641406027,Germany)) (4542,(21.690337661883046,World_War_II)) (1385,(20.48019474759793,England)) (2417,(20.22647356628089,Latin)) (2098,(18.556114930552365,India))
结果中每个元组的第一个元素是顶点ID；第二个元素包含PR值和页面名称。正如结果中所看到的，关于United States的页面是数据集中最具影响力的页面。
