網(wǎng)絡(luò)科學(xué)三大里程碑

1、網(wǎng)絡(luò)科學(xué)三大里程碑方錦清追溯網(wǎng)絡(luò)科學(xué)發(fā)展的軌跡，網(wǎng)絡(luò)科學(xué)發(fā)展史有過三大里程碑，每個里程碑無一不是從網(wǎng) 絡(luò)的理論模型首先取得突破的。國際上提出的經(jīng)典理論模型最著名的有歐拉圖論、ER隨機(jī) 圖以及小世界模型和無標(biāo)度模型?？茖W(xué)界迄今已經(jīng)積累了許多有價值的理論模型開展了許 多實(shí)際網(wǎng)絡(luò)的研究，基本揭開了復(fù)雜網(wǎng)絡(luò)的廬山真面目，使人們了解到其復(fù)雜性與簡單性、多 樣性與普適性之間錯綜復(fù)雜的關(guān)系。第一個里程碑:歐拉圖論網(wǎng)絡(luò)科學(xué)首先是得益于圖論和拓?fù)鋵W(xué)等應(yīng)用數(shù)學(xué)的發(fā)展。歷史上多位杰出數(shù)學(xué)家各自 獨(dú)立地建立和研究過圖論，他們的貢獻(xiàn)功不可沒。所謂圖論就是由一些點(diǎn)按照一定方式連線 組成的一個圖（集合）。關(guān)于圖論的文字記載

2、最早出現(xiàn)在1736年瑞士數(shù)學(xué)家歐拉的論著中， 他所考慮的原始問題具有很強(qiáng)的實(shí)際背景，那就是著名的哥尼斯堡七橋問題。哥尼斯堡是當(dāng)時東普魯士的首都，今俄羅斯加里寧格勒市，普萊格爾河橫貫其中,這條河 上建有七座橋，將河中間的兩個島和河岸聯(lián)結(jié)起來。人們閑暇時經(jīng)常在這上邊散步，有人提出: 能不能每座橋都只走一遍，最后又回到原來的位置。這個看起來很簡單卻很有趣的問題吸引 了大家,很多人在嘗試各種各樣的走法，然而無數(shù)次的嘗試都沒有成功1736年，有人帶著這個問題找到了當(dāng)時的大數(shù)學(xué)家歐拉，歐拉經(jīng)過一番思考，很快就用 一種獨(dú)特的方法給出了解答。他把兩座小島和河的兩岸分別看作四個點(diǎn)而把七座橋看作這 四個點(diǎn)之間的連

3、線，如圖所示,A、B、C、D表示陸地。于是這個問題就簡化成能不能用一筆 就把這個圖形畫出來。經(jīng)過進(jìn)一步的分析，歐拉得出結(jié)論:不可能每座橋都走一遍，最后回到 原來的位置，并且給出了所有能夠一筆畫出來的圖形所應(yīng)具有的條件。這項(xiàng)工作使歐拉成為 圖論（及拓?fù)鋵W(xué)）的創(chuàng)始人。歐拉的研究開創(chuàng)了圖論這門新的數(shù)學(xué)分支，歐拉因此被譽(yù)為“圖論之父”。這是第一代 科學(xué)家對網(wǎng)絡(luò)科學(xué)的開創(chuàng)性貢獻(xiàn)。1859年，英國數(shù)學(xué)家哈密頓發(fā)明了一種游戲:用一個規(guī)則的實(shí)心十二面體，它的20個節(jié) 點(diǎn)標(biāo)出世界著名的20個城市，要求游戲者找一條沿著各邊通過每個節(jié)點(diǎn)剛好一次的閉回路， 即“繞行世界”。用圖論的語言來說，游戲的目的是在十二面體的圖

4、中找出一個生成圈。這 個問題后來就叫做哈密頓問題。由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以化 為哈密頓問題，從而引起國際上廣泛的注意和研究。在圖論的歷史中，還有一個最著名的問題一一四色猜想，它也是世界近代三大數(shù)學(xué)難題 之一。首先提出四色猜想的人是英國人弗南西斯格思里,他在給地圖著色時，發(fā)現(xiàn)了一種有 趣的現(xiàn)象:“每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。” 18781880年兩年間，著名律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文。 但后來數(shù)學(xué)家赫伍德以自己的精確計(jì)算指出肯普的證明是錯誤的。不久泰勒的證明也被人 們否定了。于是，人們開始認(rèn)識到，這個

5、貌似容易的題目，其實(shí)是一個可與費(fèi)馬猜想相媲美的 難題。所以它對圖的著色理論、平面圖理論、代數(shù)拓?fù)鋱D論等分支的發(fā)展起到推動作用。進(jìn) 入20世紀(jì)以來,科學(xué)家們對四色猜想的證明基本上是按照肯普的想法在進(jìn)行。電子計(jì)算機(jī)問 世以后，由于演算速度迅速提高,加之人機(jī)對話的出現(xiàn)，大大加快了對四色猜想證明的進(jìn)程。 1976年，美國數(shù)學(xué)家阿佩爾與哈肯在美國伊利諾斯大學(xué)的兩臺不同的電子計(jì)算機(jī)上，用了 1200個小時，作了 i00億判斷，終于完成了四色定理的證明。當(dāng)然,不少數(shù)學(xué)家還在探索一種 更簡捷明快的書面證明方法。在拓?fù)鋵W(xué)的發(fā)展歷史中，還有一個著名而且重要的關(guān)于多面體的定理也和歐拉有關(guān)。因 此,歐拉開創(chuàng)的圖論（現(xiàn)

6、在稱為網(wǎng)絡(luò)科學(xué)理論），當(dāng)之無愧地處于網(wǎng)絡(luò)金字塔的最頂端。第二個里程碑:ER隨機(jī)圖理論在20世紀(jì)五六十年代，兩個匈牙利著名的數(shù)學(xué)家愛多士（Erdos）和瑞尼（Renyi）又一次 對圖論（網(wǎng)絡(luò)科學(xué)理論）作出了第二個里程碑式的貢獻(xiàn)，他們建立了著名的隨機(jī)圖理論，用相 對簡單的隨機(jī)圖來描述網(wǎng)絡(luò)，簡稱ER隨機(jī)圖理論。用圖論的語言和符號可以精確簡潔地加以 描述各種網(wǎng)絡(luò)，圖論不僅為數(shù)學(xué)家和物理學(xué)家提供了描述網(wǎng)絡(luò)的共同語言和研究平臺，而且 至今圖論的許多研究成果、結(jié)論和方法技巧仍然能夠自然地應(yīng)用到現(xiàn)在復(fù)雜網(wǎng)絡(luò)的研究中去 成為網(wǎng)絡(luò)研究的有力方法和工具之一。愛多士被稱為20世紀(jì)的歐拉，于1984年獲得沃爾夫獎。他的

7、一生充滿著傳奇色彩，一無 財產(chǎn)、二無妻小、三無固定居所完全是一個數(shù)學(xué)“苦行僧”。他善于與人合作打破了數(shù)學(xué) 領(lǐng)域的喜歡個人獨(dú)立研究的傳統(tǒng)，一生有480多個合作者,留下約1475篇文章，還與那些偉大 的理論物理學(xué)家和數(shù)學(xué)家，如愛因斯坦、哥德爾、奧本海默等有密切的學(xué)術(shù)交往。第三個里程碑:小世界現(xiàn)象與無標(biāo)度特性1998年，網(wǎng)絡(luò)科學(xué)又一次取得突破性進(jìn)展，出現(xiàn)了第三個里程碑。美國的瓦茨和斯特羅 加茨首先沖破了 ER理論的框框，發(fā)表了題為“小世界”網(wǎng)絡(luò)的群體動力行為的論文，他 們推廣了 “六度分離”的科學(xué)假設(shè)，提出了小世界網(wǎng)絡(luò)模型?！傲确蛛x”來自對社會調(diào)查 的推斷，指在大多數(shù)人中，任意兩個素不相識的人通過

8、朋友的朋友，平均最多通過6個人就能 夠彼此認(rèn)識。2003年，瓦茨領(lǐng)導(dǎo)的研究小組發(fā)表一個實(shí)驗(yàn)報告,他們利用互聯(lián)網(wǎng)在全世界范 圍內(nèi)檢驗(yàn)了上述驚人的“六度分離”假說，有6萬多志愿者參與利用電子郵件通信實(shí)驗(yàn)，確實(shí) 不到6步就實(shí)現(xiàn)了他們的假設(shè)，從而利用互聯(lián)網(wǎng)初步驗(yàn)證了小世界現(xiàn)象?？梢?，瓦茨和斯特羅 加茨的研究結(jié)果進(jìn)一步揭示了復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)。從科學(xué)上,小世界效應(yīng)包含兩個基本特征量:平均路徑長度APL（指網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之 間的平均最短距離）和群聚系數(shù)C（用來衡量一個復(fù)雜網(wǎng)絡(luò)的集團(tuán)化程度）。APL越小越好,C 越大越好，這樣小世界效應(yīng)就越突出。這個小世界效應(yīng)有廣泛的應(yīng)用，可以設(shè)計(jì)所需要的工程 網(wǎng)絡(luò)和計(jì)

9、算機(jī)網(wǎng)絡(luò)等。緊接小世界效應(yīng)之后的另一個發(fā)現(xiàn)是:1999年美國的巴拉巴西和艾爾伯特發(fā)表了隨機(jī) 網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)論文，提出了一個無標(biāo)度網(wǎng)絡(luò)模型，發(fā)現(xiàn)了復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)的度分布具有 冪指數(shù)函數(shù)的規(guī)律。所謂節(jié)點(diǎn)的度是指與該節(jié)點(diǎn)連接的邊數(shù)。度在不同的網(wǎng)絡(luò)中所代表的含 義不盡相同。例如，在城市航空交通網(wǎng)中，度分布表示城市之間的航線的多少和重要程度，度 越大的城市，其重要性就越大;在社會網(wǎng)絡(luò)中，度可表示個體的作用力和影響程度，一個節(jié)點(diǎn) 的度越大,一般表示在整個網(wǎng)絡(luò)系統(tǒng)組織中的作用和影響就越大反之亦然。因?yàn)閮缰笖?shù)函數(shù) 在雙對數(shù)坐標(biāo)中是一條直線，這個分布與系統(tǒng)特征長度無關(guān)，所以這個特性被稱為無標(biāo)度性 質(zhì)。它反映網(wǎng)

10、絡(luò)中度分布的不均勻性，只有很少數(shù)的節(jié)點(diǎn)與其他節(jié)點(diǎn)有很多的連接，成為“中 心節(jié)點(diǎn)”，而大多數(shù)節(jié)點(diǎn)度很小。這個無標(biāo)度特性是一把“雙刃劍”，一是可使網(wǎng)絡(luò)對意外故障具有驚人的抗攻擊能力； 另一面對協(xié)同式攻擊則很脆弱,一旦擊中少數(shù)“中心節(jié)點(diǎn)”，就會導(dǎo)致整個網(wǎng)絡(luò)崩潰。因此， 人們?yōu)榱吮苊饩W(wǎng)絡(luò)因遭受攻擊或意外事故導(dǎo)致的崩潰發(fā)生，最有效的辦法就是保護(hù)好網(wǎng)絡(luò)中 節(jié)點(diǎn)度最大和次大的少數(shù)“中心節(jié)點(diǎn)”。由巴拉巴西等入編著的網(wǎng)絡(luò)的結(jié)構(gòu)與動力學(xué)專著，在國際上產(chǎn)生了廣泛而深刻的影 響。由于巴拉巴西在網(wǎng)絡(luò)科學(xué)方面的杰出貢獻(xiàn)，他于2006年獲得了美國馮諾依曼計(jì)算機(jī)金 獎。這標(biāo)志著網(wǎng)絡(luò)研究進(jìn)入了網(wǎng)絡(luò)科學(xué)的新時代,由此誕生了一門嶄

11、新的科學(xué)一一網(wǎng)絡(luò)科學(xué)。 此后，網(wǎng)絡(luò)科學(xué)的文章鋪天蓋地，網(wǎng)絡(luò)科學(xué)的綜述和專著不斷涌現(xiàn)，從物理學(xué)到生物學(xué)，從社 會科學(xué)到技術(shù)網(wǎng)絡(luò),從工-程技術(shù)到經(jīng)濟(jì)管理等眾多領(lǐng)域，受到了人們的空前的關(guān)注和廣泛的 重視。因此，這個階段樹起了網(wǎng)絡(luò)科學(xué)的第三個里程碑，極大促進(jìn)了網(wǎng)絡(luò)科學(xué)及其應(yīng)用的發(fā) 展。網(wǎng)絡(luò)科學(xué)的廣闊應(yīng)用前景首先，我們舉一個軍事實(shí)例來說明。1991年海灣戰(zhàn)爭中，當(dāng)時美軍在網(wǎng)絡(luò)中心作戰(zhàn)實(shí)踐 中暴露出一個關(guān)鍵的問題:戰(zhàn)后發(fā)現(xiàn)伊軍網(wǎng)絡(luò)使用的是當(dāng)時市場上的因特網(wǎng)路由器，具有先 進(jìn)的動態(tài)路由選擇技術(shù)，使得伊軍指揮控制網(wǎng)絡(luò)具有較好的線路恢復(fù)和抗打擊能力。因?yàn)閼?zhàn) 爭中美軍沒有對這些路由器進(jìn)行有效的打擊,所以遲遲沒能完

12、全切斷伊軍指揮控制網(wǎng)絡(luò)，直 到最后伊軍還保留一條主要干線的光纖電纜。這是現(xiàn)代軍事史上最早的一個對因特網(wǎng)攻擊的 戰(zhàn)例。一直到2003年，巴拉巴西把無標(biāo)度網(wǎng)絡(luò)的發(fā)現(xiàn)應(yīng)用于因特網(wǎng)攻擊的實(shí)驗(yàn)及定量分柝才 發(fā)現(xiàn)只要進(jìn)行一次有組織的協(xié)同攻擊，使5%10%的節(jié)點(diǎn)度大的所謂“中心節(jié)點(diǎn)”同時失效， 就可使整個因特網(wǎng)系統(tǒng)崩潰。也就是說，只要首先去除具有最大度的節(jié)點(diǎn)，再去除次大度的節(jié) 點(diǎn)，依次類推，就會導(dǎo)致整個網(wǎng)絡(luò)的崩潰。所以，如果美軍能有組織地協(xié)同攻擊伊軍網(wǎng)絡(luò)中心 節(jié)點(diǎn)，就能很快地切斷伊主要干線的光纖電纜，從而必然加速戰(zhàn)爭勝利的進(jìn)程。有鑒于此，美國海軍首次提出“網(wǎng)絡(luò)作戰(zhàn)中心”概念。美國國防部進(jìn)一步提出了網(wǎng)絡(luò)中 心

13、作戰(zhàn)概念框架,以實(shí)現(xiàn)美軍向網(wǎng)絡(luò)中心作戰(zhàn)的轉(zhuǎn)型。這一任務(wù)的復(fù)雜性、前沿性，堪比當(dāng)年 美國的“曼哈頓”原子彈工程及“阿波羅”登月工程。我們同時可以從網(wǎng)絡(luò)的安全問題來說明網(wǎng)絡(luò)科學(xué)研究的重要性和迫切性。人們不會忘記 “愛蟲”、“熊貓燒香”等病毒在互聯(lián)網(wǎng)上大肆傳播，震驚世界的“北美大停電”，由于臺灣 地震演變成史無前例的亞太區(qū)通訊網(wǎng)絡(luò)大災(zāi)難等等。人們應(yīng)該如何阻止和控制病毒在復(fù)雜網(wǎng) 絡(luò)上傳播蔓延?如何有效地防止黑客侵入?怎樣來設(shè)計(jì)出具有強(qiáng)魯棒性（能夠有效抵抗意外故 障和攻擊能力）的復(fù)雜網(wǎng)絡(luò)以防止網(wǎng)絡(luò)上的一系列級聯(lián)效應(yīng)？怎樣消除不斷惡化的生態(tài)環(huán)境 網(wǎng)絡(luò)而保持生態(tài)環(huán)境良性平衡等等。這一系列棘手問題無不與社會生活息息相關(guān)涉及到因 特網(wǎng)、萬維網(wǎng)、各種交通運(yùn)輸網(wǎng)、電力網(wǎng)、各種通信網(wǎng)絡(luò)、衛(wèi)星電視網(wǎng)、電子郵件網(wǎng)、生態(tài) 環(huán)境網(wǎng)絡(luò)和食物鏈網(wǎng)等復(fù)雜網(wǎng)絡(luò)。一句話，世界上多種多樣網(wǎng)絡(luò)的安全是一個首要問題。當(dāng)前，迫切需要網(wǎng)絡(luò)科學(xué)研究的重大問題之一是:對于復(fù)雜的、多層次的、全球性的因特網(wǎng)，如何從全局著手，優(yōu)化網(wǎng)絡(luò)安全性能和抗打擊能力，從根本上消除在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上存在 的不安全因素，預(yù)防