[架构师训练营第 1 期] 第 13 周命题作业

题目

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

成果

PageRank 算法，其基本原理是基于其它页面对某个页面的引用来为该页面进行评分，评分越高则排名越靠前。

比如，有 A、B、C、D 四个页面，那么 A 的评分（PR 值）就等于：

        PR(B)   PR(C)   PR(D)PR(A) = ————— + ————— + —————         L(B)    L(C)    L(D)

其中，L(X) 等于 X 页面引用的页面数（允许自己引用自己）。

但是，因为允许页面自己引用自己，所以当页面只引用自己时，这个页面就只可能被其它页面引用而不可能引用其它页面，从而导致这个页面的分数只进不出，影响评分的准确性。

因此，为了解决上述这个问题，算法设定了一个固有概率（α）作为一个页面通过输入地址跳转到其它页面的可能性，从而破除页面评分只进不出的局面，也就是说，就算一个页面只引用了自身，也会因为这个固有频率被算法认为是有一定的概率会跳转到其它页面。

所以，各页面评分公式修正为：

           PR(B)   PR(C)   PR(D)    1 - αPR(A) = α*(————— + ————— + —————) + —————            L(B)    L(C)    L(D)      N

其中，N 等于 A 、B、C、D 的总页面数，在这里就等于 4。

所以，可以得到一个通用的 PageRank 评分公式：

            PR(pj)  1 - αPR(pi) = α*Σ————— + —————            L(pj)     N

其中：

• PR(X) = X 页面的 PageRank 评分

• i = 1, 2, 3 ,..., N

• pi = 第 i 个页面

• pj = 第 j 个引用 pi 页面的页面

• α = 上述固有概率

• L(X) = X 页面引用的页面总数

• N = 所有页面的数量

实际大数据计算时，使用的是矩阵的形式进行计算，各个页面的 PR 值初始为 1，进行迭代计算，直到页面的 PR 值稳定为止所得到的的 PR 值即为该页面的评分。