2020-09-03- 第十三周作业

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



PageRank算法根据页面链接作为投票方法，并进行一定轮次的投票，每一轮投票都会根据上一轮的等级以及其相关页面的权重得到本轮的等级，最终经过N轮后，每个页面的值不再大幅度变化为止，此时便是该页面的等级值。计算公式如下图，其中d为在浏览A页面时跳转到其他页面的概率，通常为0.85；N为所有页面个数；C(T)则代表T页面中包含页面链接的个数。



比如先有4个页面A、B、C和D，我们可以通过以下步骤来分别确定每个页面的等级值。设置

（1）初始化PR(A)=PR(B)=PR(C)=PR(D) = 1，即将每个页面初始等级设置为1。

（2）开始当前轮次投票，则PR(A)=(1-d)/4 + d(PR(B)/C(B) + PR(C)/C(C) + PR(D)/C(D))。即如果当前是第一轮投票，则PR(A) = (1 - 0.85) / 4 + 0.85 * (1 / C(B) + 1/ C(C) + 1/C(D))，其中d设置为0.85，由于是第一轮，所以每个页面的PR值都为1，然后根据不同的权重最终得到这一轮的A页面的PR值。

（3）循环其他三个页面，按照步骤（2）中的方法计算每个页面当前轮次的PR值。

（4）如果递归轮次超过上限M，则执行完毕。否则回到步骤（2），计算下一轮的PR值。