学界 | 继佩奇和布林的开山论文之后,谷歌团队又有哪篇经典入了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 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

为什么在VR中投掷体验很差——怎样改善它

1411
来自专栏新智元

【永久免费使用谷歌GPU】英伟达可能要发布专用于挖矿的GPU

新智元编译 来源:Hackernoon 作者:Nick Bourdakos 编译:刘小芹、克雷格 【新智元导读】用CPU训练机器学习模型太耗时但GPU又...

3137
来自专栏AI科技大本营的专栏

TensorFlow 1.0 正式发布

在刚刚过去的一年里,从语言翻译到对皮肤癌的早期检测和对糖尿病患者失明的防护,TensorFlow 对研究人员,工程师,艺术家,学生和其他各界人士在各领域的进步都...

34313
来自专栏大数据文摘

谷歌首届TensorFlow开发者峰会 重磅发布TensorFlow 1.0 | 附主题演讲视频

1393
来自专栏新智元

深度学习动手实践:用 TensorFlow 打造“会看”的机器人

(文/Lukas Biewald)物体识别是当前机器学习最热门的方向。计算机早已能够识别如人脸、猫之类的物体,但识别更大范围里的任意物体对人工智能来说仍是难题。...

4326
来自专栏机器之心

业界 | DeepWarp:一款可以玩转所有人眼球的机器学习Demo

选自the verge 作者:Lizzie Plaugic 机器之心编译 参与:黄小天 最近发生了一件互联网趣事:一款可以操控面部表情的神经网络 Demo——D...

34411
来自专栏AI研习社

普林斯顿联合Adobe 连声音都能PS了 | 2分钟读论文

来源 / Two Minute Papers 翻译 / 季伟 校对 / 贤儿响叮当 整理 / 雷锋字幕组 AI 研习社出品系列短视频《 2 分钟论文 》,带大...

2764
来自专栏玉树芝兰

如何用Python从海量文本抽取主题?

你在工作、学习中是否曾因信息过载叫苦不迭?有一种方法能够替你读海量文章,并将不同的主题和对应的关键词抽取出来,让你谈笑间观其大略。本文使用Python对超过10...

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

基于微软案例数据库数据挖掘知识点总结(结果预测篇)

前言 本篇文章主要是继续前几篇Microsoft决策树分析算法、Microsoft聚类分析算法、Microsoft Naive Bayes 算法,算法介绍后,经...

2926
来自专栏量子位

现在,TensorRT 4开放下载了

772

扫码关注云+社区