架构师训练营第十三章作业

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



PageRank算法是Google创始人Sergey Brin和Lwarence Page于1998年提出来的，它是基于Web超链接结构分析的算法中最成功的代表，也是评鉴网页权威性的重要工具。

PageRank算法借鉴了传统的情报检索理论中的引文分析方法。核心思想就是：当网页A存在一条超链接指向网页B时，就理解为“网页A向网页B投了一票”，网页B的重要级数就得到增加。PageRank算法还认为网页B的重要性不仅与它收到的投票总量有关，还和投票质量网页A的重要性即有关。公式如下：

式中PG（A）、PG(   )分别表示网页A和网页    的PageRank值；c是介于0和1之间的衰减系数，一般设为0.85；N(   )表示网页     向外指出的链接数目。从式中可以看出：当一个网页指向其它网页时，它的重要性将被均平传递到它所链接的网页。

然而由于在计算PageRank值时用到了其它网页的PageRank的值，这就出现了一个类似先有鸡还是先有蛋的问题。解决方法是：假设每个网页的初始权威性为1，然后算出网页经过第一轮迭代后的Pagerank值，接着根据第一轮的结果计算第二轮迭代后的值，以此类推，直至结果收敛为止。

PageRank算法的高明之处就在于它把整个网络当成一个整体，充分利用了网页之间的联系，而不像传统信息检索把各个网页当做独立个体分开来处理。

4.PageRank算法的不足

从以上的分析可以看到，PageRank算法本身存在一些不足之处。其中主要表现在主题漂移问题和时效性问题。

4.1主题漂移现象

在这里介绍一下普通权威网页和专业权威网页的区别。从PageRank算法很容易得知。假设高质量（PR值高）网页A都是关于“航空”的，那么就称这个网页为关于“航空”的专业权威网页。如果这个网页也用很小的部分顺带提到了“高铁”，那么就称这个网页是关于“高铁”的普通权威网页。假设网页B是“高铁”的相关权威网页，但是它的PR值相对网页A较低。假设某一用户要查询“高铁”的相关信息，很显然，网页B才是用户理想的访问网页，但是由于网页B的PR值小于网页A，网页A的排序会高于网页B，用户会更容易的抓到用处不大的网页A。

由于PageRank算法只是考虑了网页链接的结构分析，而忽略了网页内容与用户查询相关性以及相关程度的问题，这就导致了用户抓取了PR值很高的网页，但是该网页的内容并不是用户所需要的。这就是所谓的“主题飘移”问题。

4.2时效性问题

PageRank算法并没有对新旧网页进行区分，而是仅仅考虑了各网页之间的链接关系。然而一些新发布的网页是不会得到很多指向性链接的，因此新网页由PageRank算法计算出来的PR值往往很低。现代社会发展日新月异，往往一些新网页的内中里实时的讯息和资源比旧网页发布的更及时，但是因为旧网页的PR值要高于新网页，用户很容易就抓到旧网页，却很难抓到新网页。这就是PageRank算法的时效性问题。

5.总结和展望

总的来说，PageRank算法在Web结构分析领域占有重要地位，它已经成功的运用在了实际当中。但是也存在自身的一些缺陷，主要是会产生主题漂移现象以及时效性的问题。国内外的一些专家学者已经有不少人针这对两个问题对算法做出了一定的改进，但是到目前为止，还没有一个权威的、得到认可的结果。在各成果的基础上对上述问题继续进行研究