架构师训练营十三周作业

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



PageRank是通过网页上超链接之间的关系来计算的。如果一个网页B包含另一个网页A的链接，就可以认为网页B给网页A投了一票，网页B认为网页A比较重要。

假设全球只有4个网页A, B, C, D。他们之间包含链接的关系如图所示：



1. 根据上图，如果我们想计算page A的rank，把第一段话简单翻译成公式，因为B，C，D都包含了链接A，则PageRank A = PageRank B + PageRank C + PageRank D。

2. 上述公式有个明显的问题，即B给A投了一票，并不能简单用PR(B)来表示（以下都用PR来表示PageRank），因为页面B可能包含多个链接，所以针对每个链接的投票，可以用PR(B)/L(B)来表示，L(B)表示B中包含的链接个数。则上述公式变为 PR(A) = PR(B)/L(B) + PR(C)/L(C) + PR(D)/L(D) = PR(B)/2 + PR(C)/1 + PR(D)/3.

3. 通过上图可以看到，链接之间形成的图是有环的，所以PR值的计算中，是有循环依赖的，该如何处理这个问题呢？最直接的方式就是计算多次，针对每个节点计算一次PR值，然后用新的值再次计算，一直递归下去。递归必须要有终止条件，一种最简单的终止条件就是指定递归次数，比如10次，另一个是设置一个合理的最小变动值，当新计算出的PR值跟上次相比，变动非常小，都小于最小变动值，则终止计算。

4. 有一种作弊提高自身PR值的方式，就是包含自身的链接，这样每次递归计算的时候，都会让自身的PR值增加。为此，引入了随机浏览网页的概念，即用户有一定的几率通过网址直接跳转到任意一个网址，而不是通过网页中的链接。可以将通过网页链接跳转的几率记为d （google将d设为0.85，即通过地址栏跳转的几率为0.15）。然后便可以推导出最终的公式：

其中，PageRank(Pi)表示页面Pi的rank值，d为通过网页链接跳转的几率，N为所有网页的总数，M(Pj)为包换链接Pi的网页集合，Pj为M(Pj)中的任意一个网页，L(Pj)为Pj中包含的链接总数。