2017 年的The Seoul Test-of-Time Award 頒給了《Graph Structure in the Web》，這可謂是實(shí)至名歸。

雷鋒網(wǎng)了解到， Seoul Test-of-Time Award 是國際萬維網(wǎng)大會上特設(shè)的一個獎項(xiàng)，主要是為了表彰多年來對科學(xué)，技術(shù)或社會產(chǎn)生了重大影響的論文。

根據(jù)維基百科的介紹，在韓國首爾舉行的 WWW 2014 時，組委會決定在下一年的 WWW 大會上評選這一獎項(xiàng)，因而得名“The Seoul Test-of-Time Award ”。

《Graph Structure in the Web》這篇論文最初發(fā)表于 2000 年的第九屆 WWW 上，論文指出了「萬維網(wǎng)的圖表結(jié)構(gòu)」，堪稱開創(chuàng)性研究。論文作者包括谷歌的 Andrei Broder, IBM 的 Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan 和 Andrew Tomkins，以及合作成員 Farzin Maghoul, Raymie Stata 和 Janet Wiener。

彼時，它已經(jīng)在 WWW 大會上獲得了最佳論文獎，并在接下來的 17 年里呈現(xiàn)它非凡的影響力，在 ACM Digital Library 上的累計(jì)引用次數(shù)超過 3500 次。

那么這篇論文到底有何經(jīng)典之處呢？雷鋒網(wǎng)了解到，本文對互聯(lián)網(wǎng)結(jié)構(gòu)的研究做出了兩個重要的貢獻(xiàn)。

首先，它進(jìn)行的大規(guī)模實(shí)驗(yàn)，顯示 Web 節(jié)點(diǎn)是根據(jù)冪律分布的。也就是說，Web 的節(jié)點(diǎn)具有 i 個傳入鏈接的概率大致與 1/i2.1 成正比。

其次，與以前幾乎全連接的 Web 研究不同的是，論文描述的是一種更加復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，也就是如今非常標(biāo)志性的「弓箭」（bowtie）狀（如圖所示）：

作者提出了一個精簡的 Web 圖形模型，并描述了 Web 頁面的幾個特征：

• 強(qiáng)連接的核心組件：每個頁面都可以從任意其它頁面訪問；

• IN/OUT 簇：也就是說，它只具有到核心或來自核心的單向路徑；

• 兩簇之間以卷須（tendrils）連接，還有其它繞過核心與簇連接的通道，還有與其它部分完全隔絕的組件。

• 核心組件是全連接的，每個節(jié)點(diǎn)都能從任何節(jié)點(diǎn)到達(dá)。

作者 Broder 等人發(fā)現(xiàn)，比起以往的研究，實(shí)際上 Web 的結(jié)構(gòu)更加松散，而任何兩個給定頁面的互連概率少于 1/4。

有意思的是，這個 1999 年完成的研究是通過兩個 Altavista 爬蟲爬行了 2 億個頁面與 15 億個鏈接而得到的。而今天，谷歌僅僅在 App 里就需要索引超過 1000 億條連接，爬蟲需要處理超過 130 億個網(wǎng)址。

而 Broder 等人提出的 Web 宏觀結(jié)構(gòu)為大量的爬蟲及搜索網(wǎng)絡(luò)研究提供了堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，也對現(xiàn)代搜索引擎架構(gòu)產(chǎn)生了深遠(yuǎn)影響。

值得一提的是，首屆「Seoul Test-of-Time Award」于 2015 年頒給了谷歌的創(chuàng)始人 Larry Page 和 Sergey Brin，以紀(jì)念他們在 1998 年第七屆 WWW 大會上發(fā)表的論文《The Anatomy of a Large-Scale Hypertextual Web Search Engine》。

這篇論文正是 Google 的孕育之地，兩人在論文中提及：

「我們選擇 Google 作為系統(tǒng)的名字，它是數(shù)學(xué)大數(shù)『googol』的常見的一個錯誤拼寫，即 10100，我們也希望能夠構(gòu)建一個覆蓋海量信息的搜索系統(tǒng)」也就是說，WWW 大會實(shí)際上也是谷歌首度正式亮相的舞臺。

Google 是一個大范圍搜索引擎原型，通駝有效地抓取及索引 Web 頁面，產(chǎn)生比現(xiàn)有系統(tǒng)更加令人滿意的搜索結(jié)果。設(shè)計(jì)一個搜索引擎在當(dāng)時具有其必要性：

• 網(wǎng)絡(luò)頁面的大量增長讓用戶通常采用 Yahoo！這樣的上網(wǎng)導(dǎo)航網(wǎng)站，但存在的缺點(diǎn)在于網(wǎng)站的選擇具有主觀性，構(gòu)建與維護(hù)網(wǎng)站需要大量成本，而且更新時效慢，也無法覆蓋「蘿卜青菜，各有所愛」的大眾口味。

• 而當(dāng)時依賴關(guān)鍵詞的搜索引擎則有著良莠不齊的搜索結(jié)果，這也催生了 Larry Page 和 Sergey Brin 兩人想做一個更完善的搜索引擎的想法。

這篇論文提出了兩個重要的觀點(diǎn)：

• 首先是在廉價(jià)的硬件上搭建一個分布式系統(tǒng)，以處理大規(guī)模指數(shù)；

• 其次，他們使用了 Web 的超鏈接結(jié)構(gòu)作為一種有效的關(guān)聯(lián)信號。

到如今，這兩個想法已經(jīng)非常普及，而谷歌也成為了世界上最被廣泛使用的搜索引擎之一，而這篇論文所產(chǎn)生的學(xué)術(shù)影響卻依然存在：截至 2015 年，它的引用次數(shù)超過了 13000 次，而兩年之后的今天，雷鋒網(wǎng)了解到，這個數(shù)字達(dá)到了 15916 次。

想必所有人都不會想到，當(dāng)年斯坦福大學(xué)的兩個學(xué)生，只是抱著構(gòu)建「一個更令人滿意的搜索結(jié)果」系統(tǒng)的想法而開始研究，卻在這個過程中造就了一家世界巨頭公司。而如今雷鋒網(wǎng)所報(bào)道和覆蓋的每一篇論文，是否在未來也會成為力能扛鼎的學(xué)術(shù)經(jīng)典？只有時間能給我們答案。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。