目录
*
– 一、pagerank简介
–
+ 两个重要假设
– 二、pagerank算法
–
+ 公式定义
+ 计算演示
+ 矩阵化计算
– 三、存在的两个问题
–
+ 问题1.Dead Ends
+ 问题2.Spider Traps
一、pagerank简介
PageRank算法的基本想法是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其PageRank值，表示结点的重要度。PageRank 是递归定义的，PageRank 的计算可以通过迭代算法进行。
传入链接数：指向该节点的链接数
[En]
Number of incoming links: the number of links pointing to this node
传出链接数：该节点指示的链接数
[En]
Number of outgoing links: the number of links indicated by this node
以上图为例：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代表当前时刻或迭代次数
; 计算演示
接下来，以下图为例演示计算过程：
[En]
Next, the following figure is used as an example to demonstrate the calculation:
- 将四个节点的初始PR都设置为1/4
- 根据每一个节点（a）的入链节点(Ti)的PR值及出链数和自身(a)的PR值
- 不断进行迭代，直到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
其他节点的计算方法类似，不再重复。
[En]
The calculation methods of other nodes are similar and will not be repeated.
矩阵化计算
有向图的邻接矩阵如下：
[En]
The adjacency matrix of the directed graph is as follows:
借助邻接矩阵（转移矩阵）的表示方式，我们可以简化上述计算，将四个节点的PR值转化为V向量，并于转移矩阵相乘，可以得到新一轮的PR值向量
由此可以得到每一步PR值迭代的结果为：MV， M _M_V， M _M_M*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的情况
Original: https://blog.csdn.net/gary101818/article/details/124208393
Author: Unstoppable~~~
Title: pagerank算法详解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/527281/
转载文章受原作者版权保护。转载请注明原作者出处！