PageRank 算法

PageRank算法是图的链接分析（link analysis）的代表性算法，属于图数据上的无监督学习方法。

PageRank算法最初作为互联网网页重要度的计算方法，1996年由Page和Brin提出，并用于谷歌搜索引擎的网页排序。 事实上，PageRank可以定义在任意有向图上，后来被应用到社会影响力分析、文本摘要等多个问题。 PageRank算法基本想法：

• 在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为
• 在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其PageRank值，表示结点的重要度
• PageRank是递归定义的，PageRank的计算可以通过迭代算法进行

1. PageRank 的定义

1.1 基本想法

PageRank是定义在网页集合上的一个函数，对网页给出一个正实数，表示网页的重要程度，整体构成一个向量，PageRank值越高，网页就越重要，在互联网搜索的排序中可能就被排在前面

• 假设互联网是一个有向图
• 在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程
• 假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链
• PageRank表示这个马尔可夫链的平稳分布。每个网页的PageRank 值就是平稳概率

1.2 PageRank 的基本定义

定理 ：不可约且非周期的有限状态马尔可夫链，有唯一平稳分布存在，并且当时间趋于无穷时状态分布收敛于唯一的平稳分布。

• 一般的有向图未必满足强连通且非周期性的条件
• 比如，在互联网，大部分网页没有连接出去的超链接，也就是说从这些网页无法跳转到其他网页。所以PageRank的基本定义不适用

1.3 PageRank 的一般定义

2. PageRank 的计算

包括迭代算法、幂法、代数算法。常用的方法是 幂法

2.1 迭代算法

2.2 幂法

2.3 代数算法