PageRank的简单理解-什么是pagerank算法

2023-04-23 22:05:36

前言

PageRank 算法

是 Google 创始人于1997年构建早期的搜索系统原型时提出的链接分析算法，是 Google 用于用来标识网页的等级/重要性的一种方法，是 Google 用来衡量一个网站的好坏的唯一标准。例如：一个 PR 值为1的网站表明这个网站不太具有流行度，而 PR 值为7到10则表明这个网站非常受欢迎（或者说极其重要）。一般 PR 值达到4，就算是一个不错的网站了。

如果跳出网页推荐这一具体应用来看，我们可以将网页看成图中的节点，进而可以将PageRank 看成是图分析中的重要算法。在实际应用中许多数据都以图（graph）的形式存在，比如，互联网、社交网络都可以看作是一个图。图数据上的机器学习具有理论与应用上的重要意义。 PageRank 是图的链接分析（link analysis）的代表性算法，属于图数据上的无监督学习方法。

1. 什么是 PageRank

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

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

2. PageRank 算法推导

PageRank 的提出是为了解决基于网页的搜索推荐问题，它的提出基于两个假设，分别是数量假设和质量假设。

数量假设：在网页模型图中，一个网页接收到的其他网页指向的入链（in-links）越多，说明该网页越重要。

质量假设：当一个质量高的网页指向（out-links）一个网页，说明这个被指向的网页质量也高。

基于此，我们给出迭代的计算每个网页（节点）的 PR 值计算公式：

$(1)PR(a)i+1=\sumi=0nPR(Ti)iL(Ti)$ PR(a){i+1} = \sum{i = 0}^n \frac{PR(T_i)_i}{L(T_i)} \tag{1}

其中， $PR(Ti)i$ PR(T_i)_i 代表的是在第 $i$ i 次迭代中其他节点(指向节点a的节点)的PR值， $L(Ti)$ L(T_i) 代表的是其他节点(指向节点a的节点)的出链数。（数量假设和质量假设）

在算法开始迭代之前，初始化每一个网页（图中节点）的 PR 值，一般情况下，所有结点的 PR 值初始化为 $1N$ \frac{1}{N} ，其中 $N$ N 为所有网页的数量。

基于此，我们可以看出 PageRank 其实是一种无监督的迭代算法，基于网页之间已知的超链接跳转关系可以不断迭代计算每个网页的重要程度直至收敛。

3. PageRank 的矩阵化分析

前面说过 PageRank 算法的基本思想是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。这个随机游走模型即一阶马尔可夫链的详细定义如下，可以辅助理解 PageRank 的矩阵化推导。

随机游走模型（一阶马尔可夫链）：

给定一个含有 $n$ n 个节点的有向图，在有向图上定义随机游走（random walk）模型，即一阶马尔可夫链，其中节点表示状态，有向边表示状态之间的转移，假设从一个节点到通过有向边相连的所有节点的转移概率相等。具体地，转移矩阵是一个 $n$ n 阶矩阵。

$(2)M=[mij]n\timesn$ M = [m_{ij}]_{n \times n} \tag{2}

第 $i$ i 行第 $j$ j 列的元素 $mij$ m_{ij} 取值规则如下：如果节点 $j$ j 有 $k$ k 个有向边连出，并且节点 $i$ i 是其连出的一个节点，则 $mij=1k$ m_{ij} = \frac{1}{k} ，否则 $mij=0,i,j=1,2,\dots,n$ m_{ij} = 0,i,j=1,2,\dots,n 。