網(wǎng)絡科學三大里程碑

方錦清

追溯網(wǎng)絡科學發(fā)展的軌跡，網(wǎng)絡科學發(fā)展史有過三大里程碑，每個里程碑無一不是從網(wǎng)絡的理論模型首先取得突破的。國際上提出的經(jīng)典理論模型最著名的有：歐拉圖論、ER隨機圖以及小世界模型和無標度模型?？茖W界迄今已經(jīng)積累了許多有價值的理論模型，開展了許多實際網(wǎng)絡的研究，基本揭開了復雜網(wǎng)絡的廬山真面目，使人們了解到其復雜性與簡單性、多樣性與普適性之間錯綜復雜的關系。

第一個里程碑：歐拉圖論

網(wǎng)絡科學首先是得益于圖論和拓撲學等應用數(shù)學的發(fā)展。歷史上，多位杰出數(shù)學家各自獨立地建立和研究過圖論，他們的貢獻功不可沒。所謂圖論就是由一些點按照一定方式連線組成的一個圖(集合)。關于圖論的文字記載最早出現(xiàn)在1736年瑞士數(shù)學家歐拉的論著中，他所考慮的原始問題具有很強的實際背景，那就是著名的哥尼斯堡七橋問題。

哥尼斯堡是當時東普魯士的首都，今俄羅斯加里寧格勒市，普萊格爾河橫貫其中，這條河上建有七座橋，將河中間的兩個島和河岸聯(lián)結(jié)起來。人們閑暇時經(jīng)常在這上邊散步，有人提出：能不能每座橋都只走一遍，最后又回到原來的位置。這個看起來很簡單卻很有趣的問題吸引了大家，很多人在嘗試各種各樣的走法，然而無數(shù)次的嘗試都沒有成功。

1736年，有人帶著這個問題找到了當時的大數(shù)學家歐拉，歐拉經(jīng)過一番思考，很快就用一種獨特的方法給出了解答。他把兩座小島和河的兩岸分別看作四個點，而把七座橋看作這四個點之間的連線，如圖所示，A、B、C、D表示陸地。于是這個問題就簡化成，能不能用一筆就把這個圖形畫出來。經(jīng)過進一步的分析，歐拉得出結(jié)論：不可能每座橋都走一遍，最后回到原來的位置，并且給出了所有能夠一筆畫出來的圖形所應具有的條件。這項工作使歐拉成為圖論(及拓撲學)的創(chuàng)始人。

歐拉的研究開創(chuàng)了圖論這門新的數(shù)學分支，歐拉因此被譽為“圖論之父”。這是第一代科學家對網(wǎng)絡科學的開創(chuàng)性貢獻。

1859年，英國數(shù)學家哈密頓發(fā)明了一種游戲：用一個規(guī)則的實心十二面體，它的20個節(jié)點標出世界著名的20個城市，要求游戲者找一條沿著各邊通過每個節(jié)點剛好一次的閉回路，即“繞行世界”。用圖論的語言來說，游戲的目的是在十二面體的圖中找出一個生成圈。這個問題后來就叫做哈密頓問題。由于運籌學、計算機科學和編碼理論中的很多問題都可以化為哈密頓問題，從而引起國際上廣泛的注意和研究。

在圖論的歷史中，還有一個最著名的問題——四色猜想，它也是世界近代三大數(shù)學難題之一。首先提出四色猜想的人是英國人弗南西斯·格思里，他在給地圖著色時，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色?！?878～1880年兩年間，著名律師兼數(shù)學家肯普和泰勒兩人分別提交了證明四色猜想的論文。但后來數(shù)學家赫伍德以自己的精確計算指出肯普的證明是錯誤的。不久，泰勒的證明也被人們否定了。于是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。所以它對圖的著色理論、平面圖理論、代數(shù)拓撲圖論等分支的發(fā)展起到推動作用。進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。電子計算機問世以后，由于演算速度迅速提高，加之人機對話的出現(xiàn)，大大加快了對四色猜想證明的進程。1976年，美國數(shù)學家阿佩爾與哈肯在美國伊利諾斯大學的兩臺不同的電子計算機上，用了1200個小時，作了i00億判斷，終于完成了四色定理的證明。當然，不少數(shù)學家還在探索一種更簡捷明快的書面證明方法。

在拓撲學的發(fā)展歷史中，還有一個著名而且重要的關于多面體的定理也和歐拉有關。因此，歐拉開創(chuàng)的圖論(現(xiàn)在稱為網(wǎng)絡科學理論)，當之無愧地處于網(wǎng)絡金字塔的最頂端。

第二個里程碑：ER隨機圖理論

在20世紀五六十年代，兩個匈牙利著名的數(shù)學家愛多士(Erdos)和瑞尼(Renyi)又一次對圖論(網(wǎng)絡科學理論)作出了第二個里程碑式的貢獻，他們建立了著名的隨機圖理論，用相對簡單的隨機圖來描述網(wǎng)絡，簡稱ER隨機圖理論。用圖論的語言和符號可以精確簡潔地加以描述各種網(wǎng)絡，圖論不僅為數(shù)學家和物理學家提供了描述網(wǎng)絡的共同語言和研究平臺，而且至今圖論的許多研究成果、結(jié)論和方法技巧仍然能夠自然地應用到現(xiàn)在復雜網(wǎng)絡的研究中去，成為網(wǎng)絡研究的有力方法和工具之一。

愛多士被稱為20世紀的歐拉，于1984年獲得沃爾夫獎。他的一生充滿著傳奇色彩，一無財產(chǎn)、二無妻小、三無固定居所，完全是一個數(shù)學“苦行僧”。他善于與人合作，打破了數(shù)學領域的喜歡個人獨立研究的傳統(tǒng)，一生有480多個合作者，留下約1475篇文章，還與那些偉大的理論物理學家和數(shù)學家，如愛因斯坦、哥德爾、奧本海默等有密切的學術交往。

第三個里程碑：小世界現(xiàn)象與無標度特性

1998年，網(wǎng)絡科學又一次取得突破性進展，出現(xiàn)了第三個里程碑。美國的瓦茨和斯特羅加茨首先沖破了ER理論的框框，發(fā)表了題為《“小世界”網(wǎng)絡的群體動力行為》的論文，他們推廣了“六度分離”的科學假設，提出了小世界網(wǎng)絡模型?！傲确蛛x”來自對社會調(diào)查的推斷，指在大多數(shù)人中，任意兩個素不相識的人通過朋友的朋友，平均最多通過6個人就能夠彼此認識。2003年，瓦茨領導的研究小組發(fā)表一個實驗報告，他們利用互聯(lián)網(wǎng)在全世界范圍內(nèi)檢驗了上述驚人的“六度分離”假說，有6萬多志愿者參與利用電子郵件通信實驗，確實不到6步就實現(xiàn)了他們的假設，從而利用互聯(lián)網(wǎng)初步驗證了小世界現(xiàn)象?？梢?，瓦茨和斯特羅加茨的研究結(jié)果進一步揭示了復雜網(wǎng)絡的小世界效應。

從科學上，小世界效應包含兩個基本特征量：平均路徑長度APL(指網(wǎng)絡中所有節(jié)點對之間的平均最短距離)和群聚系數(shù)C(用來衡量一個復雜網(wǎng)絡的集團化程度)。APL越小越好，C越大越好，這樣小世界效應就越突出。這個小世界效應有廣泛的應用，可以設計所需要的工程網(wǎng)絡和計算機網(wǎng)絡等。

緊接小世界效應之后的另一個發(fā)現(xiàn)是：1999年美國的巴拉巴西和艾爾伯特發(fā)表了《隨機網(wǎng)絡中標度的涌現(xiàn)》論文，提出了一個無標度網(wǎng)絡模型，發(fā)現(xiàn)了復雜網(wǎng)絡的節(jié)點的度分布具有冪指數(shù)函數(shù)的規(guī)律。所謂節(jié)點的度是指與該節(jié)點連接的邊數(shù)。度在不同的網(wǎng)絡中所代表的含義不盡相同。例如，在城市航空交通網(wǎng)中，度分布表示城市之間的航線的多少和重要程度，度越大的城市，其重要性就越大；在社會網(wǎng)絡中，度可表示個體的作用力和影響程度，

一個節(jié)點的度越大，一般表示在整個網(wǎng)絡系統(tǒng)組織中的作用和影響就越大，反之亦然。因為冪指數(shù)函數(shù)在雙對數(shù)坐標中是一條直線，這個分布與系統(tǒng)特征長度無關，所以這個特性被稱為無標度性質(zhì)。它反映網(wǎng)絡中度分布的不均勻性，只有很少數(shù)的節(jié)點與其他節(jié)點有很多的連接，成為“中心節(jié)點”，而大多數(shù)節(jié)點度很小。

這個無標度特性是一把“雙刃劍”，一是可使網(wǎng)絡對意外故障具有驚人的抗攻擊能力；另一面對協(xié)同式攻擊則很脆弱，一旦擊中少數(shù)“中心節(jié)點”，就會導致整個網(wǎng)絡崩潰。因此，人們?yōu)榱吮苊饩W(wǎng)絡因遭受攻擊或意外事故導致的崩潰發(fā)生，最有效的辦法就是保護好網(wǎng)絡中節(jié)點度最大和次大的少數(shù)“中心節(jié)點”。

由巴拉巴西等入編著的《網(wǎng)絡的結(jié)構(gòu)與動力學》專著，在國際上產(chǎn)生了廣泛而深刻的影響。由于巴拉巴西在網(wǎng)絡科學方面的杰出貢獻，他于2006年獲得了美國馮·諾依曼計算機金獎。這標志著網(wǎng)絡研究進入了網(wǎng)絡科學的新時代，由此誕生了一門嶄新的科學——網(wǎng)絡科學。此后，網(wǎng)絡科學的文章鋪天蓋地，網(wǎng)絡科學的綜述和專著不斷涌現(xiàn)，從物理學到生物學，從社會科學到技術網(wǎng)絡，從工-程技術到經(jīng)濟管理等眾多領域，受到了人們的空前的關注和廣泛的重視。因此，這個階段樹起了網(wǎng)絡科學的第三個里程碑，極大促進了網(wǎng)絡科學及其應用的發(fā)展。

網(wǎng)絡科學的廣闊應用前景

首先，我們舉一個軍事實例來說明。1991年海灣戰(zhàn)爭中，當時美軍在網(wǎng)絡中心作戰(zhàn)實踐中暴露出一個關鍵的問題：戰(zhàn)后發(fā)現(xiàn)伊軍網(wǎng)絡使用的是當時市場上的因特網(wǎng)路由器，具有先進的動態(tài)路由選擇技術，使得伊軍指揮控制網(wǎng)絡具有較好的線路恢復和抗打擊能力。因為戰(zhàn)爭中美軍沒有對這些路由器進行有效的打擊，所以遲遲沒能完全切斷伊軍指揮控制網(wǎng)絡，直到最后伊軍還保留一條主要干線的光纖電纜。這是現(xiàn)代軍事史上最早的一個對因特網(wǎng)攻擊的戰(zhàn)例。

一直到2003年，巴拉巴西把無標度網(wǎng)絡的發(fā)現(xiàn)應用于因特網(wǎng)攻擊的實驗及定量分析，才發(fā)現(xiàn)只要進行一次有組織的協(xié)同攻擊，使5％～10％的節(jié)點度大的所謂“中心節(jié)點”同時失效，就可使整個因特網(wǎng)系統(tǒng)崩潰。也就是說，只要首先去除具有最大度的節(jié)點，再去除次大度的節(jié)點，依次類推，就會導致整個網(wǎng)絡的崩潰。所以，如果美軍能有組織地協(xié)同攻擊伊軍網(wǎng)絡中心節(jié)點，就能很快地切斷伊主要干線的光纖電纜，從而必然加速戰(zhàn)爭勝利的進程。

有鑒于此，美國海軍首次提出“網(wǎng)絡作戰(zhàn)中心”概念。美國國防部進一步提出了網(wǎng)絡中心作戰(zhàn)概念框架，以實現(xiàn)美軍向網(wǎng)絡中心作戰(zhàn)的轉(zhuǎn)型。這一任務的復雜性、前沿性，堪比當年美國的“曼哈頓”原子彈工程及“阿波羅”登月工程。

我們同時可以從網(wǎng)絡的安全問題來說明網(wǎng)絡科學研究的重要性和迫切性。人們不會忘記“愛蟲”、“熊貓燒香”等病毒在互聯(lián)網(wǎng)上大肆傳播，震驚世界的“北美大停電”，由于臺灣地震演變成史無前例的亞太區(qū)通訊網(wǎng)絡大災難等等。人們應該如何阻止和控制病毒在復雜網(wǎng)絡上傳播蔓延?如何有效地防止黑客侵入?怎樣來設計出具有強魯棒性(能夠有效抵抗意外故障和攻擊能力)的復雜網(wǎng)絡以防止網(wǎng)絡上的一系列級聯(lián)效應?怎樣消除不斷惡化的生態(tài)環(huán)境網(wǎng)絡而保持生態(tài)環(huán)境良性平衡等等。這一系列棘手問題無不與社會生活息息相關，涉及到因特網(wǎng)、萬維網(wǎng)、各種交通運輸網(wǎng)、電力網(wǎng)、各種通信網(wǎng)絡、衛(wèi)星電視網(wǎng)、電子郵件網(wǎng)、生態(tài)環(huán)境網(wǎng)絡和食物鏈網(wǎng)等復雜網(wǎng)絡。一句話，世界上多種多樣網(wǎng)絡的安全是一個首要問題。

當前，迫切需要網(wǎng)絡科學研究的重大問題之一是：對于復雜的、多層次的、全球性的因特網(wǎng)，如何從全局著手，優(yōu)化網(wǎng)絡安全性能和抗打擊能力，從根本上消除在網(wǎng)絡拓撲結(jié)構(gòu)上存在的不安全因素，預防未來可能發(fā)生的災難性攻擊。為此，需要解決一系列具體問題，諸如在故障和蓄意攻擊等情況下能快速自動恢復的網(wǎng)絡拓撲結(jié)構(gòu)和技術；全球規(guī)模的網(wǎng)絡監(jiān)控、入侵檢測、網(wǎng)絡取證和防范犯罪的網(wǎng)絡拓撲結(jié)構(gòu)及相關理論、方法和技術：建立因特網(wǎng)的模型、仿真系統(tǒng)和測試平臺，它包含百萬級節(jié)點并能模擬和預測因特網(wǎng)的復雜行為。這些問題的解決將大大推進人類物質(zhì)和精神文明的建設，造福于人類。(文章代碼：0405)

[責任編輯]龐云