你的网站价值几何?让PageRank告诉你答案

2019-03-24 13:16:24来源: sqybi.com 阅读 ()

新老客户大回馈,云服务器低至5折

如果你安装过Google工具栏,如果你建立过独立博客或个人网站,那么你肯定和PageRank打过照面。而即使是从未考虑建站的读者,也有很大一部分听说过PageRank,毕竟作为Google搜索结果排序的重要依据[1],这个算法已经被广泛应用于网络的每一个角落。而PageRank值的大小,也早已与网站的SEO[2]成功与否紧密相连。

那么PageRank的名称从何而来?PageRank究竟如何准确表示网页重要度,它的算法又是如何高效准确运行的呢?在PageRank的背后,有什么数学理论的支持?且听笔者为您一一道来。

三个孩子和豌豆游戏

从前有一个死理性派老爸,他有三个孩子。老爸是个懒人,他在家里把三个孩子叫做老大、老二和老三。

一天,三个孩子正在玩游戏,老爸把他们叫到身边。“我这里有三十颗豌豆,”老爸说,“我们来用它们玩一个游戏,游戏结束之后按照游戏结果把豌豆分给你们,好不好啊?”

“好!”三个孩子异口同声地答应了。

“你们先在这张纸上写下你们喜欢的人,如果你认为另外两个兄弟你都很喜欢,那就把两个人的名字都写下来。比如我知道老二很喜欢老大,那么老二就在纸上写老大的名字。”

三个孩子很快写好了,然后老爸把纸收了上来。老大的纸上写了老二和老三的名字,而老二写了老大,老三写了老二。三个人互相喜欢的结果如图:

老爸清了一下嗓子,继续向孩子们解释规则:“接下来,我会给你们每个人分十颗豌豆。桌上有三个盘子,分别代表你们三个人,豌豆都放在盘子里。在我喊‘预备’的时候,你们要把盘子里的豌豆全都拿到手里。在我喊‘开始’的时候,你们要把手里的豌豆全部平均分给自己喜欢的人。”

老二举手:“那就是说,我每次都要把自己盘子里的豌豆全部拿起来,然后放到老大的盘子里吗?”

“没错,”老爸说,“老三和老大也类似。大家都明白规则了吗?”

三个孩子点头。“好,那游戏开始!”

一开始三个孩子盘子里豌豆的情况如图:

“预备!”妈妈喊到,“开始!”

三个孩子开始分配自己手中的豌豆。老二把十颗豌豆都给了老大;老三把十颗豌豆都给了老二;老大则是给老二和老三一人分配了五颗豌豆,如图:

三个孩子很快就麻利地分配好了自己手中的豌豆。这时三个人的盘子变成了这种情况:

老大有点不高兴了:“为什么我的豌豆比老二的还少啊?这个游戏不公平!”

老爸说:“这个游戏还没有结束。接下来我还会继续吹哨,你们也还要继续这个游戏,直到你们盘子里的豌豆数不再变化为止。公平不公平,到时候就能看出来了。”

老大虽然有点疑惑,不过还是点头同意了。

就这样,游戏一直进行下去。在下一轮的交换豌豆后,老大的盘子里有了15颗豌豆,老二有10颗,而老三只有五颗。当然故事在这里还没有结束,不过我们的描述要结束了。因为这个游戏将会持续很长很长时间——这点大概是死理性派老爸没有想到的。当然如果继续分下去,豌豆的数量将不再是整数,这一点我们也不深究了,游戏怎么能进行下去,就留给老爸想办法吧。

那么这个游戏最终的结果是什么样的呢?我们可以用电脑模拟这个过程,得出的结果是:老大和老二的盘子里各有12颗豌豆,而老三的盘子里有6颗豌豆。这时候无论游戏怎么进行下去,盘子里的豌豆数量都不会再变化。

网页排名和PageRank

在互联网刚刚发展的时代,人们曾经为网页的排名问题伤透脑筋。网页排名,顾名思义,就是为互联网上成千上万(当然,现在互联网上的网页数量已经不只是成千上万的程度了)的网页按照重要度进行排序。能够得知哪个网页更重要,对搜索引擎的发展十分有帮助——很显然,搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。

这个问题看起来很容易,但是解决的方法却没有想象的那么简单。

最初,一些比较流行的网页排名算法都很类似,它们都使用了一个非常简单的思想:越是重要的网页,访问量就会越大。于是,许多大公司就通过统计网页的访问量来进行网页排名。但是这种排名算法有两个很显著的问题:一是因为只能够抽样统计,所以统计数据不一定准确,而且访问量的波动会比较大,想要得到准确的统计需要大量的时间和人力,还只能维持很短的有效时间;二是访问量并不一定能体现网页的“重要程度”——可能一些比较早接触互联网的网民还记得,那时有很多人推出了专门“刷访问量”的服务。

有没有更好的方法,不统计访问量就能够为网页的重要度排序呢?在1999年,一篇以拉里•佩奇(Larry Page)为第一作者的论文[3]发表了。论文中介绍了一种叫做PageRank的算法,这种算法的主要思想是:越“重要”的网页,页面上的链接质量也越高,同时越容易被其它“重要”的网页链接。于是,算法完全利用网页之间互相链接的关系来计算网页的重要程度,终于摆脱了访问量统计的框框。

不过,不知道我们的死理性派老爸是不是了解,实际上刚刚他和孩子玩的游戏,就是PageRank算法的运行过程。

PageRank会给每个网页一个数值,这个数值越高,就说明这个网页越“重要”。而刚刚的游戏中,如果把豌豆的数量看作这个数值(可以不是整数),把孩子们看作网页,那么游戏的过程就是PageRank的算法,而游戏结束时豌豆的分配,就是网页的PageRank值。[4]

随机行走模型和马尔可夫过程

PageRank算法的思想基于“随机行走模型”(Random Walk Model)[5]。实际上,PageRank求解了这样一个问题:一个人在网络上浏览网页,每看过一个网页之后就会随机点击网页上的链接访问新的网页。如果当前这个人浏览的网页x已经确定,那么网页x上每个链接被点击的概率也是确定的,可以用向量Nx表示。在这种条件下,这个人点击了无限多次链接后,恰好停留在每个网页上的概率分别是多少?

在这个模型中,我们用向量Ri来表示点击了i次链接之后可能停留在每个网页上的概率(R0则为一开始就打开了每个网页的概率,后面可以看到R0的取值对最终结果没有影响)。很显然Ri的L1范式[4]为1,这也是PageRank算法本身的要求。

于是,整个浏览过程的一开始,我们有:

其中,A是一个表示每一次点击链接概率的矩阵。A的第i列第j行Ai, j的含义是,如果当前访问的网页是网页i,那么下一次点击链接跳转到网页j的概率为Ai, j。

这样设计矩阵A的好处是,通过矩阵A和向量Rn-1相乘,即可得出点击一次链接后每个网页可能的停留概率向量Rn。例如,令R1=AR0,可以得到点击一次链接后停留在每个网页的概率:

之后一直迭代下去,有:

对于以上例子,迭代结果如下图:

可以看到,每个网页停留的概率在振荡之后趋于稳定。

在这种稳定状态下,我们可以知道,无论如何迭代,都有Rn=Rn-1。这样我们就获得了一个方程:

而整个迭代的过程,就是在寻求方程R=AR的解。这也是为什么R0的取值对结果没有影响:无论R0是多少,迭代无限多次之后,一定会取得令R=AR成立的R值。整个求解R的过程,就如同一个人在一张地图上的不同位置之间随机地行走一样,所以被称为“随机行走模型”。

随机行走模型有一个显著的特点,那就是每一次迭代的结果只与前一次有关,与更早的结果完全无关。这种过程又被称为马尔可夫过程(Markov Process)或马尔可夫链(Markov Chain)[7]。

马尔可夫过程的数学定义是:如果对于一个随机变量序列X0、X1、X2、…,其中Xn表示时间n的状态及转移概率(transition possibility)P,有:

即Xn只受Xn-1的影响,则此过程成为马尔可夫过程。其中P(Xn+1|Xn)称作“一步转移概率”,而两步、三步转移概率则可以通过一步转移概率的积分求得。

当状态空间有限时,转移概率可以用用一个矩阵A来表示,称作转移矩阵(transition matrix)。此时转移概率的积分即为矩阵的幂,k步转移概率可以用Ak表示,这也是随机行走模型中的情况。而对于一个正的(每个元素都为正的)转移矩阵A,可以证明一定有:

这也解释了为什么在这段开始笔者提到,R0的取值对最终结果没有影响。

上述有限状态空间的马尔可夫过程只是马尔可夫过程的一个小分支。马尔可夫过程作为一种有效的随机过程模型,已经在更广泛的领域中得以应用。除了PageRank算法外,LZMA压缩算法[8]也使用了马尔可夫过程作为信号模型;此外,生物学和机器写作的领域都有马尔可夫过程的身影。

悬挂网页和个性化PageRank

不知道细心的读者发现没有,以上叙述的算法有时并不能解决问题——在某些情况下,算法的结果中有很多网页的PageRank都是0,甚至结果就是一个零向量。

这是为什么呢?其实,当一个网页只有链入链接没有链出链接的时候,这个网页就会像一个“黑洞”一样,将同一个连通子图中其它网页流向它的PageRank慢慢“吞掉”,这种网页我们称之为“悬挂网页”(Dangling Link)。此时的转移矩阵A,对于任意自然数n,An都不会是一个正的转移矩阵——A中对应着悬挂网页的位置永远是0。

为了解决这个问题,PageRank算法加入了一个新的向量E。它的作用是,按照其中所描述的比例来向全部网页分配悬挂网页每一次“吞掉”的PageRank。这样,相当于为悬挂网页添加了链向网络上全部网页的链接,避免了悬挂链接的出现。

E的取值如何确定呢?论文中提到,一般可以直接使用平均分配的方式把悬挂网页的PageRank分配给所有网页。但是,因为抓取的数据库通常是不完全的,所以悬挂网页的数量一般来说非常巨大,E的改变也会对PageRank的结果造成影响。于是,通过设定不同的E,我们就可以人为干预PageRank的结果。这样得到的PageRank,称作“个性化PageRank”(Personalized PageRank)。

事实上,这样的干预是很重要的。在PageRank算法的真正实现中,会增加一个常系数c,即:

以此来人为“制造”悬挂网页。

佩奇和“佩奇的排名”

之前提到过,PageRank算法的论文中,第一作者的名字叫做拉里•佩奇,即Larry Page。

佩奇是Google的创始人之一,现任Google的CEO。这里有一件很有意思的事情出现了:“佩奇”的英文是“Page”,恰好与“PageRank”的“Page”相吻合。这是巧合还是有意为之呢?

在网络上笔者可以找到的许多资料中,均提到PageRank是以拉里•佩奇的姓命名。但是所有这些资料都没有提到这条信息的来源,所以其真实性无从得证。

不过,既然佩奇本人没有出来解释,那我们也没有必要纠结于Page的含义了。或许这个词本身就是佩奇利用双关语向我们开的一个小玩笑呢!

脚注与参考资料

[1] 虽然PageRank是Google搜索结果排序的重要依据,不过它并不是全部依据——实际上,Google用了数百种不同的算法来确定最终显示给用户的搜索结果顺序。

[2] SEO,即Search Engine Optimization,意为搜索引擎优化,主要是将网站的内容、布局等针对搜索引擎进行优化,使得页面更容易在搜索结果上被显示。

[3] L. Page, S. Brin, R. Motwani and T. Winograd. The PageRank Citation Ranking: Bring Order to the Web. Jan, 1998.

[4] 这里的描述不是非常准确:首先,在PageRank的算法中,要求结果向量的L2范式为1,所以需要将每个孩子的豌豆数量减少到例子中的1/30;另外,我们看到的网页PageRank值,实际上是通过对算法的结果求对数得到的。但算法的本质没有大的不同,所以这里不再赘述。

[5] 随机行走模型,来自Wikipedia:http://en.wikipedia.org/wiki/Random_walk

[6] 向量的L1范式,即向量中每一项的绝对值之和。

[7] 马尔可夫过程,来自Wikipedia:http://en.wikipedia.org/wiki/Markov_chain

[8] LZMA算法,来自Wikipedia:http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm

原文地址:http://sqybi.com/blog/archives/359

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:解决Wordpress报错“Warning: Cannot modify header information

下一篇:搜索重新定位的十大优点