新知丨纯粹的搜索排名是怎样的？
近日魏则西事件的震惊四座，再一次将长期存在于百度搜索中的医疗健康类关键词竞价排名的行为推上舆论的风口浪尖。关...
近日魏则西事件的震惊四座，再一次将长期存在于百度搜索中的医疗健康类关键词竞价排名的行为推上舆论的风口浪尖。关键词搜索里充满了商业推广行为，这是否还是一个正常的搜索引擎？一个正常的搜索引擎，其核心功能自然是网页搜索。百度在这点上，还是要向Google学习。
抛开类似百度渗透了商业行为的排名，搜索排名背后有一套完整而复杂的算法，在13年前，拉里•佩奇( Larry Page )和谢尔盖•布林( Sergey Brin )正是依靠先进的算法发家并创立谷歌的。
★
网页排名和谷歌算法的诞生
搜索结果应该怎样排序才最好呢？实际上，在谷歌主导互联网搜索之前，人们为此伤透脑筋。
当时人们认为，通过判断能够得知哪个网页更重要，对搜索引擎的发展十分有帮助——很显然，搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。
这个问题看起来很容易，但是解决的方法却没有想象的那么简单。
在谷歌诞生之前那段时间，流行的网页排名算法都很类似，它们都使用了一个非常简单的思想：越是重要的网页，访问量就会越大。许多大公司就通过统计网页的访问量来进行网页排名。但是这种排名算法有两个很显著的问题：一是因为只能够抽样统计，所以统计数据不一定准确，而且访问量的波动会比较大，想要得到准确的统计需要大量的时间和人力，还只能维持很短的有效时间；二是访问量并不一定能体现网页的“重要程度”——可能一些比较早接触互联网的网民还记得，那时有很多人推出了专门“刷访问量”的服务。有没有更好的方法，不统计访问量就能够为网页的重要度排序呢？
就是在这种情况下,1996 年初，谷歌公司的创始人，当时还是美国斯坦福大学研究生的佩奇和布林开始了对网页排序问题的研究。在1999年，一篇以佩奇为第一作者的论文发表了，论文中介绍了一种叫做 PageRank 的算法，这种算法的主要思想是：越“重要”的网页，页面上的链接质量也越高，同时越容易被其它“重要”的网页链接。于是，算法完全利用网页之间互相链接的关系来计算网页的重要程度，将网页排序彻底变成一个数学问题，终于摆脱了访问量统计的框框。
三个孩子和豌豆游戏
在详细讲述这个算法之前，不妨让我们用一个游戏，先来简单模拟一下 PageRank 算法的运行过程，以便读者更好地理解。
三兄弟分 30 颗豌豆。起初每人 10 颗，他们每次都要把手里的豌豆全部平均分给自己喜欢的人。下图表示了三兄弟各自拥有的初始豌豆数量，以及相互喜欢的关系（箭头方向表示喜欢，例如老二喜欢老大，老大喜欢老二和老三）。
那么这个游戏到底是否可以结束呢，如果可以，最终的结果又是什么样的？在此我们用电脑模拟了这个过程，得出的结果是：老大和老二的盘子里各有 12 颗豌豆，而老三的盘子里有 6 颗豌豆。这时候无论游戏怎么进行下去，盘子里的豌豆数量都不会再变化。
看到这里，读者可能会问：这个游戏和网页排序有什么关系？实际上， PageRank 会给每个网页一个数值，这个数值越高，就说明这个网页越“重要”。而刚刚的游戏中，如果把豌豆的数量看作这个数值（可以不是整数），把孩子们看作网页，那么游戏的过程就是 PageRank 的算法，而游戏结束时豌豆的分配，就是网页的 PageRank 值。
★
PageRank的数学模型不同于之前的访问量统计，PageRank 求解了这样一个问题：一个人在网络上浏览网页，每看过一个网页之后就会随机点击网页上的链接访问新的网页。如果当前这个人浏览的网页 x 已经确定，那么网页 x 上每个链接被点击的概率也是确定的，可以用向量 Nx 表示。在这种条件下，这个人点击了无限多次链接后，恰好停留在每个网页上的概率分别是多少？
在这个模型中，我们用向量 Ri 来表示点击了 i次链接之后可能停留在每个网页上的概率， R0 则为一开始就打开了每个网页的概率，在一系列证明后（这个过程实在有点复杂，略去），得到 R0 的取值对最终结果没有影响。
修正“悬挂网页”带来的不良影响
但是这里有一个问题：即便 R0 的取值对最终结果没有影响，用 R 作为网页排序的依据是否真的合理？
其实并不合理，因为当一个网页只有链入链接没有链出链接的时候，这个网页就会像一个“黑洞”一样，将同一个连通子图中其它网页流向它的 PageRank 慢慢“吞掉”（因为算法中虚拟的用户一旦进入那样的网页， 就会由于没有对外链接而永远停留在那里），这种网页我们称之为“悬挂网页”（ Dangling Link ）。这种“黑洞”效应是如此显著， 以至于在一个连通性良好的互联网上， 哪怕只有一个 “悬挂网页”， 也足以使整个互联网的网页排序失效， 可谓是 “一粒老鼠屎坏了一锅粥”。
为了解决这个问题，佩奇和布林进行了修正。他们意识到， 当用户访问到 “悬挂网页” 时， 都不可能也不应该就停留在了这个页面， 而是会自行访问其它网页。虽然对每个用户来说， 自行访问的网页与各人的兴趣有关，但在平均意义上来讲，佩奇和布林假定用户将会在整个互联网上随机选取一个网页进行访问。
所以他们给 PageRank 算法加入了一个新的向量 E。它的作用是，按照其中所描述的比例来向全部网页分配悬挂网页每一次“吞掉”的 PageRank。这样，相当于为悬挂网页添加了链向网络上全部网页的链接，避免了悬挂链接的出现。
以上就是谷歌背后最重要的数学奥秘。 与以往那种凭借关键词出现次数所作的排序不同， 这种由所有网页的相互链接所确定的排序是不那么容易做假的， 因为做假者再是把自己的网页吹得天花乱坠， 如果没有真正吸引人的内容， 别人不链接它， 一切就还是枉然。 而且 “佩奇排序” 还有一个重要特点， 那就是它只与互联网的结构有关， 而与用户具体搜索的东西无关。 这意味着排序计算可以单独进行， 而无需在用户键入搜索指令后才临时进行。 谷歌搜索的速度之所以快捷， 在很大程度上得益于此。
结语
不过要强调的是，虽然PageRank是Google搜索结果排序的重要依据并以此发家，不过它并不是全部依据——实际上，Google发展到现在，已同时用了数百种不同的算法来确定最终显示给用户的搜索结果顺序。
关于PageRank还有一个小故事。拉里•佩奇是Google的创始人之一，也是现任Google的CEO。有意思的是：“佩奇”的英文是“Page”，恰好与“PageRank”的“Page”相吻合。这是巧合还是有意为之呢？在网络上笔者可以找到的许多资料中，均提到PageRank是以拉里•佩奇的姓命名。但是所有这些资料都没有提到这条信息的来源，所以其真实性无从得证。
不过，既然佩奇本人没有出来解释，那我们也没有必要纠结于Page的含义了。或许这个词本身就是佩奇利用双关语向我们开的一个小玩笑呢！
百度作为商业公司要挣钱的行为能理解，但是在重要关键词，比如有关生老病死的话题上，还是要严把关，按科学的排名算法来，不然造成的危害将难以估量。
关注 浙大光电
微信扫一扫关注公众号
