網(wǎng)絡(luò)科學(xué)發(fā)展簡(jiǎn)史

時(shí)間：2023-02-25 02:27:01 | 來(lái)源：營(yíng)銷百科

時(shí)間：2023-02-25 02:27:01 來(lái)源：營(yíng)銷百科

網(wǎng)絡(luò)科學(xué)發(fā)展簡(jiǎn)史：圖論和拓?fù)鋵W(xué)

網(wǎng)絡(luò)科學(xué)首先得益于圖論和拓?fù)鋵W(xué)等應(yīng)用數(shù)學(xué)的發(fā)展。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中,他所考慮的原始問(wèn)題具有很強(qiáng)的實(shí)際背景。在數(shù)學(xué)上,關(guān)于哥尼斯堡七橋問(wèn)題、多面體的歐拉定理、四色問(wèn)題等都是拓?fù)鋵W(xué)發(fā)展史的重要問(wèn)題。而在歐拉身后，一些數(shù)學(xué)大師如柯西、漢密爾頓、凱利、基爾霍夫、波利亞等都對(duì)圖論作出了貢獻(xiàn)，使這門科學(xué)得到了快速的發(fā)展。

1、哥尼斯堡七橋問(wèn)題^[2]

哥尼斯堡是東普魯士的首都,今俄羅斯加里寧格勒市,普萊格爾河橫貫其中。18世紀(jì)在這條河上建有七座橋,將河中間的兩個(gè)島和河岸連結(jié)起來(lái)。人們閑暇時(shí)經(jīng)常在這上邊散步,有人提出:能不能每座橋都只走一遍,最后又回到原來(lái)的位置。這個(gè)看起來(lái)很簡(jiǎn)單卻很有趣的問(wèn)題吸引了大家,很多人在嘗試各種各樣的走法,然而無(wú)數(shù)次的嘗試都沒(méi)有成功。誰(shuí)也沒(méi)有做到,看來(lái)要得到一個(gè)明確、理想的答案決非那么容易。

1736年,有人帶著這個(gè)問(wèn)題找到了當(dāng)時(shí)的大數(shù)學(xué)家歐拉,歐拉經(jīng)過(guò)一番思考,很快就用一種獨(dú)特的方法給出了解答。歐拉首先把這個(gè)問(wèn)題簡(jiǎn)化,他把兩座小島和河的兩岸分別看作四個(gè)點(diǎn),而把七座橋看作這四個(gè)點(diǎn)之間的連線.歐拉圖的研究開創(chuàng)了'圖論'這門新的數(shù)學(xué)分支[7],因此,這是第一代科學(xué)家對(duì)網(wǎng)絡(luò)的開創(chuàng)性貢獻(xiàn),于是歐拉被譽(yù)為圖論之父。問(wèn)題是要從這四塊陸地中任何一塊開始,通過(guò)每一座橋正好一次,再回到起點(diǎn)。即這個(gè)問(wèn)題就簡(jiǎn)化成,能不能用一筆就把這個(gè)圖形畫出來(lái)。經(jīng)過(guò)進(jìn)一步的分析,歐拉得出結(jié)論———不可能每座橋都走一遍,最后回到原來(lái)的位置。并且給出了所有能夠一筆畫出來(lái)的圖形所應(yīng)具有的條件。這是拓?fù)鋵W(xué)的'先聲'。歐拉在1736年解決了這個(gè)問(wèn)題,他用抽象分析法將這個(gè)問(wèn)題化為第一個(gè)圖論問(wèn)題:即把每一塊陸地用一個(gè)點(diǎn)來(lái)代替,將每一座橋用聯(lián)接相應(yīng)的兩個(gè)點(diǎn)的一條線來(lái)代替,從而相當(dāng)于得到一個(gè)圖。歐拉證明了這個(gè)問(wèn)題沒(méi)有解,并且推廣了這個(gè)問(wèn)題,給出了對(duì)于一個(gè)給定的圖可以某種方式走遍的判定法則。這項(xiàng)工作使歐拉成為圖論〔及拓?fù)鋵W(xué)〕的創(chuàng)始人。因此,關(guān)于哥尼斯堡七橋問(wèn)題、多面體的歐拉定理、四色問(wèn)題等成為拓?fù)鋵W(xué)發(fā)展史上的著名問(wèn)題。

2、四色問(wèn)題（四色定理）

在圖論的歷史中,還有一個(gè)最著名的問(wèn)題———四色猜想（四色定理）。提出四色猜想的人來(lái)自英國(guó),有一段有趣的歷史。1852年,畢業(yè)于倫敦大學(xué)的弗南西斯.格思里來(lái)到一家科研單位搞地圖著色工作時(shí),發(fā)現(xiàn)了一種有趣的現(xiàn)象:'看來(lái),每幅地圖都可以用四種顏色著色,使得有共同邊界的國(guó)家都被著上不同的顏色。'每個(gè)國(guó)家必須由一個(gè)單連通域構(gòu)成,而兩個(gè)國(guó)家相鄰是指它們有一段公共的邊界,而不僅僅只有一個(gè)公共點(diǎn)。1872年,英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問(wèn)題,于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題,它是圖論中的一個(gè)著名的問(wèn)題,并且是世界近代三大數(shù)學(xué)難題之一。世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會(huì)戰(zhàn)。1878~1880年兩年間,著名律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文,宣布證明了四色定理。但后來(lái)數(shù)學(xué)家赫伍德以自己的精確計(jì)算指出肯普的證明是錯(cuò)誤的。不久,泰勒的證明也被人們否定了。于是,人們開始認(rèn)識(shí)到,這個(gè)貌似容易的題目,其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題。所以它對(duì)圖的著色理論、平面圖理論、代數(shù)拓?fù)鋱D論等分支的發(fā)展起到推動(dòng)作用。進(jìn)入20世紀(jì)以來(lái),科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行。電子計(jì)算機(jī)問(wèn)世以后,由于演算速度迅速提高,加之人機(jī)對(duì)話的出現(xiàn),大大加快了對(duì)四色猜想證明的進(jìn)程。1976年,美國(guó)數(shù)學(xué)家阿佩爾與哈肯在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上,用了1200個(gè)小時(shí),作了100億判斷,終于完成了四色定理的證明。當(dāng)然,不少數(shù)學(xué)家還在探索一種更簡(jiǎn)捷明快的書面證明方法。

隨機(jī)圖理論

兩個(gè)匈牙利著名的數(shù)學(xué)家Paul Edo''s(保羅·愛(ài)爾德)和Alfred Renyi（阿爾弗雷德·萊利）,他們?cè)?0世紀(jì)50年代末和60年代合作發(fā)表了8篇論文，這8篇論文在歷史上首次探討了我們所處的相互關(guān)聯(lián)的宇宙的基本問(wèn)題：網(wǎng)絡(luò)是如何形成的？建立了著名的隨機(jī)圖理論,奠定了隨機(jī)網(wǎng)絡(luò)理論的基礎(chǔ)。這一理論最重要的假設(shè)為：網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈接是隨機(jī)選擇建立連接的。他們認(rèn)為網(wǎng)絡(luò)圖和它所代表的世界從根本上說(shuō)是隨機(jī)的。隨機(jī)網(wǎng)絡(luò)模型的前提是深刻的平等主義：我們完全隨機(jī)的安排鏈接，因此所有的節(jié)點(diǎn)都有等同的機(jī)會(huì)獲得鏈接。^[3]

他們用相對(duì)簡(jiǎn)單的隨機(jī)圖來(lái)描述網(wǎng)絡(luò),簡(jiǎn)稱ER隨機(jī)圖理論,他們的最重要發(fā)現(xiàn)是ER隨機(jī)圖中許多重要性質(zhì)都是隨著網(wǎng)絡(luò)規(guī)模的增大突然涌現(xiàn)的。他們創(chuàng)立的ER隨機(jī)圖理論為圖類的閾函數(shù)和巨大分支涌現(xiàn)的相變等提供了研究網(wǎng)絡(luò),的一種重要的數(shù)學(xué)理論。

確實(shí),用圖論的語(yǔ)言和符號(hào)可以精確簡(jiǎn)潔地加以描述各種網(wǎng)絡(luò),圖論不僅為數(shù)學(xué)家和物理學(xué)家提供了描述網(wǎng)絡(luò)的共同語(yǔ)言和研究平臺(tái),而且至今圖論的許多研究成果、結(jié)論和方法技巧仍然能夠自然地應(yīng)用到現(xiàn)在復(fù)雜網(wǎng)絡(luò)的研究中去,成為網(wǎng)絡(luò)科學(xué)研究的有力方法和工具之一。在長(zhǎng)達(dá)40年的ER隨機(jī)圖對(duì)于圖論理論的影響大而廣泛。

小世界理論和六度分離

1998年,科學(xué)家迎來(lái)了復(fù)雜網(wǎng)絡(luò)的又一次突破性進(jìn)展,首先沖破了ER理論的框框的人是,美國(guó)康奈爾(Cornell )大學(xué)理論和應(yīng)用力學(xué)系的博士生Watts及其導(dǎo)師Strogatz在《Nature》雜志上發(fā)表了題為《'小世界'網(wǎng)絡(luò)的群體動(dòng)力行為》的論文,提出了小世界網(wǎng)絡(luò)模型。這實(shí)際上是20世紀(jì)60年代美國(guó)哈佛大學(xué)的心理學(xué)家Milgram曾經(jīng)作過(guò)的著名的小世界實(shí)驗(yàn)的一種拓廣,Milgram提出的'六度分離'(six degrees of separation )社會(huì)調(diào)查后的推斷,它原意是指在美國(guó)大多數(shù)人中,任意兩個(gè)人平均最多通過(guò)6個(gè)人就能夠彼此認(rèn)識(shí)。不管是誰(shuí)如果想認(rèn)識(shí)一個(gè)素不相識(shí)的人,只要通過(guò)六個(gè)他的朋友的朋友轉(zhuǎn)達(dá)之后,一般就能夠聯(lián)系得上。人們常有這么體驗(yàn),當(dāng)參加國(guó)內(nèi)外會(huì)議或訪問(wèn)或旅游時(shí),經(jīng)常與遇到一些新朋友交談時(shí),你很快就發(fā)現(xiàn):他認(rèn)識(shí)你的朋友,你認(rèn)識(shí)他的朋友的朋友,于是大家不約而同地脫口而出:這個(gè)世界真小啊!這就是'小世界效應(yīng)(現(xiàn)象)',這里包含了'六度分離概念'的基本思想,那么你現(xiàn)在想與世界上任何一個(gè)人(例如史蒂芬·霍金等)聯(lián)系交朋友嗎?咋看似乎不太可能。如果你真想聯(lián)絡(luò)到他,應(yīng)該怎么辦?你可這樣做:找一個(gè)最有可能和他有聯(lián)系的親友,把問(wèn)候轉(zhuǎn)達(dá)給他,然后他也照樣去找下一位親友。這樣你一共需要多少個(gè)親友作為'中轉(zhuǎn)站'就能找到對(duì)方呢?這個(gè)問(wèn)題的答案或許有點(diǎn)讓人吃驚:不論你想找地球上哪人(壯漢或名人),大約只需要6步,最后一步就是'中轉(zhuǎn)'的最終目標(biāo)。2003年哥倫比亞大學(xué)社會(huì)學(xué)系的的瓦茨(DuncanWatts)領(lǐng)導(dǎo)的研究小組在《科學(xué)》雜志上,發(fā)表實(shí)驗(yàn)報(bào)告,他們利用互聯(lián)網(wǎng)在全世界范圍內(nèi)初步檢驗(yàn)了上述驚人的假說(shuō),有六萬(wàn)多志愿者參與利用電子郵件通信試驗(yàn),例如從分布世界各地某同學(xué)的同學(xué)進(jìn)行通信試驗(yàn)表明,確實(shí)不到6步就實(shí)現(xiàn)了,這是利用互聯(lián)網(wǎng)初步驗(yàn)證了小世界現(xiàn)象。但是這個(gè)試驗(yàn)還不夠多,他們準(zhǔn)備做上億的互聯(lián)網(wǎng)進(jìn)一步試驗(yàn)。可見,Watts和Strogatz的研究結(jié)果進(jìn)一步揭示了復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)。

無(wú)標(biāo)度網(wǎng)絡(luò)模型（Scale-free Network）

1999年美國(guó)圣母(Notre Dame )大學(xué)物理系的Barabási教授(見圖1.3)及其博士生Albert在《Science》雜志上發(fā)表了題為《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》一文[3],提出了一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)模型,發(fā)現(xiàn)了復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度性質(zhì),并和M. Newmann,D. J. Watts共同編輯了'網(wǎng)絡(luò)的結(jié)構(gòu)與動(dòng)力學(xué)'(The Structure and Dynamics,普林斯頓大學(xué)出版社,普林斯頓, 2003年)專著,該書在國(guó)際上產(chǎn)生了廣泛的影響,引起了全世界的高度重視。正是他在網(wǎng)絡(luò)科學(xué)方面的杰出貢獻(xiàn),因此于2006年獲得了美國(guó)von Neumann (馮紐曼)計(jì)算金獎(jiǎng)。

標(biāo)志著復(fù)雜網(wǎng)絡(luò)研究進(jìn)入了網(wǎng)絡(luò)科學(xué)的新時(shí)代,由此誕生了一門嶄新的科學(xué):網(wǎng)絡(luò)科學(xué)。網(wǎng)絡(luò)科學(xué)的二大發(fā)現(xiàn),以及隨后許多真實(shí)網(wǎng)絡(luò)的實(shí)證研究表明,真實(shí)世界網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò),也不是隨機(jī)網(wǎng)絡(luò),而是兼具小世界和無(wú)標(biāo)度特性,具有與規(guī)則網(wǎng)絡(luò)和隨機(jī)圖完全不同的統(tǒng)計(jì)特性。這在全世界學(xué)術(shù)界激起了千重浪,復(fù)雜網(wǎng)絡(luò)文章鋪天蓋地,網(wǎng)絡(luò)科學(xué)的綜述和專著不斷涌現(xiàn)[11~22],從物理學(xué)到生物學(xué),從社會(huì)科學(xué)到技術(shù)網(wǎng)絡(luò),從工程技術(shù)到經(jīng)濟(jì)管理等眾多領(lǐng)域,受到了人們的空前的廣泛關(guān)注和重視,正在突飛猛進(jìn)。