0
| 本文作者： 奕欣 | 2017-04-06 18:19 |
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 次。
想必所有人都不会想到，当年斯坦福大学的两个学生，只是抱着构建「一个更令人满意的搜索结果」系统的想法而开始研究，却在这个过程中造就了一家世界巨头公司。而如今雷锋网所报道和覆盖的每一篇论文，是否在未来也会成为力能扛鼎的学术经典？只有时间能给我们答案。
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
