Week 13 命题作业

Google 搜索引擎是如何对搜索结果进行排序的？（请用自己的语言描述 PageRank 算法。）



PageRank算法做了两个基本假设：

数量假设：被更多的网页链接到的网页更重要。

质量假设：有更高权重的网页会传递更高的权重出去。

PageRank的公式简单模型：

PRi​=jϵBj​∑​Lj​PRj​​

PR为权重，L为出链数。在理想状态下，页面i的权重是所有链接到该页面的页面平均投票权重的总和。

在初始化阶段，设所有页面的权重都为1，根据以上公式进行迭代计算，更新各个页面的PR值，直到PR值收敛。

终止点：

终止点是指一个没有任何出链的网页。

在基础公式中，终止点会导致转移矩阵终止转移概率，最后迭代的结果是所有的网页PR值都是0。

因此当访问到终止点时，以等概率跳转到下一个网页。该概率为1/矩阵行数。

陷阱：

陷阱/黑洞指的是只有指向自身链接的网页，如图中C点。

根据基础公式多次迭代，会使得陷阱页面的PR值为1，而其他正常网页的概率为0。

为了解决这个问题，就有了随机浏览模型。

PRi​=djϵBj​∑​Lj​PRj​​+N1−d​

其中d为阻尼系数，N为所有页面的数量。