復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用第1頁/共67頁outline小世界實(shí)驗(yàn)

六度分離、Erdos數(shù)、bacon數(shù)等一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)

Web、科學(xué)家合作網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、疾病傳播等復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量

度分布、聚類系數(shù)、平均路徑長度等網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì)

隨機(jī)網(wǎng)絡(luò)、SmallWorld網(wǎng)絡(luò)、ScaleFree網(wǎng)絡(luò)等近幾年的研究態(tài)勢

發(fā)展歷程、會議、論文、軟件、實(shí)證等第2頁/共67頁小世界實(shí)驗(yàn)---六度分離我們或許有過這樣的經(jīng)歷：偶爾碰到一個(gè)陌生人，同他聊了一會后發(fā)現(xiàn)你認(rèn)識的某個(gè)人居然他也認(rèn)識，然后一起發(fā)出”這個(gè)世界真小”的感嘆。那么對于世界上任意兩個(gè)人來說，借助第三者、第四者這樣的間接關(guān)系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人呢？美國社會心理學(xué)家斯坦利?米爾格倫(StanleyMilgram)在1967年通過一些實(shí)驗(yàn)后得出結(jié)論：中間的聯(lián)系人平均只需要5個(gè)。他把這個(gè)結(jié)論稱為”六度分離”(sixdegreesofseparation)。六度分離:平均只要通過5個(gè)人，你就能與世界任何一個(gè)角落的任何一個(gè)人發(fā)生聯(lián)系。這個(gè)結(jié)論定量地說明了我們世界的”大小”，或者說人與人關(guān)系的緊密程度。30多年來，六度分離理論一直被作為社會心理學(xué)的經(jīng)典范例之一。盡管如此，實(shí)際上這個(gè)理論并沒有得到嚴(yán)格的證實(shí)。美國心理學(xué)教授朱迪斯?克蘭菲爾德(JudithKleinfeld)對米爾格倫最初的實(shí)驗(yàn)提出不同意見，因?yàn)樗l(fā)現(xiàn)實(shí)驗(yàn)的完成率極低。第3頁/共67頁小世界實(shí)驗(yàn)---六度分離米爾格倫的實(shí)驗(yàn)過程是：他計(jì)劃通過人傳人的送信方式來統(tǒng)計(jì)人與人之間的聯(lián)系。首先把信交給志愿者A，告訴他信最終要送給收信人S。如果他不認(rèn)識S，那么就送信到某個(gè)他認(rèn)識的人B手里，理由是A認(rèn)為在他的交集圈里B是最可能認(rèn)識S的。但是如果B也不認(rèn)識S，那么B同樣把信送到他的一個(gè)朋友C手中，……，就這樣一步步最后信終于到達(dá)S哪里。這樣就從A到B到C到……最后到S連成了一個(gè)鏈。斯坦利?米爾格倫就是通過對這個(gè)鏈做了統(tǒng)計(jì)后做出了六度分離的結(jié)論。然而在這個(gè)實(shí)驗(yàn)中，實(shí)際上只有三分之一的信送到了收信人哪里，因此實(shí)驗(yàn)的完成率很低。

第4頁/共67頁小世界實(shí)驗(yàn)---Erdos數(shù)

PaulErdos((1913-1996)，出生于匈牙利的猶太籍?dāng)?shù)學(xué)家，被公認(rèn)為本世紀(jì)最偉大的天才之一。Erdos畢生發(fā)表的論文超過1500篇（在數(shù)學(xué)史上僅次于歐拉(Euler

，1707-1783))，超長的合作者名單,合作者超過450位。但若加上別人所做但曾獲他關(guān)鍵性的提示之論文，則他的論文應(yīng)有數(shù)萬篇。他的研究領(lǐng)域主要是數(shù)論和組合數(shù)學(xué)，但他的論文中涵蓋的學(xué)科有逼近論、初等幾何、集合論、概率論、數(shù)理邏輯、格與序代數(shù)結(jié)構(gòu)、線性代數(shù)、群論、拓?fù)淙?、多?xiàng)式、測度論、單復(fù)變函數(shù)、差分方程與函數(shù)方程、數(shù)列、Fourier分析、泛函分析、一般拓?fù)浜痛鷶?shù)拓?fù)?、統(tǒng)計(jì)、數(shù)值分析、計(jì)算機(jī)科學(xué)、信息論等等。"MathematicalReviews"曾把數(shù)學(xué)劃分為大約六十個(gè)分支，Erdos的論文涉及到了其中的40%.

第5頁/共67頁小世界實(shí)驗(yàn)---Erdos數(shù)Erdos從來沒有一固定的職位，從來不定居在一個(gè)地方，也沒有結(jié)婚，帶著一半空的手提箱，穿梭于學(xué)術(shù)研討會，浪跡天涯，頗富傳奇色彩。有人稱他為流浪學(xué)者(wandering

scholar)。他效忠的是科學(xué)的皇后，

而非一特定的地方。各地都有熱心的數(shù)學(xué)家提供他舒適的食宿，安排他的一切，他則對招待他的主人，給出一些挑戰(zhàn)性的數(shù)學(xué)難題，或給予研究上的指導(dǎo)做為回饋。他可以和許多不同領(lǐng)域的數(shù)學(xué)家合作。數(shù)學(xué)家常將本身長久解決不了的問題和他討論，于是很快地一篇論文便誕生了。

第6頁/共67頁小世界實(shí)驗(yàn)---Erdos數(shù)數(shù)學(xué)家以下述方式來定義Erdos數(shù)(Erdos

number)

:

Erdos本人之Erdos數(shù)為0，任何人若曾與Erdos合寫過論文，則其Erdos數(shù)為1。任何人若曾與一位Erdos數(shù)為l(且不曾與有更少的Erdos數(shù))

的人合寫過論文，

則他的Erdos數(shù)為2…幾乎每一個(gè)當(dāng)代數(shù)學(xué)家都有一個(gè)有限的Erdos數(shù)，而且這個(gè)數(shù)往往非常小，小得出乎本人的預(yù)料。比如說證明Fermat大定理的AndrewWiles，他的研究方向與Erdos相去甚遠(yuǎn)，但他的Erdos數(shù)只有3，是通過這個(gè)途徑實(shí)現(xiàn)的：Erdos--AndrewOdlyzko--ChrisM.Skinner--AndrewWiles.

第7頁/共67頁小世界實(shí)驗(yàn)---Erdos數(shù)

Fields獎得主的Erdos數(shù)都不超過5，（只有Cohen和Grothendieck的Erdos數(shù)是5，）

Nevanlinna獎得主的Erdos數(shù)不超過3，（只有Valiant的Erdos數(shù)是3）Wolf數(shù)學(xué)獎得主的Erdos數(shù)不超過6，（只有V.I.Arnold是6，且只有Kolmogorov是5，）Steele獎的終身成就獎得主的Erdos數(shù)不超過4.在具有有限Erdos數(shù)的人名單中往往還能發(fā)現(xiàn)一些其他領(lǐng)域的專家，如:比爾蓋茲(BillGates)，他的Erdos數(shù)是4，通過如下途徑實(shí)現(xiàn)：Erdos--PavolHell--XiaoTieDeng--ChristosH.Papadimitriou--WilliamH.(Bill)Gates.愛因斯坦是2.

第8頁/共67頁小世界實(shí)驗(yàn)---Bacon數(shù)截止到幾天前，世界電影史上共產(chǎn)生了大約23萬部電影，78多萬名電影演員（參見互聯(lián)網(wǎng)電影庫

）.KavinBacon在許多部電影中飾演小角色。幾年前,Virginia大學(xué)的計(jì)算機(jī)專家BrettTjaden設(shè)計(jì)了一個(gè)游戲，他聲稱電影演員KevinBacon是電影界的中心。在游戲里定義了一個(gè)所謂的Bacon數(shù)：隨便想一個(gè)演員，如果他（她）和KavinBacon一起演過電影，那么他（她）的Bacon數(shù)就為1；如果他（她）沒有和Bacon演過電影，但是和Bacon數(shù)為1的演員一起演過電影，那么他的Bacon數(shù)就為2；以此類推。發(fā)現(xiàn):在曾經(jīng)參演的美國電影演員中，沒有一個(gè)人的Bacon數(shù)超過4。第9頁/共67頁小世界實(shí)驗(yàn)---Bacon數(shù)第10頁/共67頁小世界實(shí)驗(yàn)---Bacon數(shù)在網(wǎng)上有一個(gè)網(wǎng)頁/oracle/。網(wǎng)站的數(shù)據(jù)庫里總共存有有783940個(gè)世界各地的演員的信息以及231,088部電影信息。通過簡單地輸入演員名字就可以知道這個(gè)演員的bacon數(shù)。目前比如輸入StephenChow（周星馳）就可以得到這樣的結(jié)果：周星馳在1991年的《豪門夜宴(Haomenyeyan)》中與洪金寶(SammoHungKam-Bo)合作；而洪金寶又在李小龍的最后一部電影，即1978年的《死亡的游戲（GameofDeath）》中與ColleenCamp合作；ColleenCamp在去年的電影《Trapped》中與KevinBacon合作。這樣周星馳的培根數(shù)為3。是對所有這將近78萬個(gè)演員所做的統(tǒng)計(jì)。結(jié)果如下頁所示:左邊是Bacon數(shù)，右邊是擁有這個(gè)Bacon數(shù)的演員個(gè)數(shù)?？梢钥吹阶畲蟮呐喔鶖?shù)僅僅為8。平均培根數(shù)僅為2.948。第11頁/共67頁小世界實(shí)驗(yàn)---Bacon數(shù)第12頁/共67頁小世界實(shí)驗(yàn)---Bacon數(shù)KavinBacon圖有明確的定義（頂點(diǎn)和邊）數(shù)據(jù)庫中90%的演員被歸入到一個(gè)單獨(dú)的連通分支最高的有限Bacon數(shù)為8平均Bacon數(shù)為2.9注：少數(shù)演員承擔(dān)了將多數(shù)演員聯(lián)系在一起的工作。第13頁/共67頁小世界實(shí)驗(yàn)---用E-mial傳遞,檢驗(yàn)六度分離的假說D.watts2001年開始,18名目標(biāo)對象,166個(gè)國家共6萬多志愿者,平均轉(zhuǎn)發(fā)5—7次第14頁/共67頁outline小世界實(shí)驗(yàn)

六度分離、Erdos數(shù)、bacon數(shù)等一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)

Web、科學(xué)家合作網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、疾病傳播等復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量

度分布、聚類系數(shù)、平均路徑長度等網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì)

隨機(jī)網(wǎng)絡(luò)、SmallWorld網(wǎng)絡(luò)、ScaleFree網(wǎng)絡(luò)等近幾年的研究態(tài)勢

發(fā)展歷程、會議、論文、軟件、實(shí)證等第15頁/共67頁網(wǎng)絡(luò)的拓?fù)湫再|(zhì)網(wǎng)絡(luò)是一個(gè)包含了大量個(gè)體及個(gè)體之間相互作用的系統(tǒng).任何一個(gè)網(wǎng)絡(luò)可以抽象為一個(gè)圖.（最早可追溯到Euler對Konogsberg七橋問題的研究）網(wǎng)絡(luò)的拓?fù)湫再|(zhì)：網(wǎng)絡(luò)不依賴于節(jié)點(diǎn)的具體位置和邊的具體形態(tài)就能表現(xiàn)出來的性質(zhì)。圖的分類:無向圖,有向圖,加權(quán)圖,混合圖簡單圖是指:無向,無權(quán),無重邊,無自環(huán)的圖.目前關(guān)于簡單網(wǎng)絡(luò)的研究結(jié)果較多第16頁/共67頁一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)WebInternet網(wǎng)絡(luò),電影演員合作網(wǎng)絡(luò),科學(xué)家合作網(wǎng)絡(luò),論文引用網(wǎng)絡(luò)電話呼叫網(wǎng)絡(luò)語言學(xué)網(wǎng)絡(luò),電力網(wǎng)絡(luò)經(jīng)濟(jì)網(wǎng)絡(luò),交通網(wǎng)絡(luò)疾病傳播神經(jīng)網(wǎng)絡(luò)人類性關(guān)系網(wǎng)絡(luò),蛋白質(zhì)互作用網(wǎng)絡(luò),蛋白質(zhì)折疊關(guān)系網(wǎng)絡(luò)……..第17頁/共67頁ComplexNetworkExample:WWW-----(K.C.Claffy)

有向網(wǎng)絡(luò)，結(jié)點(diǎn)：web頁面，邊：超鏈第18頁/共67頁ComplexNetworkExample:

Internet

(WilliamR.Cheswick)

無向網(wǎng)絡(luò)，結(jié)點(diǎn)：路由器和計(jì)算機(jī)，邊：通訊設(shè)備（如電纜等）第19頁/共67頁ComplexNetworkExample:TelecommNetworks

(StephenG.Eick)第20頁/共67頁

ComplexNetworkExample:RoutesofAirlines

第21頁/共67頁ComplexNetworkExample:Usenet

(NaveenJamal)第22頁/共67頁ComplexNetworkExample:VLSICircuits,CNN第23頁/共67頁ComplexNetworkExample:BiologicalNetworks第24頁/共67頁ComplexNetworkExample:Arts

第25頁/共67頁一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)Web

有向網(wǎng)絡(luò)，結(jié)點(diǎn)：web頁面，邊：超鏈Internet網(wǎng)絡(luò)無向網(wǎng)絡(luò)，結(jié)點(diǎn)：路由器和計(jì)算機(jī)，邊：通訊設(shè)備（如電纜等）電影演員合作網(wǎng)絡(luò)無向網(wǎng)絡(luò)，結(jié)點(diǎn)：電影演員，邊：兩個(gè)電影演員一起演過電影科學(xué)家合作網(wǎng)絡(luò)無向網(wǎng)絡(luò)，結(jié)點(diǎn)：科學(xué)家，邊：兩個(gè)科學(xué)家一起發(fā)表過一篇論文論文引用網(wǎng)絡(luò)有向網(wǎng)絡(luò)，結(jié)點(diǎn)：論文，有向邊：論文引用電話呼叫網(wǎng)絡(luò)有向網(wǎng)絡(luò)，結(jié)點(diǎn)：電話號碼，有向邊：電話呼叫語言學(xué)網(wǎng)絡(luò)無向網(wǎng)絡(luò)，結(jié)點(diǎn)：單詞，邊：兩個(gè)詞相鄰，（或出現(xiàn)在同一個(gè)句子中，或相同語義）電力網(wǎng)絡(luò)無向網(wǎng)絡(luò)，結(jié)點(diǎn)：發(fā)電廠，電站，接轉(zhuǎn)站。邊：高壓線經(jīng)濟(jì)網(wǎng)絡(luò),交通網(wǎng)絡(luò)疾病傳播神經(jīng)網(wǎng)絡(luò)人類性關(guān)系網(wǎng)絡(luò),蛋白質(zhì)互作用網(wǎng)絡(luò),蛋白質(zhì)折疊關(guān)系網(wǎng)絡(luò)……..第26頁/共67頁outline小世界實(shí)驗(yàn)

六度分離、Erdos數(shù)、bacon數(shù)等一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)

Web、科學(xué)家合作網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、疾病傳播等復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量

度分布、聚類系數(shù)、平均路徑長度等網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì)

隨機(jī)網(wǎng)絡(luò)、SmallWorld網(wǎng)絡(luò)、ScaleFree網(wǎng)絡(luò)等近幾年的研究態(tài)勢

發(fā)展歷程、會議、論文、軟件、實(shí)證等第27頁/共67頁復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量度分布（degreedistribution）聚類系數(shù)(clusteringcoefficient)平均路徑長度(averagepathlength)無向網(wǎng)絡(luò)的基本幾何量有:度及其分布特征,度的相關(guān)性,集聚程度及其分布特征,最短距離及其分布特征,介數(shù)(Betweenness)及其分布特征,連通集團(tuán)的規(guī)模分布有向網(wǎng)絡(luò)的特殊靜態(tài)幾何量包括:In度和Out度的分布特征,基于頂點(diǎn)的In-Out度關(guān)聯(lián)性,基于邊的(In-Out,In-In,Out-In,Out-Out)度關(guān)聯(lián)性,雙向比,In集團(tuán)和Out集團(tuán)的集聚程度。加權(quán)網(wǎng)絡(luò)的靜態(tài)幾何量包括:度及其分布特征,權(quán)及其分布特征,權(quán)的相關(guān)性,權(quán)與度的相關(guān)性,最短距離及其分布特征,介數(shù)及其分布特征與隧道現(xiàn)象,與相應(yīng)無權(quán)網(wǎng)絡(luò)的對比,距離關(guān)系與類聚分析,以及在加權(quán)網(wǎng)絡(luò)上集聚程度的定義及其統(tǒng)計(jì)性質(zhì)。第28頁/共67頁平均路徑長度(averagepathlength)網(wǎng)絡(luò)中兩個(gè)頂點(diǎn)i，j之間的最短路徑定義為所有連通(i,j)的通路中,所經(jīng)過的其他頂點(diǎn)最少的一條或幾條路徑。兩個(gè)頂點(diǎn)i，j之間的距離dij定義為i，j之間最短路徑上的邊數(shù)。網(wǎng)絡(luò)的直徑(diameter),定義為網(wǎng)絡(luò)中任意兩個(gè)頂點(diǎn)之間距離的最大值。網(wǎng)絡(luò)的平均路徑長度(averagepathlength),定義為網(wǎng)絡(luò)中任意兩個(gè)頂點(diǎn)之間距離的平均值。即：第29頁/共67頁聚類系數(shù)(clusteringcoefficient)

在朋友關(guān)系網(wǎng)中，你的兩個(gè)朋友很可能彼此也是朋友。這種屬性稱為網(wǎng)絡(luò)的聚類特性。用數(shù)學(xué)化的語言來說，對于某個(gè)節(jié)點(diǎn)i，它的聚類系數(shù)Ci被定義為它所有相鄰節(jié)點(diǎn)之間連的數(shù)目占可能的最大連邊數(shù)目的比例。整個(gè)網(wǎng)絡(luò)的聚類系數(shù)C則是所有節(jié)點(diǎn)聚類系數(shù)的平均值。在隨機(jī)網(wǎng)絡(luò)中，C=p,（由于邊的分布是隨機(jī)的）第30頁/共67頁度分布（degreedistribution）一個(gè)頂點(diǎn)的度是指與此頂點(diǎn)連接的邊的數(shù)量。在有向網(wǎng)絡(luò)中，分為：出度，入度研究包括：度及其分布特征，度的相關(guān)性。度值的分布特征是網(wǎng)絡(luò)的重要幾何性質(zhì)。規(guī)則網(wǎng)絡(luò)各頂點(diǎn)度值相同，因而符合delta分布隨機(jī)網(wǎng)絡(luò)符合泊松分布大量實(shí)際網(wǎng)絡(luò)存在冪律(power-law)形式的度分布，即無標(biāo)度網(wǎng)絡(luò)（ScaleFreeNetworks）。無標(biāo)度網(wǎng)絡(luò)包括Internet網(wǎng)絡(luò)，電影與電視劇演員合作網(wǎng)絡(luò)，科學(xué)家合作網(wǎng)絡(luò)，人類性關(guān)系網(wǎng)絡(luò)，蛋白質(zhì)互作用網(wǎng)絡(luò)，語言學(xué)網(wǎng)絡(luò)等，同時(shí)還存在高斯型，如蛋白質(zhì)折疊網(wǎng)絡(luò)和指數(shù)衰減型的概率分布。度的相關(guān)性：Newman把它稱為“匹配模式”，意思是考察度值大的點(diǎn)傾向于和度值大的點(diǎn)連接，還是傾向于和度值小的點(diǎn)連接。實(shí)際網(wǎng)絡(luò)的分析表明，不同的網(wǎng)絡(luò)存在不同的匹配模式，有正相關(guān)也有負(fù)相關(guān)。（有向網(wǎng)絡(luò)中）基于頂點(diǎn)的In-Out度關(guān)聯(lián)性。第31頁/共67頁outline小世界實(shí)驗(yàn)

六度分離、Erdos數(shù)、bacon數(shù)等一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)

Web、科學(xué)家合作網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、疾病傳播等復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量

度分布、聚類系數(shù)、平均路徑長度等網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì)

隨機(jī)網(wǎng)絡(luò)、SmallWorld網(wǎng)絡(luò)、ScaleFree網(wǎng)絡(luò)等近幾年的研究態(tài)勢

發(fā)展歷程、會議、論文、軟件、實(shí)證等第32頁/共67頁網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì)

規(guī)則網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)SmallWorld網(wǎng)絡(luò)ScaleFree網(wǎng)絡(luò)等級網(wǎng)絡(luò)第33頁/共67頁規(guī)則網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò)是指平移對稱性晶格,任何一個(gè)格點(diǎn)的近鄰數(shù)目都相同。各個(gè)節(jié)點(diǎn)的具有相同的度值如圖為最近鄰耦合網(wǎng)絡(luò)：每個(gè)節(jié)點(diǎn)都與它左右的K/2個(gè)節(jié)點(diǎn)相連。對大的N,K,有：聚類系數(shù)C~3/4,平均路徑長度L~無窮大一般地，規(guī)則網(wǎng)絡(luò)具有大的簇系數(shù)和大的平均距離第34頁/共67頁隨機(jī)網(wǎng)絡(luò)ER隨機(jī)圖模型：頂點(diǎn)的度值服從Poissondistribution，也稱Poisson隨機(jī)圖如：pajek的生成平均度：k~p*N平均路徑長度L~ln(N)/ln(k)聚類系數(shù):C=p<<1(由于極度稀疏)一般地，隨機(jī)網(wǎng)絡(luò)具有小的簇系數(shù)和小的平均距離。第35頁/共67頁SmallWorld模型

是否存在一個(gè)同時(shí)具有高的集聚程度,小的最短路徑網(wǎng)絡(luò)呢?對于傳染病模型,平均集聚程度對應(yīng)于傳播的廣度,平均最短距離代表的是傳播的深度。因此,如果實(shí)際網(wǎng)絡(luò)同時(shí)存在寬的廣度和大的深度的話,在這樣的網(wǎng)絡(luò)上的傳染病傳播顯然將大大高于規(guī)則網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)。1998年Watts和Strogatz為我們找到了這樣的網(wǎng)絡(luò)模型—SmallWorld網(wǎng)絡(luò)（發(fā)表在Nature上）.現(xiàn)在常稱為：WSmodel第36頁/共67頁SmallWorld模型方法：Watts和Strogatz發(fā)現(xiàn),只需要在規(guī)則網(wǎng)絡(luò)上稍作隨機(jī)改動就可以同時(shí)具備以上兩個(gè)性質(zhì)。改動的方法是,對于規(guī)則網(wǎng)絡(luò)的每一個(gè)頂點(diǎn)的所有邊,以概率p斷開一個(gè)端點(diǎn),并重新連接,連接的新的端點(diǎn)從網(wǎng)絡(luò)中的其他頂點(diǎn)里隨機(jī)選擇,如果所選的頂點(diǎn)已經(jīng)與此頂點(diǎn)相連,則再隨機(jī)選擇別的頂點(diǎn)來重連。當(dāng)p=0時(shí)就是規(guī)則網(wǎng)絡(luò),p=1則為隨機(jī)網(wǎng)絡(luò),對于0<p<1的情況,存在一個(gè)很大的p的區(qū)域,同時(shí)擁有較大的集聚程度和較小的最小距離。形成機(jī)制：規(guī)則網(wǎng)絡(luò)，以概率p斷開一個(gè)端點(diǎn)，隨機(jī)連接）第37頁/共67頁NW模型WSmodel的構(gòu)造過程有可能破壞網(wǎng)絡(luò)的連通性1999年NewmanandWatts提出了NW模型：用“隨機(jī)化加邊”替代“隨機(jī)化重連”還有許多改進(jìn)的模型：加點(diǎn)，加邊，去點(diǎn)，去邊，以及不同形式的交叉，產(chǎn)生多種形式的小世界模型第38頁/共67頁實(shí)際的SmallWorld網(wǎng)絡(luò)第39頁/共67頁ScaleFree網(wǎng)絡(luò)節(jié)點(diǎn)度服從冪律分布，就是說具有某個(gè)特定度的節(jié)點(diǎn)數(shù)目與這個(gè)特定的度之間的關(guān)系可以用一個(gè)冪函數(shù)近似地表示。冪函數(shù)曲線是一條下降相對緩慢的曲線，這使得度很大的節(jié)點(diǎn)可以在網(wǎng)絡(luò)中存在。對于隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)，度分布區(qū)間非常狹窄，幾乎找不到偏離節(jié)點(diǎn)度均值較大的點(diǎn)，故其平均度可以被看作其節(jié)點(diǎn)度的一個(gè)特征標(biāo)度。在這個(gè)意義上，我們把節(jié)點(diǎn)度服從冪律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)（scale-freenetworks），并稱這種節(jié)點(diǎn)度的冪律分布為網(wǎng)絡(luò)的無標(biāo)度特性。第40頁/共67頁ScaleFree網(wǎng)絡(luò)1999年，Barabási和Albert給出了構(gòu)造無標(biāo)度網(wǎng)絡(luò)的演化模型。形成機(jī)制：生長和擇優(yōu)連接取初始m0個(gè)頂點(diǎn)任意連接或完全連接。每一步在原網(wǎng)絡(luò)G(t-1)的基礎(chǔ)上加上一個(gè)新的頂點(diǎn),同時(shí)加上從此頂點(diǎn)出發(fā)的m條邊,形成新的網(wǎng)絡(luò)G(t)。其中新加邊的另一個(gè)端點(diǎn)按照正比于頂點(diǎn)度數(shù)的分布。隨機(jī)選取。重復(fù)以上新加點(diǎn)的過程足夠多步所形成的網(wǎng)絡(luò)的各頂點(diǎn)的度滿足冪律分布p(k)~

k^(-γ)。而且,指數(shù)γ=3與模型的參數(shù)m0,m無關(guān)。進(jìn)一步的數(shù)值模擬表明,當(dāng)m取某一范圍內(nèi)的隨機(jī)數(shù)時(shí),指數(shù)也不變?，F(xiàn)在常稱為：BAModel第41頁/共67頁ScaleFree網(wǎng)絡(luò)第42頁/共67頁等級網(wǎng)絡(luò)(Hierarchicalnetwork)以模塊生成等級網(wǎng)絡(luò)實(shí)例具有:scale-free特征第43頁/共67頁outline小世界實(shí)驗(yàn)

六度分離、Erdos數(shù)、bacon數(shù)等一些實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)

Web、科學(xué)家合作網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、疾病傳播等復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量

度分布、聚類系數(shù)、平均路徑長度等網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì)

隨機(jī)網(wǎng)絡(luò)、SmallWorld網(wǎng)絡(luò)、ScaleFree網(wǎng)絡(luò)等近幾年的研究態(tài)勢

發(fā)展歷程、會議、論文、軟件、實(shí)證等第44頁/共67頁復(fù)雜網(wǎng)絡(luò)研究簡史過去講究較小規(guī)模的網(wǎng)絡(luò)第45頁/共67頁國內(nèi)外的研究情況從2002年起，國內(nèi)不同學(xué)科的研究人員和青年學(xué)者對復(fù)雜網(wǎng)絡(luò)研究的興趣越來越濃，至今國內(nèi)已召開過多次以復(fù)雜網(wǎng)絡(luò)為主題的學(xué)術(shù)會議和論壇2004年4月在無錫組織了有40余人參加的首屆全國復(fù)雜動態(tài)網(wǎng)絡(luò)學(xué)術(shù)論壇。武漢大學(xué)在國內(nèi)率先成立了校級復(fù)雜網(wǎng)絡(luò)研究中心并于2005年春季組織了全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議2005年10月在北京召開的由中國高等學(xué)術(shù)研究中心組織的第二屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)論壇一些國際著名大學(xué)（如MIT，哥倫比亞大學(xué)和密歇根大學(xué)等）已相繼開設(shè)了有關(guān)復(fù)雜網(wǎng)絡(luò)的課程，汪小帆教授也在上海交通大學(xué)為研究生開設(shè)了復(fù)雜網(wǎng)絡(luò)課程。2006年10月武漢會議第46頁/共67頁2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議第47頁/共67頁復(fù)雜網(wǎng)絡(luò)中理論及其應(yīng)用--book第48頁/共67頁復(fù)雜網(wǎng)絡(luò)中理論及其應(yīng)用--book第49頁/共67頁復(fù)雜網(wǎng)絡(luò)的主要研究內(nèi)容實(shí)證研究結(jié)合應(yīng)用的研究簡單的如：LibraryAndInformationScienceAbstracts(LISA)圖書館與信息科學(xué)文摘庫中1996年－2005年所有的英文論文數(shù)據(jù)，共109249條教育網(wǎng)數(shù)據(jù)第50頁/共67頁教育網(wǎng)數(shù)據(jù):對xzm搜集的edu數(shù)據(jù)網(wǎng)頁數(shù)量〉1000，有376個(gè)，鏈接關(guān)系圖第51頁/共67頁教育網(wǎng)數(shù)據(jù)--input50個(gè)（入度大小.按網(wǎng)絡(luò)影響因子核心站點(diǎn)？）第52頁/共67頁教育網(wǎng)數(shù)據(jù)-output34個(gè)（按出度大小）第53頁/共67頁情報(bào)學(xué)報(bào)第54頁/共67頁P(yáng)apers:ComplexNetworks

SCIpapersEIpapers第55頁/共67頁P(yáng)apers:Small-WorldNetworks

SCIpapersEIpapers第56頁/共67頁P(yáng)apers:Scale-FreeNetworks

SCIpapersEIpapers第57頁/共67頁面臨的挑戰(zhàn)性課題20世紀(jì)美國最有影響的五十人物之一E.O.Wilson指出:"今天最大的挑戰(zhàn)性,不僅是細(xì)胞生物學(xué)和生態(tài)學(xué),而是科學(xué)的所有方面,特別是如何精確地和完全地描述復(fù)雜系統(tǒng).科學(xué)家已經(jīng)認(rèn)識了許多類型的復(fù)雜系統(tǒng).他們認(rèn)為已經(jīng)知道系統(tǒng)中大多數(shù)元素和受力況.下一步的任務(wù)就是怎么綜合起來,至少在數(shù)學(xué)模型方面必須抓住整個(gè)系綜的關(guān)鍵性質(zhì)."如下為中國原子能科學(xué)研究院方錦清列舉:

挑戰(zhàn)性問題之一,從理論上急待深入探索復(fù)雜動態(tài)網(wǎng)絡(luò)的數(shù)學(xué)物理模型,建立精確的理論框架,例如,統(tǒng)一混合擇優(yōu)理論,六度分離理論,無標(biāo)度特性,多標(biāo)度特性和超家族特性,以及量子信息網(wǎng)絡(luò)等,這是網(wǎng)絡(luò)發(fā)展面臨的一大課題.挑戰(zhàn)性問題之二,探索從隨機(jī)方法,確定性方法,到多種混合方法,以及不同網(wǎng)絡(luò)特性的互相轉(zhuǎn)變關(guān)系,從而構(gòu)造符合實(shí)際要求和工程應(yīng)用的復(fù)雜網(wǎng)絡(luò).

挑戰(zhàn)性問題之三,復(fù)雜網(wǎng)絡(luò)是否存在普遍動力學(xué)性質(zhì),是否存