架构师训练营第 1 期 第 13 周作业

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

Google最早是利用网页之间相互的超链接指向关系，来计算网页排名的。



假设有4个网页，A，B，C，D，如果BCD都仅有一个链接，且指向A，那么A的PageRank就等于BCD的PageRank的总和：PR(A)=PR(B) + PR(C) + PR(D)。如果BCD都有2个链接，其中一个指向A，则PR(A)=PR(B)/2 + PR(C)/2 + PR(D)/2。



我们用C(B)，C(C)和C(D)来代表每个页面的链接数，上述公式转化为PR(A)=PR(B)/C(B) + PR(C)/C(C) + PR(D)/C(D)。



但这个公式还有缺陷，就是当一个页面只有指向自己的链接时，RP值每一次计算只会增加，会导致不能收敛。



因此，我们需要增加一个随机概率，就是用户在打开这个网页时，随机输入另一个网址跳出该网页的概率d，这个跳出概率按经验来说是15%。



所以公式转换为：PR(A)=d/N + (1-d)(PR(B)/C(B) + PR(C)/C(C) + PR(D)/C(D).....)，其中N为网页总数。



开始计算：先假定每个页面的初始PR值为1，先计算PR(A)，然后依次计算PR(B)，PR(C)，PR(D)。此为一个迭代。



然后再开始新一轮迭代，再次计算ABCD的PR值。经过X轮迭代后，当PR值变化小于某个阈值时，可认为趋于稳定，停止计算。