数据挖掘算法——PageRank及建立的模型

PageRank是由Sergey Brin和Larry Page在1998年WWW7会议上提出的，用于解决链接分析中的网页排名问题。在衡量网页排名时，直觉告诉我们：

• 当一个网页链接到另一个网页时，它的排名会更高；
• 高排名的网页应该有更大的投票权，也就是说，当网页链接到高排名的页面时，其重要性也应该增加。

对于这两个直觉，PageRank 算法创建的模型非常简单：网页的排名等于链接到该网页的所有网页的加权排名之和：

(1)

PRi 表示第i个网页的PageRank值，用于衡量每个网页的排名；排名越高，PageRank 值就越大。网页之间的链接关系可以写成有向图G=(V,E)。 Edge(j,i)表示网页j链接到网页i； Oj 是网页 j 的退出率，也可以认为是网页 j 的退出链接数（退出链接数）。

假设 P=(PR1,PR2,⋯,PRn)TT 定价为 nk-，直接数为 nnk- 对应于转移矩阵的图G，

Aij={1Oi0if (i,j)εOijwiseAij={1Oiif (i,j)εE0otherwise

n 可重写为等式：

p = Atp这么排第一，是不是鸡蛋有问题？幸运的是，PageRank 使用幂迭代的方法消除了这个问题。

2。求解

为了对上面和下面的求解过程有个直观的了解，我们来看一个例子。网页链接关系图如下：

那么矩阵A就是

所谓幂迭代 意思是P❿先为p，然后求解通过各种迭代：

pk = atpk-1最终收敛到 || p k−Pk−1||

显然，一般情况下，矩阵A不满足这三个性质。为了满足随机矩阵的性质，可以将所有0行替换为e/n，其中e是单位向量；同时，为了满足不可约性和非周期性，必须进行平滑处理：

其中，d 为阻尼因子，通常设置为 0 到 1 之间的常数； E 是单位矩阵。那么，等式（1）改写为