幸运飞艇:继佩奇和布林的开山论文之后,谷歌团队又有哪篇经典入

继佩奇和布林的开山论文之后,谷歌团队又有哪篇经典入了WWW大会的法眼?

2017 年的The Seoul Test-of-Time Award 颁给了《Graph Structure in the Web》,这可谓是实至名归。

了解到, Seoul Test-of-Time Award 是国际万维网大会上特设的一个奖项,主要是为了表彰多年来对科学,技术或社会产生了重大影响的论文。

根据维基百科的介绍,在韩国首尔举行的 WWW 2014 时,组委会决定在下一年的 WWW 大会上评选这一奖项,因而得名“The Seoul Test-of-Time Award ”。

《Graph Structure in the Web》这篇论文最初发表于 2000 年的第九届 WWW 上,论文指出了「万维网的图表结构」,堪称开创性研究。论文作者包括谷歌的 Andrei Broder, IBM 的 Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan 和 Andrew Tomkins,以及合作成员 Farzin Maghoul, Raymie Stata 和 Janet Wiener。

彼时,它已经在 WWW 大会上获得了最佳论文奖,并在接下来的 17 年里呈现它非凡的影响力,在 ACM Digital Library 上的累计引用次数超过 3500 次。

那么这篇论文到底有何经典之处呢?了解到,本文对互联网结构的研究做出了两个重要的贡献。

首先,它进行的大规模实验,显示 Web 节点是根据幂律分布的。也就是说,Web 的节点具有 i 个传入链接的概率大致与 1/i2.1 成正比。

其次,与以前几乎全连接的 Web 研究不同的是,论文描述的是一种更加复杂的网络结构,也就是如今非常标志性的「弓箭」(bowtie)状(如图所示):

作者提出了一个精简的 Web 图形模型,并描述了 Web 页面的几个特征:

  • 强连接的核心组件:每个页面都可以从任意其它页面访问;

  • IN/OUT 簇:也就是说,它只具有到核心或来自核心的单向路径;

  • 两簇之间以卷须(tendrils)连接,还有其它绕过核心与簇连接的通道,还有与其它部分完全隔绝的组件。

  • 核心组件是全连接的,每个节点都能从任何节点到达。

作者 Broder 等人发现,比起以往的研究,实际上 Web 的结构更加松散,而任何两个给定页面的互连概率少于 1/4。

有意思的是,这个 1999 年完成的研究是通过两个 Altavista 爬虫爬行了 2 亿个页面与 15 亿个链接而得到的。而今天,谷歌仅仅在 App 里就需要索引超过 1000 亿条连接,爬虫需要处理超过 130 亿个网址。

而 Broder 等人提出的 Web 宏观结构为大量的爬虫及搜索网络研究提供了坚实的数学基础,也对现代搜索引擎架构产生了深远影响。

值得一提的是,首届「Seoul Test-of-Time Award」于 2015 年颁给了谷歌的创始人 Larry Page 和 Sergey Brin,以纪念他们在 1998 年第七届 WWW 大会上发表的论文《The Anatomy of a Large-Scale Hypertextual Web Search Engine》。

这篇论文正是 Google 的孕育之地,两人在论文中提及:

「我们选择 Google 作为系统的名字,它是数学大数『googol』的常见的一个错误拼写,即 10100,我们也希望能够构建一个覆盖海量信息的搜索系统」也就是说,WWW 大会实幸运飞艇开奖结果官网际上也是谷歌首度正式亮相的舞台。

Google 是一个大范围搜索引擎原型,通驼有效地抓取及索引 Web 页面,产生比现有系统更加令人满意的搜索结果。设计一个搜索引擎在当时具有其必要性:

  • 网络页面的大量增长让用户通常采用 Yahoo!这样的上网导航网站,但存在的缺点在于网站的选择具有主观性,构建与维护网站需要大量成本,而且更新时效慢,也无法覆盖「萝卜青菜,各有所爱」的大众口味。

  • 而当时依赖关键词的搜索引擎则有着良莠不齐的搜索结果,这也催生了 Larry Page 和 Sergey Brin 两人想做一个更完善的搜索引擎的想法。

这篇论文提出了两个重要的观点:

  • 首先是在廉价的硬件上搭建一个分布式系统,以处理大规模指数;

  • 其次,他们使用了 Web 的超链接结构作为一种有效的关联信号。

到如今,这两个想法已经非常普及,而谷歌也成为了世界上最被广泛使用的搜索引擎之一,而这篇论文所产生的学术影响却依然存在:截至 2015 年,它的引用次数超过了 13000 次,而两年之后的今天,(公众号:)了解到,这个数字达到了 15916 次。

想必所有人都不会想到,当年斯坦福大学的两个学生,只是抱着构建「一个更令人满意的搜索结果」系统的想法而开始研究,却在这个过程中造就了一家世界巨头公司。而如今所报道和覆盖的每一篇论文,幸运飞艇开奖结果官网是否在未来也会成为力能扛鼎的学术经典?只有时间能给我们答案。

原创文章,未经授权禁止转载。详情见转载须知。