架构师训练营第一期 - 第十三周课后作业

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

PageRank 算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的 PageRank 得分，直到得分稳定为止。PageRank 计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。

网页通过链接关系构建起 Web 图，每个页面设置相同的 PageRank 值，通过若干轮的计算，会得到每个页面所获得的最终 PageRank 值。随着每一轮的计算进行，网页当前的 PageRank 值会不断得到更新。在一轮更新页面 PageRank 得分的计算中，每个页面将其当前的 PageRank 值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值，而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的 PageRank 得分。当每个页面都获得了更新后的 PageRank 值，就完成了一轮 PageRank 计算。

如果网页 A 存在一个指向网页 B 的连接，则表明 A 的所有者认为 B 比较重要，从而把 A 的一部分重要性得分赋予 B。这个重要性得分值为：PR（A）/L(A)其中 PR（A）为 A 的 PageRank 值，L(A)为 A 的出链数。B 的 PageRank 值为一系列类似于 A 的页面重要性得分值的累加,即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的 PageRank 是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。

  假设一个由只有 4 个页面组成的集合：A，B，C 和 D。如果所有页面都链向 A，那么 A 的 PR（PageRank）值将是 B，C 及 D 的和。

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

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

但是如果互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不

断地迭代过程中，这一个或几个网页的 PR 值将只增不减，显然不合理。如下图中的 C 网

页就是刚刚说的只有对自己的出链的网页：

为了解决这个问题，要对 PageRank 公式进行修正，即在上面公式 3 的基础上增加一个阻尼系数 d（一般取值 0.85），即假设一个随机浏览网页的人，他有一个确定的概率（1-d）会输入网址直接跳转到一个随机的网页，并且跳转到所有每个网页的概率是一样的。于是则此图中 A 的 PR 值可表示为：

则根据上述 A 网页 PR 值的计算公式推广可得任意一个网页的 PageRank 计算公式为：

P1,P2…PN 是被研究的页面，M(pi) 是链入 Pi 页面的集合，L(pj) 是 Pj 链出页面的数量，而 N 是所有页面的数量。