week13 homework

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

Google 搜索引擎是通过网页排名算法 PageRank 算法来对网页搜索结果进行排序的。 PageRank 算法主要是通过网页之间的链接关系来进行计算。

类比一个常见的例子（例子仅为假设），微博粉丝关注，如何判断一个人的名气高。不能简单通过其粉丝数量来判断，因为有可能有些粉丝是僵尸粉，不具有判断意义。因此，需要通过判断一个人的粉丝是不是也被多人关注。比如，杨幂被胡歌关注，胡歌拥有很大的粉丝量，那说明杨幂具有很高的影响力。



但是，这种做法也会有问题。

第一种情况是，比如，马云被杨幂、邓伦以及其他很多名人关注，但是马云不关注别人，这样可能导致马云的影响力无穷大，而使杨幂、邓伦等人失去影响力。这种情况称为：等级泄露（Rank Leak）。



第二种情况是，比如，蔡徐坤是新人，一有微博就关注了杨幂、胡歌和邓伦，但是没有名人关注他，这样可能导致蔡徐坤失去影响力。这种情况称为：等级沉没（Rank Sink）。



为了避免上述情况的发生，可以设定微博认证，只要有微博认证，就给认证人员添加初始影响力 d，这样可以一定程度的避免等级泄露和等级沉默事件的发生。

上述例子放到网页搜索中也一样。

利用网页之间的相互链接来判断一个网页的排名，等级泄露代表一个网页只有入链没有出链，等级沉默代表一个网页包含了其他页面的链接，却没有页面指向他，因此，可以想象一个人有一定的概率直接通过网址跳转到页面，并且跳转到每个页面的概率是一样的。这个过程的具体计算公式为：



其中，其中 N 为网页总数，d为阻尼比，通常为0.85。u 为待评估的页面，Bu​ 为页面 u 的入链集合。针对入链集合中的任意页面 v，它能给 u 带来的影响力是其自身的影响力 PR(v) 除以 v 页面的出链数量，即页面 v 把影响力 PR(v) 平均分配给了它的出链，这样统计所有能给 u 带来链接的页面 v，得到的总和就是网页 u 的影响力，即为 PR(u)。