架构师训练营第 13 周作业

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

PageRank，网页排名，又称网页级别，Google 左侧排名或佩奇排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Google 公司创办人拉里·佩奇（Larry Page）之姓来命名。

• PageRank 让链接来"投票"

PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。Google 把从A 页面到B 页面的链接解释为A 页面给B 页面投票，Google 根据投票来源（甚至来源的来源，即链接到A 页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

一个页面的"得票数"由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank 是由所有链向它的页面（「链入页面」）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。

• PageRank 算法

• 假设一个由4个页面组成的小团体：A，B，C 和D。如果所有页面都链向A，那么A 的PR (PageRank) 值将是B，C 及D 的Pagerank 总和。





• 继续假设B 也有链接到C，并且D 也有链接到包括A 的3个页面。一个页面不能投票2次。所以B 给每个页面半票。以同样的逻辑，D 投出的票只有三分之一算到了A 的PageRank 上。



• 换句话说，根据链出总数平分一个页面的PR 值。



• 互联网中如果一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中，这一个或几个网页的PR值将只增不减，显然不合理。为了解决这个问题。我们想象一个随机浏览网页的人，假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。于是则此图中A的PR值可表示为：

$\alpha$默认是0.85

• PageRank的计算公式

$P_1,P_2\dots P_N$是被研究的页面，$M_{pi}$是所有对$P_i$有出链的页面集合, $L\left(p_j\right)$是$P_j$页面的出链数目, $N$是所有页面数量, $\alpha$一般取0.85

• 根据上面的公式，我们可以计算每个页面的PR值，在不断迭代趋于稳定的时候，停止计算，这个时候得到的就是所有页面最终的PageRank值。