电话

020-88823568

pagerank算法详解

标签: 欧亿体育 2024-02-11 

目录

一、pagerank简介

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

入链数:指向该节点的链接数
出链数:由该节点指出的链接数
以上图为例:A的入链数为2,出链数为3,所以将由A指向其他节点的边权重设置为1/3,表示A访问B、C、D节点的概率均为1/3

两个重要假设

  • 数量假设:在Web图模型中,如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要。
  • 质量假设:指向页面A的入链质量不同,质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A,则页面A越重要。

二、pagerank算法

公式定义

  • PR(a)表示当前节点a的PR值
  • PR(Ti)表示其他各个节点(能够指向a)的PR值
  • L(Ti)表示其他各个节点(能够指向a)的出链数
  • i代表当前时刻或迭代次数

计算演示

接下来以下图为例进行计算演示:

  1. 将四个节点的初始PR都设置为1/4
  2. 根据每一个节点(a)的入链节点(Ti)的PR值及出链数和自身(a)的PR值
  3. 不断进行迭代,直到PR值不再发生变化

以A为例:
A有两个入链节点C(出链数为1,PR=1/4)和D(出链数为2,PR=1/4)由计算公式得到:i=1时刻的PR(A) = (1/4)/1 + (1/4)/2 = 3/8
其余节点计算方法类似,不作赘述。

矩阵化计算

该有向图的邻接矩阵如下所示:

借助邻接矩阵(转移矩阵)的表示方式,我们可以简化上述计算,将四个节点的PR值转化为V向量,并于转移矩阵相乘,可以得到新一轮的PR值向量

由此可以得到每一步PR值迭代的结果为:MV, MMV, MMM*V 最终会收敛为M‘ * V(详细数学证明,有兴趣可以百度查询)

三、存在的两个问题

问题1.Dead Ends

如上图所示:B没有任何出链,这就是Dead Ends,Dead Ends会导致网站权重变成0.

最朴素的想法是:对全是0的列的每一个元素加上1/n(n为节点个数)
对M进行修正

问题2.Spider Traps

如上图所示,A节点与其它节点之间没有出链,这就是Spider Traps,这将导致网站权重变为像一个节点偏移(经过多轮迭代后,A的权重越来越大,趋近于1)
需要对M进行修正:

如上图所示仍有β的概率访问出链页面,但剩下(1 -β)的概率会随机跳转到其他页面,防止一直从A跳转到A的情况