第 13 周命题作业：PageRank 算法

PageRank算法受到了论文影响力因子的评价启发。当一篇论文被引用的次数越多，证明这篇论文的影响力越大。这个算法解决了当时网页检索质量不高的问题。



PageRank算法计算一个页面的排名主要是看两个方面，出链和入链。出链指的是从这个页面指向其他页面的链接，入链指的是从其他页面指向这个页面的链接。当一个页面通过出链跳转到其他页面相当于对其他页面进行投票，其他页面通过入链跳转到这个页面，相当于对这个页面投票。当一个页面的票数越高，它的排名就越高。



那么PageRank算法具体是怎么计算页面的票数呢？下面用一个例子来说明。

假设有A,B,C,D 四个页面，他们之间的链接关系如图所示。





各个页面到其他页面的链接数用图表示如下



假设每个页面开始的时候都有1票，如果页面有3个出链，那么每个出链就会获得1/3票。下面的图表，行表示一个页面获得票的情况，列表示一个页面投出票的情况。无论页面的票数怎么变化，只要页面的出链和入链没有变化，这个分配票的比例就不会变化。





这里我们定义向页面的所有出链投票为一轮投票。假设每个页面初始有1票，那么经过一轮投票之后，每个页面的票数如下 A 1.5 B 5/6 C 5/6 D 5/6。这个票数是怎么计算出来的呢？我们可以看到，用上面的分票比例乘以每个页面现在的票数就可以了。已页面A为例，看A的那一行，页面A的票数=0*1+1/2*1+1*1+0*1=1.5。第二轮投票用第一次投票后每个页面的票数乘以分票比例也可以计算出来。经过多次投票，每个页面的票数会趋于一个稳定值, 从而可以得到一个页面的最终得票。



但是这样的算法会存在两个问题：

1）等级泄露（Rank Leak）如果一个网页没有出链，就像是一个黑洞一样，吸收了其他网页的票数而不释放，最终会导致其他网页的票数 为 0

2）等级沉没（Rank Sink）：如果一个网页只有出链，没有入链，计算的过程迭代下来，会导致这个网页的 票数值为 0。



要解决这两个问题，需要使用PageRank的随机浏览模型来计算各个页面的票数。那么随机模型是什么呢？随机模型可以理解为不点击链接进行投票，而是直接输入网址进行访问。在实际的上网过程中，也是有这种情况发生的，虽然出现的概率不高。随机模型设计一个阻尼因子d的概念，用阻尼因子d这个参数来表示直接输入网址进行访问的出现的概率，阻尼因子d的值被设定为0.15。使用阻尼因子可以一定程度上解决等级泄漏和等级沉没的问题。