PageRank算法

在之前的前几篇文章中，我们分别介绍了图遍历算法，单源最短路算法。这篇文章里将介绍一下佩奇排名（PageRank）算法。

PageRank，网页排名，又称为网页级别，Google左侧排名，是一种由网页之间相互的超链接计算的技术，作为网页排名的要素之一。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

我们在生活和生产活动中，会经常遇到网络中节点排序的任务。在互联网中会有以亿为单位的网页，那么哪些页面对用户感兴趣，怎么投放广告？论文在引用和被引用的过程中实现了知识传递，哪些论文在发展中起着关键性的作用？

我们可以用图来表示。图1是有向图，包含了4个节点和4条边。边的起点是一个网页，人或者论文，终点指向的是起点所引用的网页，人或者论文。节点1引用节点0，代表前者从后者获取消息，知识。引用其他节点就是获益；反之，被他人引用就是传播信息。

问题，哪个节点传播力最强更重要?

PageRank认为，节点1向其他节点传递信息，节点1接受不能搞传播从节点0得到的信息。节点0的影响力，可以用其相连的节点1的影响力来衡量。类似于“通过一个人的朋友来分析这个人”。

以上就是对于PageRank算法的介绍，感兴趣的朋友可以自己动手尝试，在这里我推荐使用Graphscope这个平台。

graphscope是阿里达摩院智能计算实验室研发并开源的全球首个一站式超大规模分布式图计算平台，支持多种图算法，可以方便地进行图分析和图计算，并且在性能上也达到极致。

在图分析测试 LDBC GraphAnalytics Benchmark 上，GraphScope 与 PowerGraph 以及其他最新系统比较，几乎在所有算法和数据集的组合中居于领先水平。从下图中我们可以看到，在执行PageRank时，GraphScope用时1.61秒，远小于PowerGraph的26.9秒。

GraphScope 的白皮书、代码已经在 github.com/alibaba/graphscope 开源，可以直接试用。