網絡科學三大里程碑

方錦清

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

第一個里程碑：歐拉圖論

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

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

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

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

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

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

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

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

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

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

第三個里程碑：小世界現象與無標度特性

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

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

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

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

這個無標度特性是一把“雙刃劍”，一是可使網絡對意外故障具有驚人的抗攻擊能力；另一面對協同式攻擊則很脆弱，一旦擊中少數“中心節點”，就會導致整個網絡崩潰。因此，人們為了避免網絡因遭受攻擊或意外事故導致的崩潰發生，最有效的辦法就是保護好網絡中節點度最大和次大的少數“中心節點”。

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

網絡科學的廣闊應用前景

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

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

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

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

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

[責任編輯]龐云