本文共 1445 字，大约阅读时间需要 4 分钟。

PageRank

• 1基本概念
• 2算法基础讲解
• 3 Dead Ends问题
• 4 Spider Traps问题
• 5 算法优缺点
• 6 使用β能否解决Dead Ends问题

1、基本概念

1.1 背景介绍

1.1.1 google提出

1.1.2 PageRank值高，则搜索内容时，出现在最前位

1.1.3 PageRank称为PR，对于网页进行排名，计算网站的重要性，PR值表示其重要性因子

2.1算法中心思想

2.1.1 数量假设：当在网页模型图中，一个网页接收到的其他网页指向的入链越多，则该网页越重要，在图中用大小来表示PR值。

2.1.2质量假设：当一个质量高的网页指向另一个网页，则这个被指向的网页也重要

2.1.3入链(in-links)出链(out-links)，字面意思

2、算法基础讲解

2.1 PageRank公式

              其中当i=0时，初始化PR值为1n,其中n为网页总数，即每个网页一样重要。

   计算PR值例子：

      其中ABCD为互相指向的网页。初始化PR值均为1/4。利用PageRank公式进行更新PR值。（因PR值只更新一次不稳定，需多次更新）

计算PR(A)

计算PR(B)

以此类推，第一次迭代求得所有网页的PR值，并根据PR值进行排序，得到结果如下。

将PR值转为矩阵（便于计算,及更新PR值）

其中M为当前PR值矩阵化表达，V为上一次得到的PR值。

第二次迭代结果：

由下图可知，PR = M*V，可得到下一步的PR值

3、Dead Ends问题

若A指向B，B不指向任何一个网页，则B的PR值会变为0

可发现，在迭代过程中，会逐渐使PR变为0，这个问题称之为Dead Ends问题。

使用PR = M*V验证，得同样结果，在第二次迭代是，PR值均变为0

3.1、使用Teleport解决Dead Ends问题

   因在迭代过程中M矩阵中有某一列全为0，故在M*V时，产生Dead Ends问题，Teleport设置a（1xN维），若M中第i列为0时，ai=[1,1,…,1],其余状态下，a全为0。

3.2 使用Teleport解决Dead Ends问题例题

   通过Teleport，将M矩阵中均为0的列，加1n,解决网络中结点只含入链不含出链的问题。

4、Spider Traps问题

Spider Traps例子：

当网络中存在，只有自己指向自己时，PR值在更新过程中，含有自指向结点的PR值会逐渐归于1，其他结点归于0，此为Spider Traps问题。

4．1、Spider Traps问题解决方法，Random Teleport

步骤1：列转移概率矩阵：即B出链，指向其他结点的概率。 将列转移概率矩阵设为M矩阵。例

   步骤2：

   为了使，M矩阵中某列只有一行为1的问题，以1-β的概率加上到其他结点的平均概率。例：

我认为是在尽可能不影响其他结点的PR值比例的条件下，解决M中某列中只有一个1的问题。

通过修正后的M矩阵，通过PR = M*V，解决PR值偏向有环的结点。

4．2 总结Spider Traps问题修正公式

最终修正公式：将解决Dead Ends与Spider Traps汇总

在解决Dead Ends与Spider Traps问题时，都是修正M矩阵。

5 PageRank算法优缺点

6 使用β能否解决Dead Ends问题

故仅用β不能解决Dead Ends问题

转载地址：https://blog.csdn.net/qq_41427834/article/details/110262036 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！