復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用PPT課件

1、簡(jiǎn)介簡(jiǎn)介: : 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用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ù)、平均路徑長(zhǎng)度等 網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì) 隨機(jī)網(wǎng)絡(luò)、Small World網(wǎng)絡(luò)、Scale Free網(wǎng)絡(luò)等 近幾年的研究態(tài)勢(shì) 發(fā)展歷程、會(huì)議、論文、軟件、實(shí)證等小世界實(shí)驗(yàn)- 六度分離 我們或許有過這樣的經(jīng)歷：偶爾碰到一個(gè)陌生人，同他聊了一會(huì)后發(fā)現(xiàn)你認(rèn)識(shí)的某個(gè)人居然他也認(rèn)識(shí)，然后一起發(fā)出”這個(gè)世界真小”的感嘆。那么對(duì)于世界上任意兩個(gè)人來說，借助第三者、第

2、四者這樣的間接關(guān)系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人呢？ 美國(guó)社會(huì)心理學(xué)家斯坦利米爾格倫(Stanley Milgram)在1967年通過一些實(shí)驗(yàn)后得出結(jié)論：中間的聯(lián)系人平均只需要5個(gè)。他把這個(gè)結(jié)論稱為”六度分離”(six degrees of separation)。 六度分離: 平均只要通過5個(gè)人，你就能與世界任何一個(gè)角落的任何一個(gè)人發(fā)生聯(lián)系。這個(gè)結(jié)論定量地說明了我們世界的”大小”，或者說人與人關(guān)系的緊密程度。 30多年來，六度分離理論一直被作為社會(huì)心理學(xué)的經(jīng)典范例之一。 盡管如此，實(shí)際上這個(gè)理論并沒有得到嚴(yán)格的證實(shí)。美國(guó)心理學(xué)教授朱迪斯克蘭菲爾德(Judith Kleinfe

3、ld)對(duì)米爾格倫最初的實(shí)驗(yàn)提出不同意見，因?yàn)樗l(fā)現(xiàn)實(shí)驗(yàn)的完成率極低。小世界實(shí)驗(yàn)- 六度分離 米爾格倫的實(shí)驗(yàn)過程是：他計(jì)劃通過人傳人的送信方式來統(tǒng)計(jì)人與人之間的聯(lián)系。 首先把信交給志愿者A，告訴他信最終要送給收信人S。如果他不認(rèn)識(shí)S，那么就送信到某個(gè)他認(rèn)識(shí)的人B手里，理由是A認(rèn)為在他的交集圈里B是最可能認(rèn)識(shí)S的。但是如果B也不認(rèn)識(shí)S，那么B同樣把信送到他的一個(gè)朋友C手中，就這樣一步步最后信終于到達(dá)S哪里。這樣就從A到B到C到最后到S連成了一個(gè)鏈。斯坦利米爾格倫就是通過對(duì)這個(gè)鏈做了統(tǒng)計(jì)后做出了六度分離的結(jié)論。 然而在這個(gè)實(shí)驗(yàn)中，實(shí)際上只有三分之一的信送到了收信人哪里，因此實(shí)驗(yàn)的完成率很低。 小世界

4、實(shí)驗(yàn)-ErdosErdos數(shù)數(shù) Paul Erdos(1913-1996)， 出生于匈牙利的猶太籍?dāng)?shù)學(xué)家，被公認(rèn)為本世紀(jì)最偉大的天才之一。 Erdos畢生發(fā)表的論文超過1500篇（在數(shù)學(xué)史上僅次于歐拉(Euler ，1707-1783)，超長(zhǎng)的合作者名單,合作者超過450位。但若加上別人所做但曾獲他關(guān)鍵性的提示之論文，則他的論文應(yīng)有數(shù)萬篇。 他的研究領(lǐng)域主要是數(shù)論和組合數(shù)學(xué)，但他的論文中涵蓋的學(xué)科有逼近論、初等幾何、集合論、概率論、數(shù)理邏輯、格與序代數(shù)結(jié)構(gòu)、線性代數(shù)、群論、拓?fù)淙骸⒍囗?xiàng)式、測(cè)度論、單復(fù)變函數(shù)、差分方程與函數(shù)方程、數(shù)列、Fourier分析、泛函分析、一般拓?fù)浜痛鷶?shù)拓?fù)洹⒔y(tǒng)計(jì)、數(shù)值

5、分析、計(jì)算機(jī)科學(xué)、信息論等等。 Mathematical Reviews 曾把數(shù)學(xué)劃分為大約六十個(gè)分支，Erdos的論文涉及到了其中的40%. 小世界實(shí)驗(yàn)-ErdosErdos數(shù)數(shù) Erdos從來沒有一固定的職位，從來不定居在一個(gè)地方，也沒有結(jié)婚，帶著一半空的手提箱，穿梭于學(xué)術(shù)研討會(huì)，浪跡天涯，頗富傳奇色彩。有人稱他為流浪學(xué)者(wande ring scholar)。 他效忠的是科學(xué)的皇后， 而非一特定的地方。各地都有熱心的數(shù)學(xué)家提供他舒適的食宿，安排他的一切，他則對(duì)招待他的主人，給出一些挑戰(zhàn)性的數(shù)學(xué)難題，或給予研究上的指導(dǎo)做為回饋。 他可以和許多不同領(lǐng)域的數(shù)學(xué)家合作。數(shù)學(xué)家常將本身長(zhǎng)久解決不

6、了的問題和他討論，于是很快地一篇論文便誕生了。 小世界實(shí)驗(yàn)-ErdosErdos數(shù)數(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大定理的Andrew Wiles，他的研究方向與Erdos相去甚遠(yuǎn)，但他的Erdos數(shù)只有3，是通過這個(gè)途徑實(shí)現(xiàn)的：Erdos-Andr

7、ew Odlyzko-Chris M.Skinner-Andrew Wiles. 小世界實(shí)驗(yàn)-ErdosErdos數(shù)數(shù) Fields獎(jiǎng)得主的Erdos數(shù)都不超過5，（只有Cohen和Grothendieck的Erdos數(shù)是5，） Nevanlinna獎(jiǎng)得主的Erdos數(shù)不超過3，（只有Valiant的Erdos數(shù)是3） Wolf數(shù)學(xué)獎(jiǎng)得主的Erdos數(shù)不超過6，（只有V.I.Arnold是6，且只有Kolmogorov是5，） Steele獎(jiǎng)的終身成就獎(jiǎng)得主的Erdos數(shù)不超過4. 在具有有限Erdos數(shù)的人名單中往往還能發(fā)現(xiàn)一些其他領(lǐng)域的專家，如: 比爾蓋茲(Bill Gates)， 他的E

8、rdos數(shù)是4，通過如下途徑實(shí)現(xiàn)：Erdos-Pavol Hell-Xiao Tie Deng-Christos H. Papadimitriou-William H. (Bill) Gates. 愛因斯坦是2.小世界實(shí)驗(yàn)- Bacon數(shù) 截止到幾天前，世界電影史上共產(chǎn)生了大約23萬部電影，78多萬名電影演員（參見互聯(lián)網(wǎng)電影庫(kù) ）. Kavin Bacon在許多部電影中飾演小角色。 幾年前,Virginia 大學(xué)的計(jì)算機(jī)專家Brett Tjaden設(shè)計(jì)了一個(gè)游戲，他聲稱電影演員Kevin Bacon是電影界的中心。 在游戲里定義了一個(gè)所謂的Bacon數(shù)：隨便想一個(gè)演員，如果他（她）和Kavin

9、 Bacon一起演過電影，那么他（她）的Bacon數(shù)就為1；如果他（她）沒有和Bacon演過電影，但是和Bacon數(shù)為1的演員一起演過電影，那么他的Bacon數(shù)就為2；以此類推。 發(fā)現(xiàn): 在曾經(jīng)參演的美國(guó)電影演員中，沒有一個(gè)人的Bacon數(shù)超過4。小世界實(shí)驗(yàn)- Bacon數(shù)小世界實(shí)驗(yàn)- Bacon數(shù) 在網(wǎng)上有一個(gè)網(wǎng)頁(yè)/oracle/。網(wǎng)站的數(shù)據(jù)庫(kù)里總共存有有783940個(gè)世界各地的演員的信息以及231,088部電影信息。 通過簡(jiǎn)單地輸入演員名字就可以知道這個(gè)演員的bacon數(shù)。目前比如輸入Stephen Chow（周星馳）就可以得到這樣的結(jié)果：

10、周星馳在1991年的豪門夜宴(Haomen yeyan) 中與洪金寶(Sammo Hung Kam-Bo)合作；而洪金寶又在李小龍的最后一部電影，即1978年的死亡的游戲 （Game of Death） 中與 Colleen Camp 合作；Colleen Camp 在去年的電影Trapped 中與Kevin Bacon 合作。這樣周星馳的培根數(shù)為3。 是對(duì)所有這將近78萬個(gè)演員所做的統(tǒng)計(jì)。結(jié)果如下頁(yè)所示: 左邊是Bacon數(shù)，右邊是擁有這個(gè)Bacon數(shù)的演員個(gè)數(shù)。可以看到最大的培根數(shù)僅僅為8。平均培根數(shù)僅為2.948。 小世界實(shí)驗(yàn)- Bacon數(shù)小世界實(shí)驗(yàn)- Bacon數(shù) Kavin Bac

11、on圖 有明確的定義（頂點(diǎn)和邊） 數(shù)據(jù)庫(kù)中90%的演員被歸入到一個(gè)單獨(dú)的連通分支 最高的有限Bacon數(shù)為8 平均Bacon數(shù)為2.9 注：少數(shù)演員承擔(dān)了將多數(shù)演員聯(lián)系在一起的工作。小世界實(shí)驗(yàn)-用用E-mialE-mial傳遞傳遞, ,檢驗(yàn)六度分離的假說檢驗(yàn)六度分離的假說D. wattsD. watts20012001年開始年開始, ,1818名目標(biāo)對(duì)象名目標(biāo)對(duì)象, , 166166個(gè)國(guó)家共個(gè)國(guó)家共6 6萬多志愿者萬多志愿者, ,平均轉(zhuǎn)發(fā)平均轉(zhuǎn)發(fā)5 57 7次次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ò)

12、、疾病傳播等 復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量 度分布、聚類系數(shù)、平均路徑長(zhǎng)度等 網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì) 隨機(jī)網(wǎng)絡(luò)、Small World網(wǎng)絡(luò)、Scale Free網(wǎng)絡(luò)等 近幾年的研究態(tài)勢(shì) 發(fā)展歷程、會(huì)議、論文、軟件、實(shí)證等網(wǎng)絡(luò)的拓?fù)湫再|(zhì) 網(wǎng)絡(luò)是一個(gè)包含了大量個(gè)體及個(gè)體之間相互作用的系統(tǒng). 任何一個(gè)網(wǎng)絡(luò)可以抽象為一個(gè)圖.（最早可追溯到Euler對(duì)Konogsberg七橋問題的研究） 網(wǎng)絡(luò)的拓?fù)湫再|(zhì)：網(wǎng)絡(luò)不依賴于節(jié)點(diǎn)的具體位置和邊的具體形態(tài)就能表現(xiàn)出來的性質(zhì)。 圖的分類: 無向圖, 有向圖,加權(quán)圖, 混合圖 簡(jiǎn)單圖是指: 無向,無權(quán),無重邊,無自環(huán)的圖. 目前關(guān)于簡(jiǎn)單網(wǎng)絡(luò)的研究結(jié)果較多一些實(shí)際的復(fù)雜網(wǎng)絡(luò)

13、系統(tǒng) Web Internet 網(wǎng)絡(luò), 電影演員合作網(wǎng)絡(luò), 科學(xué)家合作網(wǎng)絡(luò), 論文引用網(wǎng)絡(luò) 電話呼叫網(wǎng)絡(luò) 語(yǔ)言學(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ò) .Complex Network Example: WWW - (K. (K. C. Claffy)C. Claffy) 有向網(wǎng)絡(luò)， 結(jié)點(diǎn)：web頁(yè)面，邊：超鏈Complex Network Example: Internet (William R. (William R. Cheswick)Cheswick) 無向網(wǎng)絡(luò)， 結(jié)點(diǎn)：路由器和計(jì)算機(jī)， 邊：通訊設(shè)備（如電纜

14、等）Complex Network Example: Telecomm Networks ( S t e p h e n G . E i c k ) Complex Network Example: Routes of AirlinesComplex Network Example: Usenet ( N a v e e n J a m a l )Complex Network Example: VLSI Circuits, CNNComplex Network Example: Biological NetworksComplex Network Example: Arts 一些實(shí)際的復(fù)雜網(wǎng)

15、絡(luò)系統(tǒng)Web 有向網(wǎng)絡(luò)， 結(jié)點(diǎn)：web頁(yè)面，邊：超鏈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)：電話號(hào)碼，有向邊：電話呼叫語(yǔ)言學(xué)網(wǎng)絡(luò) 無向網(wǎng)絡(luò)， 結(jié)點(diǎn)：?jiǎn)卧~， 邊：兩個(gè)詞相鄰，（或出現(xiàn)在同一個(gè)句子中，或相同語(yǔ)義）電力網(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)系

16、網(wǎng)絡(luò),蛋白質(zhì)互作用網(wǎng)絡(luò),蛋白質(zhì)折疊關(guān)系網(wǎng)絡(luò).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ù)、平均路徑長(zhǎng)度等 網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì) 隨機(jī)網(wǎng)絡(luò)、Small World網(wǎng)絡(luò)、Scale Free網(wǎng)絡(luò)等 近幾年的研究態(tài)勢(shì) 發(fā)展歷程、會(huì)議、論文、軟件、實(shí)證等復(fù)雜網(wǎng)絡(luò)的靜態(tài)幾何量 度分布（degree distribution） 聚類系數(shù) (clustering coefficient) 平均路徑長(zhǎng)度(average path length) 無向網(wǎng)絡(luò)的基本幾何

17、量有: 度及其分布特征,度的相關(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ò)的對(duì)比,距離關(guān)系與類聚分析,以及在加權(quán)網(wǎng)絡(luò)上集聚程度的定義及其統(tǒng)

18、計(jì)性質(zhì)。平均路徑長(zhǎng)度(average path length) 網(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ò)的平均路徑長(zhǎng)度(average path length), 定義為網(wǎng)絡(luò)中任意兩個(gè)頂點(diǎn)之間距離的平均值。即：2/NjiijCdL聚類系數(shù) (clustering coefficient) 在朋友關(guān)系網(wǎng)中，你的兩個(gè)朋友很可能彼此也是朋友。這種屬性稱為網(wǎng)絡(luò)的聚類特性。 用數(shù)學(xué)化的語(yǔ)言

19、來說，對(duì)于某個(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ī)的） 度分布（degree distribution） 一個(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ò)（Scale Free Networks）。 無標(biāo)度網(wǎng)絡(luò)

20、包括Internet網(wǎng)絡(luò)，電影與電視劇演員合作網(wǎng)絡(luò)，科學(xué)家合作網(wǎng)絡(luò)，人類性關(guān)系網(wǎng)絡(luò)，蛋白質(zhì)互作用網(wǎng)絡(luò)，語(yǔ)言學(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)性。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ù)、

21、平均路徑長(zhǎng)度等 網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì) 隨機(jī)網(wǎng)絡(luò)、Small World網(wǎng)絡(luò)、Scale Free網(wǎng)絡(luò)等 近幾年的研究態(tài)勢(shì) 發(fā)展歷程、會(huì)議、論文、軟件、實(shí)證等網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì) 規(guī)則網(wǎng)絡(luò) 隨機(jī)網(wǎng)絡(luò) Small World網(wǎng)絡(luò) Scale Free網(wǎng)絡(luò) 等級(jí)網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò) 規(guī)則網(wǎng)絡(luò)是指平移對(duì)稱性晶格,任何一個(gè)格點(diǎn)的近鄰數(shù)目都相同。 各個(gè)節(jié)點(diǎn)的具有相同的度值 如圖為最近鄰耦合網(wǎng)絡(luò)：每個(gè)節(jié)點(diǎn)都與它左右的K/2個(gè)節(jié)點(diǎn)相連。 對(duì)大的N, K, 有：聚類系數(shù)C3/4, 平均路徑長(zhǎng)度L無窮大 一般地，規(guī)則網(wǎng)絡(luò)具有大的簇系數(shù)和大的平均距離隨機(jī)網(wǎng)絡(luò) ER隨機(jī)圖模型：頂點(diǎn)的度值服從 Poisson di

22、stribution，也稱Poisson隨機(jī)圖 如：pajek的生成 平均度：kp*N 平均路徑長(zhǎng)度Lln(N)/ln(k) 聚類系數(shù): C=p 1 (由于極度稀疏) 一般地，隨機(jī)網(wǎng)絡(luò)具有小的簇系數(shù)和小的平均距離。 Small World Small World模型模型 是否存在一個(gè)同時(shí)具有高的集聚程度,小的最短路徑網(wǎng)絡(luò)呢? 對(duì)于傳染病模型, 平均集聚程度對(duì)應(yīng)于傳播的廣度,平均最短距離代表的是傳播的深度。 因此,如果實(shí)際網(wǎng)絡(luò)同時(shí)存在寬的廣度和大的深度的話,在這樣的網(wǎng)絡(luò)上的傳染病傳播顯然將大大高于規(guī)則網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)。 1998年Watts和Strogatz 為我們找到了這樣的網(wǎng)絡(luò)模型Small

23、World 網(wǎng)絡(luò)（發(fā)表在Nature上）. 現(xiàn)在常稱為：WS modelSmall WorldSmall World模型模型 方法：Watts和Strogatz 發(fā)現(xiàn),只需要在規(guī)則網(wǎng)絡(luò)上稍作隨機(jī)改動(dòng)就可以同時(shí)具備以上兩個(gè)性質(zhì)。 改動(dòng)的方法是,對(duì)于規(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ò),對(duì)于0 p 1 的情況,存在一個(gè)很大的p 的區(qū)域,同時(shí)擁有較大的集聚程度和較小的最小距離。 形成機(jī)制：規(guī)則網(wǎng)絡(luò)，以概率p 斷

24、開一個(gè)端點(diǎn)，隨機(jī)連接）NWNW模型模型 WS model的構(gòu)造過程有可能破壞網(wǎng)絡(luò)的連通性 1999年Newman and Watts提出了NW模型：用“隨機(jī)化加邊”替代“隨機(jī)化重連” 還有許多改進(jìn)的模型：加點(diǎn)，加邊，去點(diǎn)，去邊， 以及不同形式的交叉，產(chǎn)生多種形式的小世界模型實(shí)際的Small World網(wǎng)絡(luò)Scale Free網(wǎng)絡(luò) 節(jié)點(diǎn)度服從冪律分布，就是說具有某個(gè)特定度的節(jié)點(diǎn)數(shù)目與這個(gè)特定的度之間的關(guān)系可以用一個(gè)冪函數(shù)近似地表示。 冪函數(shù)曲線是一條下降相對(duì)緩慢的曲線，這使得度很大的節(jié)點(diǎn)可以在網(wǎng)絡(luò)中存在。 對(duì)于隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)，度分布區(qū)間非常狹窄，幾乎找不到偏離節(jié)點(diǎn)度均值較大的點(diǎn)，故其平均度可

25、以被看作其節(jié)點(diǎn)度的一個(gè)特征標(biāo)度。在這個(gè)意義上，我們把節(jié)點(diǎn)度服從冪律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)（scale-free networks），并稱這種節(jié)點(diǎn)度的冪律分布為網(wǎng)絡(luò)的無標(biāo)度特性。 Scale FreeScale Free網(wǎng)絡(luò)網(wǎng)絡(luò) 1999年，Barabsi 和Albert給出了構(gòu)造無標(biāo)度網(wǎng)絡(luò)的演化模型。 形成機(jī)制：生長(zhǎng)和擇優(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)

26、的度滿足冪律分布p ( k) k( -) 。而且,指數(shù)= 3 與模型的參數(shù)m0 , m 無關(guān)。 進(jìn)一步的數(shù)值模擬表明,當(dāng)m 取某一范圍內(nèi)的隨機(jī)數(shù)時(shí),指數(shù)也不變。 現(xiàn)在常稱為： BA ModelScale Free網(wǎng)絡(luò)等級(jí)網(wǎng)絡(luò)等級(jí)網(wǎng)絡(luò)(Hierarchical network)(Hierarchical network) 以模塊生成等級(jí)網(wǎng)絡(luò)實(shí)例 具有:scale-free特征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ù)、平均路徑長(zhǎng)度等 網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图?/p>

27、其性質(zhì) 隨機(jī)網(wǎng)絡(luò)、Small World網(wǎng)絡(luò)、Scale Free網(wǎng)絡(luò)等 近幾年的研究態(tài)勢(shì) 發(fā)展歷程、會(huì)議、論文、軟件、實(shí)證等復(fù)雜網(wǎng)絡(luò)研究簡(jiǎn)史過去講究較小規(guī)模的網(wǎng)絡(luò)國(guó)內(nèi)外的研究情況 從2002年起，國(guó)內(nèi)不同學(xué)科的研究人員和青年學(xué)者對(duì)復(fù)雜網(wǎng)絡(luò)研究的興趣越來越濃，至今國(guó)內(nèi)已召開過多次以復(fù)雜網(wǎng)絡(luò)為主題的學(xué)術(shù)會(huì)議和論壇 2004年4月在無錫組織了有40余人參加的首屆全國(guó)復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)學(xué)術(shù)論壇。 武漢大學(xué)在國(guó)內(nèi)率先成立了校級(jí)復(fù)雜網(wǎng)絡(luò)研究中心并于2005年春季組織了全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議 2005年10月在北京召開的由中國(guó)高等學(xué)術(shù)研究中心組織的第二屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)論壇 一些國(guó)際著名大學(xué)（如MIT，哥倫比亞大

28、學(xué)和密歇根大學(xué)等）已相繼開設(shè)了有關(guān)復(fù)雜網(wǎng)絡(luò)的課程，汪小帆教授也在上海交通大學(xué)為研究生開設(shè)了復(fù)雜網(wǎng)絡(luò)課程。 2006年10月武漢會(huì)議2006全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議 復(fù)雜網(wǎng)絡(luò)中理論及其應(yīng)用-book復(fù)雜網(wǎng)絡(luò)中理論及其應(yīng)用-book復(fù)雜網(wǎng)絡(luò)的主要研究?jī)?nèi)容實(shí)證研究結(jié)合應(yīng)用的研究 簡(jiǎn)單的如：Library And Information Science Abstracts(LISA)圖書館與信息科學(xué)文摘庫(kù)中1996年2005年所有的英文論文數(shù)據(jù)，共109249條教育網(wǎng)數(shù)據(jù)教育網(wǎng)數(shù)據(jù): 對(duì)對(duì)xzmxzm搜集的搜集的eduedu數(shù)據(jù)數(shù)據(jù)網(wǎng)頁(yè)數(shù)量1000，有376個(gè)，鏈接關(guān)系圖教育網(wǎng)數(shù)據(jù)-input50個(gè)（入度

29、大小. 按網(wǎng)絡(luò)影響因子核心站點(diǎn)？ ）教育網(wǎng)數(shù)據(jù)-output34個(gè)（按出度大?。┣閳?bào)學(xué)報(bào)Papers: Complex Networks Papers: Small-World Networks Papers: Scale-Free Networks 面臨的挑戰(zhàn)性課題 20世紀(jì)美國(guó)最有影響的五十人物之一E. O. Wilson指出: 今天最大的挑戰(zhàn)性,不僅是細(xì)胞生物學(xué)和生態(tài)學(xué),而是科學(xué)的所有方面,特別是如何精確地和完全地描述復(fù)雜系統(tǒng).科學(xué)家已經(jīng)認(rèn)識(shí)了許多類型的復(fù)雜系統(tǒng).他們認(rèn)為已經(jīng)知道系統(tǒng)中大多數(shù)元素和受力況.下一步的任務(wù)就是怎么綜合起來,至少在數(shù)學(xué)模型方面必須抓住整個(gè)系綜的關(guān)鍵性質(zhì). 如下為

30、中國(guó)原子能科學(xué)研究院 方錦清列舉: 挑戰(zhàn)性問題之一,從理論上急待深入探索復(fù)雜動(dòng)態(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ò)是否存在普遍動(dòng)力學(xué)性質(zhì),是否存在更多的統(tǒng)計(jì)分布規(guī)律和非統(tǒng)計(jì)規(guī)律, 大規(guī)模復(fù)雜網(wǎng)絡(luò)是否存在富標(biāo)度特性, 它們之間有什么內(nèi)在聯(lián)系 挑戰(zhàn)性問題之四,研究非線性動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中動(dòng)力學(xué)過程的時(shí)空復(fù)雜性

31、及其主要表現(xiàn)形式, 包括: 相同和不同的結(jié)點(diǎn)動(dòng)力學(xué)下,分叉,混沌,陣發(fā)混沌等及其各種廣義同步.同步的產(chǎn)生機(jī)制分析,控制和同步問題. 面臨的挑戰(zhàn)性課題 挑戰(zhàn)性問題之五,探索不同類型網(wǎng)絡(luò)的非線性演化和時(shí)空斑圖的涌現(xiàn)產(chǎn)生的 挑戰(zhàn)性問題之六,如何描述復(fù)雜物理機(jī)制, 為什么社會(huì)網(wǎng)絡(luò)與技術(shù)網(wǎng)絡(luò)和生物網(wǎng)絡(luò)的拓?fù)涮匦圆町惡艽?挑戰(zhàn)性問題之七,動(dòng)態(tài)網(wǎng)絡(luò)基本性質(zhì)的特征量 如何發(fā)展定量與定性分析方法,不僅需要幾何描述,而且需要物理和信息等更多的描述,以便有效地刻畫復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)的主要特性. 挑戰(zhàn)性問題之八,進(jìn)一步研究和發(fā)展廣義隨機(jī)與確定論相結(jié)合理論,交叉理論方法,非平衡統(tǒng)計(jì)理論方法,相變理論方法,玻色-愛因斯坦凝聚理

32、論方法,等等,推進(jìn)整體復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)研究的深入. 挑戰(zhàn)性問題之九,復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)的應(yīng)用研究,如何把復(fù)雜網(wǎng)絡(luò)的研究成果盡快地實(shí)應(yīng)用于我國(guó)實(shí)際工程,國(guó)防領(lǐng)域(例如無線特設(shè)通信網(wǎng)絡(luò)等) 中去,這正是該領(lǐng)域深入研究的迫切要求和進(jìn)一步發(fā)展的推動(dòng)力所在. 挑戰(zhàn)性問題之十,生物復(fù)雜網(wǎng)絡(luò)的研究. softwareSoftwareSoftwarepajek (處理近千萬個(gè)頂點(diǎn))復(fù)雜寓于簡(jiǎn)單 在不同領(lǐng)域許多系統(tǒng)都呈自相似結(jié)構(gòu),即局部與總體相似。例如國(guó)家、河流、行星系等都是這樣。 “分形”是研究自相似結(jié)構(gòu)的。分形的構(gòu)成常遵循一種法則:復(fù)雜的分形外形是由簡(jiǎn)單的規(guī)則重復(fù)迭代生成的。 以Koch曲線為例:將一直線三等分,中間

33、的1 /3用一等邊三角形取代。直線變?yōu)?段等長(zhǎng)折線。每段直線再按此規(guī)則變化,一直重復(fù)下去,即生成Koch曲線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ù)、平均路徑長(zhǎng)度等 網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ图捌湫再|(zhì) 隨機(jī)網(wǎng)絡(luò)、Small World網(wǎng)絡(luò)、Scale Free網(wǎng)絡(luò)等 近幾年的研究態(tài)勢(shì) 發(fā)展歷程、會(huì)議、論文、軟件、實(shí)證等Thank you!911小世界實(shí)驗(yàn)- 六度分離 我們或許有過這樣的經(jīng)歷：偶爾碰到一個(gè)陌生人，同他聊了一會(huì)后發(fā)現(xiàn)你認(rèn)識(shí)的某個(gè)人居然他也認(rèn)識(shí)，然

34、后一起發(fā)出”這個(gè)世界真小”的感嘆。那么對(duì)于世界上任意兩個(gè)人來說，借助第三者、第四者這樣的間接關(guān)系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人呢？ 美國(guó)社會(huì)心理學(xué)家斯坦利米爾格倫(Stanley Milgram)在1967年通過一些實(shí)驗(yàn)后得出結(jié)論：中間的聯(lián)系人平均只需要5個(gè)。他把這個(gè)結(jié)論稱為”六度分離”(six degrees of separation)。 六度分離: 平均只要通過5個(gè)人，你就能與世界任何一個(gè)角落的任何一個(gè)人發(fā)生聯(lián)系。這個(gè)結(jié)論定量地說明了我們世界的”大小”，或者說人與人關(guān)系的緊密程度。 30多年來，六度分離理論一直被作為社會(huì)心理學(xué)的經(jīng)典范例之一。 盡管如此，實(shí)際上這個(gè)理論并沒有得到嚴(yán)格的證實(shí)。美國(guó)心理學(xué)教授朱迪斯克蘭菲爾德(Judith Kleinfeld)對(duì)米爾格倫最初的實(shí)驗(yàn)提出不同意見，因?yàn)樗l(fā)現(xiàn)實(shí)驗(yàn)的完成率極低。小世界實(shí)驗(yàn)- 六度分離 米爾格倫的實(shí)驗(yàn)過程是：他計(jì)劃通過人傳人的送信方式來統(tǒng)計(jì)人與人之間的聯(lián)系。 首先把信交給志愿者A，告訴他信最終要