第十三周作业

Google 搜索引擎是如何对搜索结果进行排序

Google搜索引擎采用的PageRank来进行网页排名，PageRank算法是一种以网页之间的超链接个数和质量作为主要因素粗略的分析网页的重要性算法，其基于的假设是：更重要的页面往往更多的被其他页面引用。其将从A页面到B页面的链接解释为“A页面给B页面投票”，并根据投票来源（甚至来源的来源，即链接到A页面的页面）和投票对象的等级来决定被投票页面的等级。简单的说，一个高等级的页面可以提升其他低等级的页面。

假设一个由4个网页组成的群体，A，B，C和D，如果所有页面都链接到A，则A的PR值将是B、C、D的PageRank总和，也即：PR(A) = PR(B) + PR(C) + PR(D)

假设B链接到A和C，C只链接到A，并且D链接到全部其他的3个页面。一个页面总共只有一票。所以B给A和C每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。也即PR(A) = PR(B) / 2 + PR(C) + PR(D) / 3

所以一个页面的的PR值为 PR(A) = PR(B) / L(B) + PR(C) / L(C)+ PR(D) / L(D)，L(B)、L(C)、L(D)是B、C、D页面的出度，也即他们链接了几个页面。

现实网络中由于存在出度为0的，即不链接任何网页的页面，但是很多网页可以访问它，所以上面的公式就需要进行修正。在上面公式需要增加一个阻尼系数d，也即用户随机点击链接的概率，(1 - d) 就是不考虑入站链接情况下随机进入一个页面的概率。假设总共有N个页面，且有j个页面链接到i页面。所以修正公式为：

最后不断重复计算每个页面的PR值，最终每个页面的PR值都将趋于稳定。