谷歌网页排名算法

谷歌网页排名算法

Google并不是第一家搜索引擎公司,但后来却成为龙头行业,这其中PageRank算法发挥着重要的作用。

PageRank是Google创始人之一Larry Page发明的,今天我们就来一起瞻仰下大神的创作。

互联网上的每一个网页都可以看作一个顶点,每一个顶点都有出度和入度。

出度是指从这个网页能链接到的其他网页的数目,入度是指能链接到这个网页的其他网页的数目。

这样整个互联网中的所有网页的链接关系可以看成具有大量网页结点的有向图。

一个网页很重要最直观的感受就是有许多的网页链接到它,即它的入度大,并且重要性越高的网页链接它更能说明它越重要。

基于以上思想,我们首先量化网页的重要性,用PR值表示重要性,一个网页的PR值越大表明这个网页越重要。

PageRank的简化模型。

一个网页的PR值在一定程序上取决于它的入度,也和链接到它的网页本身的PR值有关,基于这个思想,计算任意一个网页的PR值的公式如下。

其中Bu是所有链接到u网页的网页集合,网页v属于集合Bu,L(v)是网页v的出度。

下面我们就用下图的网页链接关系举例。

假定A、B、C、D网页的初始PR值都为0.25,根据上面的计算公式,我们有如下的计算过程。

经过多次的迭代计算后,PR值逐渐稳定,即可认为PR值收敛。

从计算结果看出,B、D的PR值较高,这表明B、D的重要程度高,这也符合我们对图的直观感受。

但真实的网页链接关系复杂,这种简化的模型会面临以下两个问题。

1.排名泄漏。

如果有向图中有一个顶点的出度为0,即这个网页没有链接到其他的网页,则会出现排名泄漏问题。

以下图为例,A顶点的出度为0。

以此图的迭代计算过程如下。

出现这种问题的原因可以理解为A网页对整个网页没有PR值的贡献,因为它的出度为0,相反它还吸收其它网页对它PR值的贡献,导致整个网页的PR值越来越小。

2.排名下沉。

如果有向图中有一个顶点的入度为0,即没有其他网页链接到这个网页,则会出现排名下沉问题。

以下图为例,A顶点的入度为0。

因为A的入度为0,则在第一次迭代的时候A的PR值就为0,以后都为0。

为了解决简化模型出现的以上两个问题,PageRank的随机浏览模型应运而生。

PageRank的随机浏览模型。

随机浏览模型是符合用户上网行为的一种模型。

用户随机打开一个网页后,要么点击这个网页上的链接继续网页的浏览,要么随机转到另外的一个网页重新开始新一轮的浏览。

为此随机浏览模型引入了一个阻尼系数d来表示用户点击此网页上的链接继续浏览的概率,则1-d就是用户重新进行新一轮的浏览的概率。

引入阻尼系数d的计算公式如下。

其中N为整个网页的数目。

引入阻尼系数的效果为：在原有的有向图中添加了一个全链接的浏览关系,这样就完全解决了简化模型中出现的排名泄漏和排名下沉的问题。

如下图所示。

其中虚线就是随机浏览模型添加的全链接关系。