架构师训练营第十三周作业

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

PageRank算法是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法，是Google用来衡量一个网站的好坏的唯一标准。通过算法计算网站的一个PR值（PageRank）,PR越高，网站的重要性越高。

算法的出发点是：1）每个网页对它链出的网页投票，投票的数量形成PR值；2）如果一个网页有很多链接链接到它，它的PR值就高。3）如果一个网页被PR值高的网页链接，其PR也相应提高。

算法基本的计算过程大体是：1）在要计算的一组网页中，初始化每个网页的PR值。2）通过递归的，根据每个网页的链入的其他网页的PR值，更新其PR值。

一般的更新公式为：

假设有p1,p2,p3,......pN这N个页面，每个页面Pi的更新公式

每个网页的PR值等于所有链入的网页的PR值除以其链出数的和。其中L(pj)表示pj这个网页链出的网页数，Mpi为链入pi的网页。如果一个网页对多个网页有链接链出，它不能投多票，所投的票在各个链出的网页进行平分。

如果遇到有自己链接自己的网页，上面的公式会导致计算结果无限增大而无法收敛，公式进行调整。假设有一定概率1-q，用户会从浏览器输入URL调整的其他页面，q为阻尼系数，公式调整为：

其中N为网页总数。