《復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用》讀書筆記

1、復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用讀書筆記1引言 二十世紀(jì)，科學(xué)研究的特點(diǎn)是分析的方法，復(fù)原論的方法：物理學(xué)牛頓力學(xué)、量子力學(xué)、電子論、半導(dǎo)體，化學(xué)量子分子論，生物雙螺旋結(jié)構(gòu)；建筑工程應(yīng)力應(yīng)變分析，。 二十一世紀(jì)二十世紀(jì)末，系統(tǒng)成為主要的研究對(duì)象，整合成為主要方法。普列高津的耗散結(jié)構(gòu)理論，哈肯的協(xié)同學(xué)，混沌和復(fù)雜系統(tǒng)理論，系統(tǒng)生物學(xué) 。 當(dāng)分析為主要的研究方法時(shí)，人類關(guān)注如何將系統(tǒng)“分析”、“分解”，揭開系統(tǒng)的細(xì)部，了解是什么元素或部件組成了系統(tǒng)，卻無視或破壞了這些元素是如何組合成系統(tǒng)的。而整合的方法在于了解細(xì)部以后，研究“如何組合”的問題。這種方法導(dǎo)致復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的研究。美國Science周刊：“如果對(duì)當(dāng)

2、前流行的、時(shí)髦的關(guān)鍵詞進(jìn)行一番分析，那么人們會(huì)發(fā)現(xiàn)，“系統(tǒng)”高居在排行榜上?！?復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特征如前所述，復(fù)雜網(wǎng)絡(luò)具有很多與規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)不同的統(tǒng)計(jì)特征，其中最重要的是小世界效應(yīng)small -world effect和無標(biāo)度特性scale -free property。在網(wǎng)絡(luò)中，兩點(diǎn)間的距離被定義為連接兩點(diǎn)的最短路所包含的邊的數(shù)目，把所有節(jié)點(diǎn)對(duì)的距離求平均，就得到了網(wǎng)絡(luò)的平均距離average distance 。另外一個(gè)叫做簇系數(shù)clustering coefficient的參數(shù)，專門用來衡量網(wǎng)絡(luò)節(jié)點(diǎn)聚類的情況。比方在朋友關(guān)系網(wǎng)中，你朋友的朋友很可能也是你的朋友；你的兩個(gè)朋友很可能彼此

3、也是朋友。簇系數(shù)就是用來度量網(wǎng)絡(luò)的這種性質(zhì)的。用數(shù)學(xué)化的語言來說，對(duì)于某個(gè)節(jié)點(diǎn)，它的簇系數(shù)被定義為它所有相鄰節(jié)點(diǎn)之間連的數(shù)目占可能的最大連邊數(shù)目的比例，網(wǎng)絡(luò)的簇系數(shù) C則是所有節(jié)點(diǎn)簇系數(shù)的平均值。研究說明，規(guī)則網(wǎng)絡(luò)具有大的簇系數(shù)和大的平均距離，隨機(jī)網(wǎng)絡(luò)具有小的簇系數(shù)和小的平均距離。1998 年，Watts 和Strogatz通過以某個(gè)很小的概率 p 切斷規(guī)則網(wǎng)絡(luò)中原始的邊，并隨機(jī)選擇新的端點(diǎn)重新連接，構(gòu)造出了一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)WS 網(wǎng)絡(luò)，它同時(shí)具有大的簇系數(shù)和小的平均距離，因此既不能當(dāng)作規(guī)則網(wǎng)絡(luò)處理，也不能被看作是隨機(jī)網(wǎng)絡(luò)。隨后，Newman 和Watts 給出了一種新的網(wǎng)絡(luò)

4、的構(gòu)造方法，在他們的網(wǎng)絡(luò)NW 網(wǎng)絡(luò)中，原有的連邊并不會(huì)被破壞，平均距離的縮短源于以一個(gè)很小的概率在原來的規(guī)則網(wǎng)絡(luò)上添加新的連邊。后來物理學(xué)家把大的簇系數(shù)和小的平均距離兩個(gè)統(tǒng)計(jì)特征合在一起稱為小世界效應(yīng)，具有這種效應(yīng)的網(wǎng)絡(luò)就是小世界網(wǎng)絡(luò)small-world networks。圖 1 ：小世界網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖左邊的網(wǎng)絡(luò)是規(guī)則的，右邊的網(wǎng)絡(luò)是隨機(jī)的，中間的網(wǎng)絡(luò)是在規(guī)則網(wǎng)絡(luò)上加上一點(diǎn)隨機(jī)的因素而形成的小世界網(wǎng)絡(luò)，它同時(shí)具有大的簇系數(shù)和小的平均距離。大量的實(shí)證研究說明，真實(shí)網(wǎng)絡(luò)幾乎都具有小世界效應(yīng)，同時(shí)科學(xué)家還發(fā)現(xiàn)大量真實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)度服從冪率分布，這里某節(jié)點(diǎn)的度是指該節(jié)點(diǎn)擁有相鄰節(jié)點(diǎn)的數(shù)目，或者說與

5、該節(jié)點(diǎn)關(guān)聯(lián)的邊的數(shù)目。節(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)，故其平均度可以被看作其節(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)度特性。1999 年，Barabási和Albert 給出了構(gòu)造無標(biāo)度網(wǎng)絡(luò)的演化模型,他們所用的方法與 Price 的方法是類似的。B

6、arabási和 Albert 把真實(shí)系統(tǒng)通過自組織生成無標(biāo)度的網(wǎng)絡(luò)歸功于兩個(gè)主要因素：生長和優(yōu)先連接，而他們的網(wǎng)絡(luò)模型BA 網(wǎng)絡(luò)正是模擬這兩個(gè)關(guān)鍵機(jī)制設(shè)計(jì)的。除了小世界效應(yīng)和無標(biāo)度特性外，真實(shí)網(wǎng)絡(luò)還有很多統(tǒng)計(jì)上的特征，例如混合模式，度相關(guān)特性，超小世界性質(zhì)等等。3復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)3.1復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)的概念系統(tǒng)定義：集合具體元素+ 結(jié)構(gòu)+功能。例：不同角度分析系統(tǒng)，人。系統(tǒng)的結(jié)構(gòu)是： 一切系統(tǒng)的基礎(chǔ)結(jié)構(gòu)都是網(wǎng)絡(luò)； 一切系統(tǒng)的核心結(jié)構(gòu)都是邏輯網(wǎng)絡(luò)； 復(fù)雜系統(tǒng)的結(jié)構(gòu)就是復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)是構(gòu)成復(fù)雜系統(tǒng)的基本結(jié)構(gòu)，每個(gè)復(fù)雜系統(tǒng)都可以看作是單元或個(gè)體之間的相互作用網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)在刻畫復(fù)

7、雜性方面的重要性是由于結(jié)構(gòu)決定功能的。復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一種角度和方法，它關(guān)注系統(tǒng)中因子相互關(guān)聯(lián)作用的拓?fù)浣Y(jié)構(gòu)，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基礎(chǔ)。3.2復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)的主要特性：a開放性。即與環(huán)境和其它系統(tǒng)進(jìn)行相互作用，交換物質(zhì)、能量、信息，保持和發(fā)展系統(tǒng)內(nèi)部的有序性與結(jié)構(gòu)穩(wěn)定性。在這種交換中，系統(tǒng)經(jīng)歷著從低級(jí)向高級(jí)、從簡單到復(fù)雜、從無序向有序的不斷優(yōu)化的動(dòng)態(tài)發(fā)展過程。雖然開放性是所有真實(shí)系統(tǒng)的基本屬性，但這里的開放非指一般意義上的相互作用與交流，而開放的度量、性質(zhì)、強(qiáng)度對(duì)復(fù)雜系統(tǒng)的性態(tài)、演化具有決定性的意義。例子，人，城市網(wǎng)絡(luò)簇。b涌現(xiàn)性。即內(nèi)部元素通過非線性相互作用，在宏觀層次上產(chǎn)

8、生出新的、元素不具有的整體屬性，表現(xiàn)為整體斑圖、模式等。雖然涌現(xiàn)同樣是所有系統(tǒng)都具有的，但這里涌現(xiàn)意味著新的整體屬性的產(chǎn)生。例子， “整體大于部分之和”， 大腦的神經(jīng)網(wǎng)絡(luò)系統(tǒng)。c演化性不可逆性。即通過與所在環(huán)境中的其它系統(tǒng)的相互作用和內(nèi)部的自組織，使系統(tǒng)發(fā)展到新的階段，表現(xiàn)出階段性、臨界性，完成系統(tǒng)演化的生命周期。例:社會(huì)網(wǎng)絡(luò)中的人，生物群體的自組織系統(tǒng)鳥群。d復(fù)雜性。包括系統(tǒng)的結(jié)構(gòu)、行為、功能等多個(gè)方面同時(shí)具有的復(fù)雜性。結(jié)構(gòu)復(fù)雜性表現(xiàn)為多元性，非對(duì)稱性，非均勻性，非線性分岔 (Bifurcation) , 混沌(Chaos), 分形Fractal；行為復(fù)雜性表現(xiàn)為學(xué)習(xí)，自適應(yīng)性，混沌同步，混

9、沌邊沿，隨機(jī)性等等；認(rèn)識(shí)復(fù)雜性又稱為主觀復(fù)雜性，它表現(xiàn)為不確定性，描述復(fù)雜性與計(jì)算復(fù)雜性等等。例:神經(jīng)網(wǎng)絡(luò)中的突觸有強(qiáng)有弱，可抑制也可興奮。e網(wǎng)絡(luò)結(jié)構(gòu)。即系統(tǒng)內(nèi)部和系統(tǒng)之間的相互作用可以看成由節(jié)點(diǎn)、邊連接構(gòu)成的體系，出現(xiàn)網(wǎng)絡(luò)復(fù)雜性、小世界特征與無標(biāo)度特征等。3.3網(wǎng)絡(luò)系統(tǒng)的復(fù)雜性a結(jié)構(gòu)復(fù)雜性網(wǎng)絡(luò)連接結(jié)構(gòu)錯(cuò)綜復(fù)雜、極其混亂，同時(shí)又蘊(yùn)含著豐富的結(jié)構(gòu)：社區(qū)、基序、聚集性、生成規(guī)律性等等，而且網(wǎng)絡(luò)連接結(jié)構(gòu)可能是隨時(shí)間變化的，例如，WWW上每天都不停地有頁面和鏈接的產(chǎn)生和刪除。 靜態(tài)結(jié)構(gòu)的復(fù)雜性和結(jié)構(gòu)動(dòng)態(tài)演化的復(fù)雜性。 例：神經(jīng)系統(tǒng)由神經(jīng)元互連形成，連接以“突觸連接結(jié)構(gòu)”實(shí)現(xiàn)，突觸有強(qiáng)弱、興奮與抑制、不

10、同的神經(jīng)遞質(zhì)；連接不斷改變，形成連接結(jié)構(gòu)變化。重邊，加權(quán)等。b節(jié)點(diǎn)復(fù)雜性1】節(jié)點(diǎn)的獨(dú)立或固有特性網(wǎng)絡(luò)中的節(jié)點(diǎn)可能是具有分岔和混沌等復(fù)雜非線 性行為的動(dòng)力系統(tǒng)。例如，基因網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都具有復(fù)雜的時(shí)間演化行為。而且，一個(gè)網(wǎng)絡(luò)中可能存在多種不同類型的節(jié)點(diǎn)。例如，控制哺乳動(dòng)物中細(xì)胞分裂的生化網(wǎng)絡(luò)就包含各種各樣的基質(zhì)和酶。2】關(guān)聯(lián)引發(fā)的節(jié)點(diǎn)特性當(dāng)關(guān)聯(lián)失去時(shí)這類特性會(huì)在節(jié)點(diǎn)處消失或改變。例如，耦合神經(jīng)元重復(fù)地被同時(shí)激活，那么它們之間的連接就會(huì)加強(qiáng)，這被認(rèn)為是記憶和學(xué)習(xí)的基礎(chǔ)。3】復(fù)雜網(wǎng)絡(luò)之間相互影響的復(fù)雜性實(shí)際的復(fù)雜網(wǎng)絡(luò)會(huì)受到各種各樣因素的影響和作用。例如，電力網(wǎng)絡(luò)故障會(huì)導(dǎo)致Internet網(wǎng)速變慢，運(yùn)

11、輸系統(tǒng)失控等一系列不同網(wǎng)絡(luò)間的連鎖反應(yīng)。4】網(wǎng)絡(luò)分層結(jié)構(gòu)的復(fù)雜性例如，行政管理網(wǎng)絡(luò)是具有層結(jié)構(gòu)的，多數(shù)網(wǎng)絡(luò)都有節(jié)點(diǎn)的分層結(jié)構(gòu)，只是在許多網(wǎng)絡(luò)中沒有意識(shí)到是一種造成復(fù)雜性的重要結(jié)構(gòu)。復(fù)雜網(wǎng)絡(luò)是二十一世紀(jì)科學(xué)研究的思想和理念，它啟發(fā)我們用什么觀點(diǎn)理解這個(gè)世界：整個(gè)世界以及組成世界的任何細(xì)部都是由網(wǎng)絡(luò)及其變化形成的。復(fù)雜網(wǎng)絡(luò)也是研究復(fù)雜系統(tǒng)的一種技術(shù)和方法，它關(guān)注系統(tǒng)中個(gè)體相互作用的拓?fù)浣Y(jié)構(gòu)，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基本方法。4復(fù)雜網(wǎng)絡(luò)上的物理過程對(duì)于物理學(xué)家而言，研究復(fù)雜網(wǎng)絡(luò)的終極目標(biāo)是理解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)物理過程的影響。在以前的研究中，物理學(xué)家往往忽略了網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，在討論逾滲、傳播、同步等物

12、理過程時(shí)，他們自然地選擇了最容易模擬和分析的規(guī)則網(wǎng)絡(luò)或者隨機(jī)網(wǎng)絡(luò)，而沒有仔細(xì)思考和研究這種選擇是不是應(yīng)該的，不同的選擇會(huì)不會(huì)對(duì)物理過程產(chǎn)生不可忽略的影響。以網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)模型為例，由于傳統(tǒng)的網(wǎng)絡(luò)傳播模型大都是基于規(guī)則網(wǎng)絡(luò)的，因此，復(fù)雜網(wǎng)絡(luò)不同統(tǒng)計(jì)特征的發(fā)現(xiàn)使科學(xué)家面臨更改既有結(jié)論的危險(xiǎn)。當(dāng)然，如果理論研究和實(shí)驗(yàn)結(jié)果都說明復(fù)雜網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)行為與規(guī)則網(wǎng)絡(luò)別無二致，那么我們至少暫時(shí)還可以心安理得地使用以前的結(jié)論。但是，不幸的是，復(fù)雜網(wǎng)絡(luò)上的傳播行為與規(guī)則網(wǎng)絡(luò)相比確實(shí)存在根本上的不同。類似的情況還出現(xiàn)在其他的物理過程中，下面我們將簡略地介紹網(wǎng)絡(luò)拓?fù)湫再|(zhì)對(duì)某些典型物理過程的影響。逾滲模型與疾病

13、傳播動(dòng)力學(xué)。之所以在這里把逾滲模型和網(wǎng)絡(luò)上的疾病傳播動(dòng)力學(xué)問題歸在一起討論，是因?yàn)榫W(wǎng)絡(luò)上的疾病傳播模型可以等價(jià)于鍵逾滲模型。以前的基于規(guī)則網(wǎng)絡(luò)的研究說明，疾病在網(wǎng)絡(luò)中的平均涉及范圍與疾病的傳染強(qiáng)度正相關(guān)，而疾病的傳染強(qiáng)度有一個(gè)閾值，只有當(dāng)其值大于這個(gè)閾值時(shí)，疾病才能在網(wǎng)絡(luò)中長期存在，否則感染人數(shù)會(huì)指數(shù)衰減。根據(jù)這個(gè)理論，疾病假設(shè)是持久存在，則必然涉及大量個(gè)體。但實(shí)證研究說明，電腦病毒，麻疹等一般僅涉及少數(shù)個(gè)體但能夠長期存在。這一理論與實(shí)證的矛盾在很長時(shí)間里一直困擾著科學(xué)界。近年來的研究說明在無標(biāo)度網(wǎng)絡(luò)中沒有正的傳播閾值，也就是說即使疾病的傳染強(qiáng)度接近零，只涉及非常少的個(gè)體，也能在網(wǎng)絡(luò)中長期存在

14、。由于大部分真實(shí)網(wǎng)絡(luò)是無標(biāo)度網(wǎng)絡(luò)，因此該結(jié)論很好地解決了上面的矛盾?；煦缤?。近十余年來，混沌動(dòng)力系統(tǒng)在網(wǎng)絡(luò)上的同步性能吸引了大量科學(xué)家的關(guān)注。早期的研究主要是針對(duì)以最近鄰環(huán)網(wǎng)為代表的規(guī)則網(wǎng)絡(luò)，研究說明對(duì)于給定的非零耦合強(qiáng)度，當(dāng)節(jié)點(diǎn)數(shù)目很大時(shí)網(wǎng)絡(luò)無法實(shí)現(xiàn)同步。最近幾年的研究卻說明，盡管小世界網(wǎng)絡(luò)只是在規(guī)則網(wǎng)絡(luò)進(jìn)行一個(gè)非常小的修正的結(jié)果，但其實(shí)現(xiàn)混沌同步的能力卻遠(yuǎn)遠(yuǎn)好于規(guī)則網(wǎng)絡(luò)。對(duì)于小世界上的廣義混沌同步與超混沌同步的研究同樣說明，小世界網(wǎng)絡(luò)有明顯好于規(guī)則網(wǎng)絡(luò)的同步能力。物理學(xué)家還考察了無標(biāo)度網(wǎng)絡(luò)，研究說明其混沌同步的能力與星形網(wǎng)絡(luò)幾乎是一樣的，這可能是因?yàn)樗c星形網(wǎng)絡(luò)都具有很不均勻的節(jié)點(diǎn)度分布

15、。沙堆模型與自組織臨界性。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是否會(huì)影響沙堆模型中的自組織臨界現(xiàn)象，一直以來就是該領(lǐng)域爭論的焦點(diǎn)。 Zhou和 Wang 對(duì)復(fù)雜網(wǎng)絡(luò)上沙堆模型的研究說明，沙堆模型中的雪崩動(dòng)力學(xué)性質(zhì)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)非常敏感，相比規(guī)則網(wǎng)絡(luò)，無標(biāo)度網(wǎng)絡(luò)上大雪崩發(fā)生更為頻繁，最大雪崩的規(guī)模也大得多。物理性質(zhì)明顯依賴于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的物理過程還很多，例如隨機(jī)游走，玻色愛因斯坦凝聚49-51 ，XY 臨界模型等等?？偟膩碚f，物理學(xué)家已經(jīng)開始學(xué)會(huì)把網(wǎng)絡(luò)拓?fù)湫再|(zhì)看作影響系統(tǒng)行為的一個(gè)特征量，這也很大程度上改變了我們對(duì)很多物理過程原有的認(rèn)識(shí)。5復(fù)雜網(wǎng)絡(luò)研究簡史a格尼斯堡七橋問題。b隨機(jī)圖理論。20世紀(jì)60年代，由兩位匈牙利

16、數(shù)學(xué)家Erds和Rényi建立的隨機(jī)圖理論random graph theory被公認(rèn)為是在數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。Erds和Rényi的最重要的發(fā)現(xiàn)是：ER隨機(jī)圖的許多重要性質(zhì)都是突然涌現(xiàn)的。也就是說，對(duì)于任一給定的概率p，要么幾乎每一個(gè)圖都具有某個(gè)性質(zhì)Q比方說，連通性，要么幾乎每一個(gè)圖都不具有該性質(zhì)。在20世紀(jì)的后40年中，隨機(jī)圖理論一直是研究復(fù)雜網(wǎng)絡(luò)的基本理論。c小世界實(shí)驗(yàn)。20世紀(jì)60年代美國哈佛大學(xué)的社會(huì)心理學(xué)家Stanley Milgram通過一些社會(huì)調(diào)查后給出的推斷是：地球上任意兩個(gè)人之間的平均距離是6。這就是著名的“六度別離”six degre

17、es of separation推斷。為了檢驗(yàn)“六度別離”的正確性，小世界實(shí)驗(yàn)Bacon數(shù)。美國Virginia大學(xué)電腦系的科學(xué)家建立了一個(gè)電影演員的數(shù)據(jù)庫，放在網(wǎng)上供人們隨意查詢。網(wǎng)站的數(shù)據(jù)庫里目前總共存有近60萬個(gè)世界各地的演員的信息以及近30萬部電影信息。通過簡單地輸入演員名字就可以知道這個(gè)演員的Bacon數(shù)。有兩篇開創(chuàng)性的文章可以看作是復(fù)雜網(wǎng)絡(luò)研究新紀(jì)元開始的標(biāo)志：一篇是美國康奈爾Cornell大學(xué)理論和應(yīng)用力學(xué)系的博士生Watts及其導(dǎo)師、非線性動(dòng)力學(xué)專家Strogatz教授于1998年6月在Nature雜志上發(fā)表的題為“小世界”網(wǎng)絡(luò)的集體動(dòng)力學(xué)Collective Dynamics

18、 of Small-World Networks的文章；另一篇是美國Notre Dame大學(xué)物理系的Barabsi教授及其博士生Albert于1999年10月在Science雜志上發(fā)表的題為隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)Emergence of Scaling in Random Networks的文章。這兩篇文章分別揭示了復(fù)雜網(wǎng)絡(luò)的小世界特征和無標(biāo)度性質(zhì)，并建立了相應(yīng)的模型以闡述這些特性的產(chǎn)生機(jī)理。不同領(lǐng)域的復(fù)雜網(wǎng)絡(luò)：社會(huì)網(wǎng)：演員合作網(wǎng)，友誼網(wǎng)，姻親關(guān)系網(wǎng)，科研合作網(wǎng)，Email網(wǎng)；生物網(wǎng)：食物鏈網(wǎng)，神經(jīng)網(wǎng)，新陳代謝網(wǎng)，蛋白質(zhì)網(wǎng)，基因網(wǎng)絡(luò)；信息網(wǎng)絡(luò)：WWW，專利使用，論文引用，電腦共享；技術(shù)網(wǎng)絡(luò)：電力

19、網(wǎng)，Internet， 線路網(wǎng)；交通運(yùn)輸網(wǎng)：航線網(wǎng)，鐵路網(wǎng)，公路網(wǎng)，自然河流網(wǎng)。6復(fù)雜網(wǎng)絡(luò)研究內(nèi)容6.11復(fù)雜網(wǎng)絡(luò)模型 典型的復(fù)雜網(wǎng)絡(luò)：隨機(jī)網(wǎng)、小世界網(wǎng)、無標(biāo)度網(wǎng)等；實(shí)際網(wǎng)絡(luò)及其分類。2網(wǎng)絡(luò)的統(tǒng)計(jì)量及與網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)性 度分布的定義和意義，聚集性、連通性的統(tǒng)計(jì)量及其實(shí)際 意義等。3復(fù)雜網(wǎng)絡(luò)性質(zhì)與結(jié)構(gòu)的關(guān)系 同步性、魯棒性和穩(wěn)定性與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系。4復(fù)雜網(wǎng)絡(luò)的動(dòng)力學(xué) 信息傳播動(dòng)力學(xué)、網(wǎng)絡(luò)演化動(dòng)力學(xué)、網(wǎng)絡(luò)混沌動(dòng)力學(xué)。5復(fù)雜網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu) 社團(tuán)結(jié)構(gòu)、層次結(jié)構(gòu)、節(jié)點(diǎn)分類結(jié)構(gòu)等。6網(wǎng)絡(luò)控制 關(guān)鍵節(jié)點(diǎn)控制、主參數(shù)控制和控制的穩(wěn)定性和有效性。7復(fù)雜網(wǎng)絡(luò)建模 機(jī)理建模、數(shù)據(jù)建模和實(shí)際系統(tǒng)的復(fù)雜網(wǎng)絡(luò)正向與逆向建

20、模。8復(fù)雜邏輯網(wǎng)絡(luò)邏輯與高階邏輯定義、分類、判定算法，高階邏輯的實(shí)際意義等等。F1: AB; F2:(A, B) C; F3:(A, B, C) D A, B, C, D取布爾值。6.2復(fù)雜網(wǎng)絡(luò)研究a突破性進(jìn)展的主要原因 越來越強(qiáng)大的計(jì)算設(shè)備和迅猛發(fā)展的Internet，使得人們開始能夠收集和處理規(guī)模巨大且種類不同的實(shí)際網(wǎng)絡(luò)數(shù)據(jù)。 學(xué)科之間的相互交叉使得研究人員可以廣泛比較各種不同類型的網(wǎng)絡(luò)數(shù)據(jù)，從而揭示復(fù)雜網(wǎng)絡(luò)的共性。 以復(fù)原理論和整體論相結(jié)合為重要特色的復(fù)雜性科學(xué)的興起，也促使人們開始從整體上研究網(wǎng)絡(luò)的結(jié)構(gòu)與性能之間的關(guān)系。b研究的主要目標(biāo)發(fā)現(xiàn)：揭示刻畫網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)的統(tǒng)計(jì)性質(zhì)，以及度量這些

21、性質(zhì)的合適方法。建模：建立合適的網(wǎng)絡(luò)模型以及理解網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)的意義與產(chǎn)生機(jī)理。分析：基于單個(gè)節(jié)點(diǎn)的特性和整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)分析與預(yù)測(cè)網(wǎng)絡(luò)的行為?？刂疲禾岢龈纳埔延芯W(wǎng)絡(luò)性能和設(shè)計(jì)新的網(wǎng)絡(luò)的有效方法，特別是穩(wěn)定性、同步和數(shù)據(jù)流通等方面。c復(fù)雜網(wǎng)絡(luò)的基本概念度(degree)：節(jié)點(diǎn) i 的度 ki 定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目。直觀上看，一個(gè)節(jié)點(diǎn)的度越大就意味著這個(gè)節(jié)點(diǎn)在某種意義上越“重要”“能力大”。 網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度和的平均值，記作<k>。事實(shí)上，<k>=2q/p 。度分布函數(shù)p(k):隨機(jī)選定節(jié)點(diǎn)的度恰好為k的概率。節(jié)點(diǎn)的聚類系數(shù)簇系數(shù)：在簡單圖

22、中，設(shè)節(jié)點(diǎn)v的鄰集為N(v), |N(v)|=ki，則節(jié)點(diǎn)v的聚類系數(shù)定義為這ki個(gè)節(jié)點(diǎn)之間存在邊數(shù)Ei與總的可能邊數(shù)ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1) ，節(jié)點(diǎn)v的鄰點(diǎn)間關(guān)系的密切程度。網(wǎng)絡(luò)的聚類系數(shù)C：所有節(jié)點(diǎn)i的聚類系數(shù)Ci的平均值。0£C£1C=0Û網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是孤立點(diǎn)；C=1Û網(wǎng)絡(luò)中任意節(jié)點(diǎn)間都有邊相連，網(wǎng)絡(luò)節(jié)點(diǎn)間聯(lián)系的密切程度, 表達(dá)網(wǎng)絡(luò)的凝聚力。 許多大規(guī)模的實(shí)際網(wǎng)絡(luò)都具有明顯的聚類效應(yīng)。事實(shí)上，在很多類型的網(wǎng)絡(luò)(如社會(huì)關(guān)系網(wǎng)絡(luò))中，你的朋友同時(shí)也是朋友的概率會(huì)隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于某個(gè)非零常數(shù)，即當(dāng)N時(shí)，C

23、=O(1)。這意味著這些實(shí)際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的，而是在某種程度上具有類似于社會(huì)關(guān)系網(wǎng)絡(luò)中“物以類聚，人以群分”的特性。最短路徑Shortest path:兩個(gè)節(jié)點(diǎn)之間邊數(shù)最少的路徑，最短路徑的長度稱為兩點(diǎn)。所有節(jié)點(diǎn)對(duì)之間的距離的平均值。研究發(fā)現(xiàn)：盡管許多實(shí)際復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)巨大，網(wǎng)絡(luò)的平均路徑長度卻小的驚人。小世界效應(yīng)點(diǎn)介數(shù)：網(wǎng)絡(luò)中通過該節(jié)點(diǎn)的最短路徑的條數(shù)。邊介數(shù)：網(wǎng)絡(luò)中通過該邊的最短路徑的條數(shù)。反映了節(jié)點(diǎn)或邊的作用和影響力。如果一對(duì)節(jié)點(diǎn)間共有B條不同的最短路徑，其中有b條經(jīng)過節(jié)點(diǎn)i，那么節(jié)點(diǎn)i對(duì)這對(duì)節(jié)點(diǎn)的介數(shù)的奉獻(xiàn)為b/B。把節(jié)點(diǎn)i對(duì)所有節(jié)點(diǎn)對(duì)的奉獻(xiàn)累加起來再除以節(jié)點(diǎn)對(duì)總數(shù)，就可得

24、到節(jié)點(diǎn)i的介數(shù)。類似的，邊的介數(shù)定義為所有節(jié)點(diǎn)對(duì)的最短路徑中經(jīng)過該邊的數(shù)量比例關(guān)鍵點(diǎn)邊！連通性影響？。介數(shù)越大，說明經(jīng)過該節(jié)點(diǎn)邊的最短路徑越多。在信息傳播過程中，通過該節(jié)點(diǎn)邊的信息量就越大，于是就越容易發(fā)生擁塞。研究說明，節(jié)點(diǎn)介數(shù)與度之間有很強(qiáng)的相關(guān)性，不同類型的網(wǎng)絡(luò)，其介數(shù)分布也大不一樣。網(wǎng)絡(luò)點(diǎn)介數(shù)，網(wǎng)絡(luò)邊介數(shù)： 所有節(jié)點(diǎn)邊的平均介數(shù)。核數(shù)一個(gè)圖的k-核：反復(fù)去掉圖中度小于等于k 的節(jié)點(diǎn)后，所剩余的子圖假設(shè)一個(gè)節(jié)點(diǎn)存在于k-核，而在(k+1)-核中被去掉，則此節(jié)點(diǎn)核數(shù)為k，例：所有度為1的節(jié)點(diǎn)的核數(shù)必為0，節(jié)點(diǎn)核數(shù)中的最大值稱為網(wǎng)絡(luò)圖的核數(shù)，節(jié)點(diǎn)核數(shù)可以說明節(jié)點(diǎn)在核中的深度；即便一個(gè)節(jié)點(diǎn)的度

25、數(shù)很高，它的核數(shù)也可能很小。例如：包含N個(gè)節(jié)點(diǎn)的星型網(wǎng)絡(luò)的中心節(jié)點(diǎn)的度數(shù)為N-1，但它的核數(shù)為0。7小世界實(shí)驗(yàn)a六度別離米爾格倫的實(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í)

26、驗(yàn)的完成率很低。 我們或許有過這樣的經(jīng)歷：偶爾碰到一個(gè)陌生人，同他聊了一會(huì)后發(fā)現(xiàn)你認(rèn)識(shí)的某個(gè)人居然他也認(rèn)識(shí)，然后一起發(fā)出”這個(gè)世界真小”的感慨。那么對(duì)于世界上任意兩個(gè)人來說，借助第三者、第四者這樣的間接關(guān)系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人呢？美國社會(huì)心理學(xué)家斯坦利米爾格倫(Stanley Milgram)在1967年通過一些實(shí)驗(yàn)后得出結(jié)論：中間的聯(lián)系人平均只需要5個(gè)。他把這個(gè)結(jié)論稱為“六度別離”。六度別離: 平均只要通過5個(gè)人，你就能與世界任何一個(gè)角落的任何一個(gè)人發(fā)生聯(lián)系。這個(gè)結(jié)論定量地說明了我們世界的”大小”，或者說人與人關(guān)系的緊密程度。30多年來，六度別離理論一直被作為社會(huì)心

27、理學(xué)的經(jīng)典范例之一。盡管如此，實(shí)際上這個(gè)理論并沒有得到嚴(yán)格的證實(shí)。美國心理學(xué)教授朱迪斯克蘭菲爾德(Judith Kleinfeld)對(duì)米爾格倫最初的實(shí)驗(yàn)提出不同意見，因?yàn)樗l(fā)現(xiàn)實(shí)驗(yàn)的完成率極低。b Bacon數(shù) 截止到幾天前，世界電影史上共產(chǎn)生了大約23萬部電影，78多萬名電影演員，Kavin Bacon在許多部電影中飾演小角色。幾年前,Virginia 大學(xué)的電腦專家Brett Tjaden設(shè)計(jì)了一個(gè)游戲，他聲稱電影演員Kevin Bacon是電影界的中心。在游戲里定義了一個(gè)所謂的Bacon數(shù)：隨便想一個(gè)演員，如果他她和Kavin Bacon一起演過電影，那么他她的Bacon數(shù)就為1；如果他

28、她沒有和Bacon演過電影，但是和Bacon數(shù)為1的演員一起演過電影，那么他的Bacon數(shù)就為2；依此類推。發(fā)現(xiàn)：在曾經(jīng)參演的美國電影演員中，沒有一個(gè)人的Bacon數(shù)超過4。在網(wǎng)上有一個(gè)網(wǎng)頁 :/ /oracle/。網(wǎng)站的數(shù)據(jù)庫里總共存有有783940個(gè)世界各地的演員的信息以及231,088部電影信息。通過簡單地輸入演員名字就可以知道這個(gè)演員的bacon數(shù)。目前比方輸入Stephen Chow周星馳就可以得到這樣的結(jié)果：周星馳在1991年的豪門夜宴(Haomen yeyan) 中與洪金寶(Sammo Hung Kam-Bo)合作；而洪金寶又在李小龍的最后一部電影，

29、即1978年的死亡的游戲 Game of Death 中與 Colleen Camp 合作；Colleen Camp 在去年的電影Trapped 中與Kevin Bacon 合作。這樣周星馳的Bacon數(shù)為3。對(duì)78萬個(gè)演員所做的統(tǒng)計(jì)：演員的最大Bacon數(shù)僅僅為8，平均Bacon數(shù)僅為2.948。 c Erdos數(shù) Paul Erdos(1913-1996)：是出生于匈牙利的猶太籍?dāng)?shù)學(xué)家，被公認(rèn)為20世紀(jì)最偉大的天才之一。Erdos畢生發(fā)表的論文超過1500篇在數(shù)學(xué)史上僅次于歐拉(Euler ，1707-1783)，超長的合作者名單,合作者超過450位。但假設(shè)加上別人所做但曾獲他關(guān)

30、鍵性提示之論文，則他的論文應(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ù)?、統(tǒng)計(jì)、數(shù)值分析、電腦科學(xué)、信息論等等。"Mathematical Reviews" 曾把數(shù)學(xué)劃分為大約六十個(gè)分支，Erdos的論文涉及到了其中的40%. Erdos從來沒有一個(gè)固定的職位，從來不定居在一個(gè)地方，也沒有結(jié)婚，帶著一半空的手提箱，穿梭于學(xué)術(shù)研討會(huì)，浪跡天涯，頗富傳奇色彩。有人稱他為流

31、浪學(xué)者(wande ring scholar)。他效忠的是科學(xué)的皇后， 而非一特定的地方。各地都有熱心的數(shù)學(xué)家提供他舒適的食宿，安排他的一切，他則對(duì)招待他的主人，給出一些挑戰(zhàn)性的數(shù)學(xué)難題，或給予研究上的指導(dǎo)做為回饋。他可以和許多不同領(lǐng)域的數(shù)學(xué)家合作。數(shù)學(xué)家常將本身長久解決不了的問題和他討論，于是很快地一篇論文便誕生了。 數(shù)學(xué)家以下述方式來定義Erdos數(shù)(Erdos number) : Erdos本人之Erdos數(shù)為0，任何人假設(shè)曾與Erdos合寫過論文，則其Erdos數(shù)為1。任何人假設(shè)曾與一位Erdos數(shù)為l(且不曾與有更少的Erdos數(shù))&

32、#160;的人合寫過論文， 則他的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-Andrew Odlyzko-Chris M.Skinner-Andrew Wiles。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)得主

33、的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)，他的Erdos數(shù)是4，通過如下途徑實(shí)現(xiàn)：Erdos-Pavol Hell-Xiao Tie Deng-Christos H. Papadimitriou-William H.(Bill) Gates.。愛因斯坦的Erdos數(shù)是2。8復(fù)雜網(wǎng)絡(luò)理論的應(yīng)用研究目前國內(nèi)關(guān)于復(fù)雜網(wǎng)絡(luò)的應(yīng)用研究主要涉及信息網(wǎng)絡(luò)、社會(huì)、經(jīng)濟(jì)管理等領(lǐng)域。在論述已有工作的基礎(chǔ)上，構(gòu)建了一個(gè)Internet 的復(fù)雜網(wǎng)絡(luò)模型，對(duì)病毒的傳播行為進(jìn)行了仿真研究，結(jié)果說明，構(gòu)建的網(wǎng)絡(luò)模型真實(shí)地反映了Internet 的特性，通過對(duì)某些參數(shù)的調(diào)整，病毒傳播可以得到有效控制。通信網(wǎng)絡(luò)可以看成是由成千上萬個(gè)路由器節(jié)點(diǎn)以及節(jié)點(diǎn)之間的數(shù)百萬條通信線路組成的邊所構(gòu)成的復(fù)雜網(wǎng)絡(luò)。實(shí)際通信網(wǎng)絡(luò)經(jīng)常承受超負(fù)荷的流量，導(dǎo)致?lián)砣漠a(chǎn)生。陳振毅等利用BA 無標(biāo)度網(wǎng)絡(luò)模型來模擬通信網(wǎng)絡(luò)中的數(shù)