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

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

AI 科技评论了解到, 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 次。

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

首先,它进行的大规模实验,显示 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 次,而两年之后的今天,AI科技评论了解到,这个数字达到了 15916 次。

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

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-04-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据派THU

干货收藏 | 计算机学习绝对不能错过的10大网站(内附网站链接)

本文整理出大数据和人工智能领域最实用,质量最高的10大技术网站信息,既可以用于丰富技术知识,也可以用于学术研究。

482
来自专栏AI研习社

谷歌开源 FHIR 标准协议缓冲工具,利用机器学习预测医疗事件

在上月 26 日,谷歌在 arXiv 上发表的一篇论文《Scalable and accurate deep learning for electronic h...

3157
来自专栏企鹅号快讯

Hinton:5-10年内深度学习取代放射科医生

2017年4月,Hinton在接受《纽约客》采访时说:“5年内深度学习就能超过放射科医生,从现在起就停止培训放射科医生”。此言论一出,再一次引发全球关于AI正在...

1896
来自专栏ATYUN订阅号

MIT开发算法使无人机等时效性强的设备可以获得最新的数据

对于即时共享时效性强的信息的无线网络,光是快速传输数据是不够的,这些数据要尽可能新。考虑一下你车内的诸多传感器,尽管大多数传感器将数据包传输到中央处理器可能需要...

844
来自专栏mwangblog

组块构建——《学习之道》(Barbara Oakley)读书笔记二

高质量的组块构成的神经模型,不仅能与我们钻研的学科产生共鸣,也能在其他学科或生活领域产生反响。

942
来自专栏点点滴滴

Western Blot一抗的选择

2322
来自专栏AI科技评论

动态 | 谷歌开源FHIR标准协议缓冲工具,利用机器学习预测医疗事件

AI科技评论按:在上月 26 日,谷歌在 arXiv 上发表的一篇论文《Scalable and accurate deep learning for elec...

2906
来自专栏大数据挖掘DT机器学习

Microsoft 时序算法——结果预算+下期彩票预测篇)

前言 本篇我们将总结的算法为Microsoft时序算法的结果预测值,是上一篇文章Microsoft时序算法的一个总结,上一篇我们已经基于微软案例数据库的销售历史...

4865
来自专栏人人都是极客

如何利用树莓派打造一款机器人

作者/刘端阳,清华大学aminer.org研究者社交网络系统的R&D,参与过智谷睿拓公司(已经被小米收购)的专利挖掘,在大数据征信领域创业过,出过一本叫做《树莓...

4597
来自专栏DT数据侠

一场危险的手机WiFi连接数据“试验”:世界之大,你无所遁形!

人人“机不离手”的这个时代,你能想象下一旦没了WiFi世界会怎样吗?WiFi使用越来越普遍,基于WiFi使用相关的数据研究也多了起来。

730

扫码关注云+社区