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

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

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

3、是你的朋友；你的兩個朋友很可能彼此也是朋 友。簇系數(shù)就是用來度量網(wǎng)絡(luò)的這種性質(zhì)的。用數(shù)學(xué)化的語言來說, 對于某個節(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 通過以某個很小的概率 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ù)和小的平均距離，因此既不能當(dāng)作規(guī)則網(wǎng)絡(luò)處理，也不能被看作是隨機(jī)網(wǎng)絡(luò)。隨后，Newma

4、 n和Watts給出了一種新的網(wǎng)絡(luò)的構(gòu)造方法，在他們的網(wǎng)絡(luò)（NW網(wǎng)絡(luò)）中，原有的連邊并不會被破壞，平均距離的縮短源于以一個很小的概 率在原來的規(guī)則網(wǎng)絡(luò)上添加新的連邊。后來物理學(xué)家把大的簇系數(shù)和 小的平均距離兩個統(tǒng)計特征合在一起稱為小世界效應(yīng)，具有這種效應(yīng) 的網(wǎng)絡(luò)就是小世界網(wǎng)絡(luò)（small-world networks ）。30%理他能恣薊圖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í)網(wǎng)絡(luò)幾乎都具有小世界效應(yīng)，同時科學(xué)家還發(fā)現(xiàn)大量真實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)度

5、服從幕率分布，這里某節(jié)點(diǎn)的度是 指該節(jié)點(diǎn)擁有相鄰節(jié)點(diǎn)的數(shù)目，或者說與該節(jié)點(diǎn)關(guān)聯(lián)的邊的數(shù)目。節(jié) 點(diǎn)度服從幕律分布就是說具有某個特定度的節(jié)點(diǎn)數(shù)目與這個特定的 度之間的關(guān)系可以用一個幕函數(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)度的一個特征標(biāo)度。 在這個意義上，我們把節(jié)點(diǎn)度服從幕律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)（scale -free networks），并稱這種節(jié)點(diǎn)度的幕律分布為網(wǎng)絡(luò)的無標(biāo)度特性。1999年，Barab®和Albert給出了構(gòu)

6、造無標(biāo)度網(wǎng)絡(luò)的演化模型，他們所用的方法與Price的方法是類似的。BarabdBi和Albert把真實(shí)系 統(tǒng)通過自組織生成無標(biāo)度的網(wǎng)絡(luò)歸功于兩個主要因素： 生長和優(yōu)先連 接，而他們的網(wǎng)絡(luò)模型（BA網(wǎng)絡(luò)）正是模擬這兩個關(guān)鍵機(jī)制設(shè)計的。除了小世界效應(yīng)和無標(biāo)度特性外，真實(shí)網(wǎng)絡(luò)還有很多統(tǒng)計上的特 征，例如混合模式，度相關(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)，每個復(fù)雜系統(tǒng)

7、都可以看作 是單元或個體之間的相互作用網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)在刻畫復(fù)雜性方面的重 要性是由于結(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)歷著從低級向高級、從簡單到復(fù)雜、從無序向有序的不斷優(yōu)化 的動態(tài)發(fā)展過程。雖然開放性是所有真實(shí)系統(tǒng)的基本屬性，但這里的 開放非指一般意義上的相互作用與交流，而開放的度量、性質(zhì)、強(qiáng)度 對復(fù)雜系統(tǒng)的性態(tài)、演化具有決定性的意

8、義。例子，人，城市網(wǎng)絡(luò)簇。b涌現(xiàn)性。即內(nèi)部元素通過非線性相互作用，在宏觀層次上產(chǎn)生出新的、元素不具有的整體屬性，表現(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)演化的生命周期。例：社會網(wǎng)絡(luò)中的人，生物群體的自 組織系統(tǒng)（鳥群）。d復(fù)雜性。包括系統(tǒng)的結(jié)構(gòu)、行為、功能等多個方面同時具有的復(fù)雜性。結(jié)構(gòu)復(fù)雜性表現(xiàn)為多元性，非對稱性，非均勻性，非線性（分岔(Bifurcation),混

9、沌(Chaos),分形Fractal);行為復(fù)雜性表現(xiàn)為學(xué) 習(xí)，自適應(yīng)性，混沌同步，混沌邊沿，隨機(jī)性等等；認(rèn)識復(fù)雜性又稱 為主觀復(fù)雜性，它表現(xiàn)為不確定性，描述復(fù)雜性與計算復(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)錯綜復(fù)雜、極其混亂，同時又蘊(yùn)含著豐富的結(jié)構(gòu): 社區(qū)、基序、聚集性、生成規(guī)律性等等，而且網(wǎng)絡(luò)連接結(jié)構(gòu)可能是隨 時間變化的，例如，WWW上每天都不停地有頁面和鏈接的產(chǎn)生和刪除。靜態(tài)結(jié)構(gòu)的復(fù)雜性和結(jié)構(gòu)動態(tài)演化

10、的復(fù)雜性。例：神經(jīng)系統(tǒng)由 神經(jīng)元互連形成，連接以 突觸連接結(jié)構(gòu)”實(shí)現(xiàn)，突觸有強(qiáng)弱、興奮與抑制、不同的神經(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ù)雜非線性行為的動力 系統(tǒng)。例如，基因網(wǎng)絡(luò)中每個節(jié)點(diǎn)都具有復(fù)雜的時間演化行為。 而且, 一個網(wǎng)絡(luò)中可能存在多種不同類型的節(jié)點(diǎn)。 例如，控制哺乳動物中細(xì) 胞分裂的生化網(wǎng)絡(luò)就包含各種各樣的基質(zhì)和酶。2】關(guān)聯(lián)引發(fā)的節(jié)點(diǎn)特性當(dāng)關(guān)聯(lián)失去時這類特性會在節(jié)點(diǎn)處消失或改變。 例如，耦合神經(jīng) 元重復(fù)地被同時激活，那么它們之間的連接就會加強(qiáng)，這被認(rèn)為是記 憶和學(xué)習(xí)的基礎(chǔ)。3】復(fù)雜網(wǎng)絡(luò)之

11、間相互影響的復(fù)雜性實(shí)際的復(fù)雜網(wǎng)絡(luò)會受到各種各樣因素的影響和作用。 例如，電力 網(wǎng)絡(luò)故障會導(dǎo)致In ternet網(wǎng)速變慢，運(yùn)輸系統(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ò)中沒有意識到是一種造成復(fù)雜性的重要結(jié)構(gòu)。復(fù)雜網(wǎng)絡(luò)是二十一世紀(jì)科學(xué)研究的思想和理念， 它啟發(fā)我們用什 么觀點(diǎn)理解這個世界：整個世界以及組成世界的任何細(xì)部都是由網(wǎng)絡(luò) 及其變化形成的。復(fù)雜網(wǎng)絡(luò)也是研究復(fù)雜系統(tǒng)的一種技術(shù)和方法， 它 關(guān)注系統(tǒng)中個體相互作用的拓?fù)浣Y(jié)構(gòu)，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的 基本方法。4復(fù)雜網(wǎng)絡(luò)上的物理過程對于物理學(xué)家而言

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

13、上的傳播行為與規(guī)則網(wǎng)絡(luò)相比確實(shí)存在根本上的不同。類似的情況還 出現(xiàn)在其他的物理過程中，下面我們將簡略地介紹網(wǎng)絡(luò)拓?fù)湫再|(zhì)對某 些典型物理過程的影響。逾滲模型與疾病傳播動力學(xué)。之所以在這里把逾滲模型和網(wǎng)絡(luò)上 的疾病傳播動力學(xué)問題歸在一起討論，是因?yàn)榫W(wǎng)絡(luò)上的疾病傳播模型 可以等價于鍵逾滲模型。以前的基于規(guī)則網(wǎng)絡(luò)的研究表明，疾病在網(wǎng) 絡(luò)中的平均波及范圍與疾病的傳染強(qiáng)度正相關(guān)， 而疾病的傳染強(qiáng)度有 一個閾值，只有當(dāng)其值大于這個閾值時，疾病才能在網(wǎng)絡(luò)中長期存在, 否則感染人數(shù)會指數(shù)衰減。根據(jù)這個理論，疾病若是持久存在，則必 然波及大量個體。但實(shí)證研究表明，計算機(jī)病毒，麻疹等一般僅波及 少數(shù)個體但能夠長期存

14、在。這一理論與實(shí)證的矛盾在很長時間里一直 困擾著科學(xué)界。近年來的研究表明在無標(biāo)度網(wǎng)絡(luò)中沒有正的傳播閾 值，也就是說即使疾病的傳染強(qiáng)度接近零，只波及非常少的個體，也 能在網(wǎng)絡(luò)中長期存在。由于大部分真實(shí)網(wǎng)絡(luò)是無標(biāo)度網(wǎng)絡(luò)，因此該結(jié) 論很好地解決了上面的矛盾?；煦缤?。近十余年來，混沌動力系統(tǒng) 在網(wǎng)絡(luò)上的同步性能吸引了大量科學(xué)家的關(guān)注。 早期的研究主要是針 對以最近鄰環(huán)網(wǎng)為代表的規(guī)則網(wǎng)絡(luò)，研究表明對于給定的非零耦合強(qiáng)度，當(dāng)節(jié)點(diǎn)數(shù)目很大時網(wǎng)絡(luò)無法實(shí)現(xiàn)同步。最近幾年的研究卻表明,盡管小世界網(wǎng)絡(luò)只是在規(guī)則網(wǎng)絡(luò)進(jìn)行一個非常小的修正的結(jié)果，但其 實(shí)現(xiàn)混沌同步的能力卻遠(yuǎn)遠(yuǎn)好于規(guī)則網(wǎng)絡(luò)。 對于小世界上的廣義混沌 同

15、步與超混沌同步的研究同樣表明，小世界網(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)度分布。沙堆模型與自組織臨界性。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是否會影響沙堆模型中 的自組織臨界現(xiàn)象，一直以來就是該領(lǐng)域爭論的焦點(diǎn)。Zhou和Wang 對復(fù)雜網(wǎng)絡(luò)上沙堆模型的研究表明，沙堆模型中的雪崩動力學(xué)性質(zhì)對 網(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臨界模型等等。總的

16、來說，物理學(xué)家已經(jīng)開始學(xué)會把網(wǎng)絡(luò)拓?fù)湫再|(zhì)看作影響系統(tǒng)行為的一個特征量，這也很大程度上改變了我們對很 多物理過程原有的認(rèn)識。5復(fù)雜網(wǎng)絡(luò)研究簡史a格尼斯堡七橋問題。b隨機(jī)圖理論。20世紀(jì)60年代，由兩位匈牙利數(shù)學(xué)家 Erdcs和Re ny建立的隨機(jī)圖理論(random graph theory)被公認(rèn)為是在數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。Erdcs和Re nyi的最重要的發(fā)現(xiàn)是：ER隨機(jī)圖的許多重要性質(zhì)都是突然涌現(xiàn)的。也就是說，對于任一給定的概率P,要么幾乎每一個圖都具有某個性質(zhì) Q （比如說，連 通性），要么幾乎每一個圖都不具有該性質(zhì)。 在20世紀(jì)的后40年中, 隨機(jī)圖理論一直是研究復(fù)雜網(wǎng)

17、絡(luò)的基本理論。c小世界實(shí)驗(yàn)。20世紀(jì)60年代美國哈佛大學(xué)的社會心理學(xué)家Stanley Milgram通過一些社會調(diào)查后給出的推斷是：地球上任意兩個 人之間的平均距離是 6。這就是著名的 六度分離”（six degrees of separation）推斷。為了檢驗(yàn) 六度分離”的正確性，小世界實(shí)驗(yàn)一Bacon 數(shù)。美國Virginia大學(xué)計算機(jī)系的科學(xué)家建立了一個電影演員的數(shù)據(jù)庫，放在網(wǎng)上供人們隨意查詢。網(wǎng)站的數(shù)據(jù)庫里目前總共存有近60萬個世界各地的演員的信息以及近30萬部電影信息。通過簡單地輸入演員名字就可以知道這個演員的 Bacon數(shù)。有兩篇開創(chuàng)性的文章可以看作是復(fù)雜網(wǎng)絡(luò)研究新紀(jì)元開始的標(biāo)

18、志:一篇是美國康奈爾（Cornell）大學(xué)理論和應(yīng)用力學(xué)系的博士生Watts及其導(dǎo)師、非線性動力學(xué)專家Strogatz教授于1998年6月在Nature雜志上發(fā)表的題為 小世界”網(wǎng)絡(luò)的集體動力學(xué)（CollectiveDynamics of SmOWorld ' Networks）的文章；另一篇是美國NotreDame大學(xué)物理系的Barabcsi教授及其博士生Albert于1999年10月在Scienee雜志上發(fā)表的題為隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)（Emergenee ofScali ng in Ran dom Network®的文章。這兩篇文章分別揭示了復(fù)雜網(wǎng)絡(luò)的小世界特征和無標(biāo)度性

19、質(zhì)，并建立了相應(yīng)的模型以闡述這些特性 的產(chǎn)生機(jī)理。不同領(lǐng)域的復(fù)雜網(wǎng)絡(luò):社會網(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,專利使用，論文引用，計算機(jī)共享；技術(shù)網(wǎng)絡(luò): 電力網(wǎng)，In ternet，電話線路網(wǎng)；交通運(yùn)輸網(wǎng)：航線網(wǎng)，鐵路網(wǎng)，公路網(wǎng)，自然河流網(wǎng)。6復(fù)雜網(wǎng)絡(luò)研究內(nèi)容6.1 1)復(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)計量及與網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)性度分布的定義和意義，聚集性、連通性的統(tǒng)計量及其實(shí)際 意義等。3)復(fù)雜網(wǎng)絡(luò)性質(zhì)與結(jié)構(gòu)的關(guān)系同步性、魯棒性和穩(wěn)定性與網(wǎng)

20、絡(luò)結(jié)構(gòu)的關(guān)系。4)復(fù)雜網(wǎng)絡(luò)的動力學(xué)信息傳播動力學(xué)、網(wǎng)絡(luò)演化動力學(xué)、網(wǎng)絡(luò)混沌動力學(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ò)正向與逆向建模。8）復(fù)雜邏輯網(wǎng)絡(luò)邏輯與高階邏輯定義、分類、判定算法，高階邏輯的實(shí)際意義等等。F1: 2B; F2:(A, B) TC;F3:(A, B, C)D A, B, C,取布爾值。6.2復(fù)雜網(wǎng)絡(luò)研究 a突破性進(jìn)展的主要原因 越來越強(qiáng)大的計算設(shè)備和迅猛發(fā)展的In ter net,使得人們開始能夠收集和處理規(guī)模巨大且種類不同的實(shí)際網(wǎng)絡(luò)數(shù)據(jù)。

21、 學(xué)科之間的相互交叉使得研究人員可以廣泛比較各種不同類型的 網(wǎng)絡(luò)數(shù)據(jù)，從而揭示復(fù)雜網(wǎng)絡(luò)的共性。以還原理論和整體論相結(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)計性質(zhì)，以及度量這些性質(zhì)的 合適方法。建模：建立合適的網(wǎng)絡(luò)模型以及理解網(wǎng)絡(luò)的統(tǒng)計性質(zhì)的意義與產(chǎn) 生機(jī)理。分析：基于單個節(jié)點(diǎn)的特性和整個網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)分析與預(yù)測網(wǎng) 絡(luò)的行為?？刂疲禾岢龈纳埔延芯W(wǎng)絡(luò)性能和設(shè)計新的網(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ù)

22、目。直觀上看，一個節(jié)點(diǎn)的度越大就意味著這個節(jié)點(diǎn)在某種意義上 越“重要”(“能力大”)。網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度和的平均值，記作vk>。事實(shí)上，vk>=2q/ P。度分布函數(shù)p(k):隨機(jī)選定節(jié)點(diǎn)的度恰好為k的概率。節(jié)點(diǎn)的聚類系數(shù)(簇系數(shù))：在簡單圖中,設(shè)節(jié)點(diǎn)v的鄰集為N(v),個節(jié)點(diǎn)之間存在邊數(shù)E|N(v)|=ki,則節(jié)點(diǎn)v的聚類系數(shù)定義為這ki與總的可能邊數(shù)ki(ki-1)/2之比，即：C=2E/ki(ki-1)，節(jié)點(diǎn)v的鄰點(diǎn)間C=l二網(wǎng)絡(luò)中任關(guān)系的密切程度。網(wǎng)絡(luò)的聚類系數(shù) C:所有節(jié)點(diǎn)i的聚類系數(shù)C的平均值。(0蘭C蘭1) C=0二網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是孤立點(diǎn);意節(jié)點(diǎn)間都有

23、邊相連，網(wǎng)絡(luò)節(jié)點(diǎn)間聯(lián)系的密切程度,體現(xiàn)網(wǎng)絡(luò)的凝聚力。許多大規(guī)模的實(shí)際網(wǎng)絡(luò)都具有明顯的聚類效應(yīng)。事實(shí)上，在很多類型的網(wǎng)絡(luò)(如社會關(guān)系網(wǎng)絡(luò))中，你的朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于某個非零常數(shù)，即當(dāng)N7乂時，C=0(1。這意味著這些實(shí)際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的，而是在某種程度上 具有類似于社會關(guān)系網(wǎng)絡(luò)中 物以類聚，人以群分”的特性。最短路徑(Shortest path):兩個節(jié)點(diǎn)之間邊數(shù)最少的路徑，最短路徑的長度稱為兩點(diǎn)。所有節(jié)點(diǎn)對之間的距離的平均值。研究發(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)的最短路徑的

24、條數(shù)。邊介數(shù)：網(wǎng)絡(luò)中通過該邊的最短路徑的條數(shù)。 反映了節(jié)點(diǎn)或邊的 作用和影響力。如果一對節(jié)點(diǎn)間共有 B條不同的最短路徑，其中有b條經(jīng)過節(jié)點(diǎn)i，那么節(jié)點(diǎn)i對這對節(jié)點(diǎn)的介數(shù)的貢獻(xiàn)為b/B。把節(jié)點(diǎn)i對所有節(jié)點(diǎn)對的貢獻(xiàn)累加起來再除以節(jié)點(diǎn)對總數(shù)，就可得到節(jié)點(diǎn)i的介數(shù)。類似的，邊的介數(shù)定義為所有節(jié)點(diǎn)對的最短路徑中經(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ù)

25、。核數(shù) 一個圖的k-核：反復(fù)去掉圖中度小于等于 k的節(jié)點(diǎn)后，所剩余的子圖若一個節(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)在核中的深度； 即便一個節(jié)點(diǎn)的度 數(shù)很高，它的核數(shù)也可能很小。例如：包含N個節(jié)點(diǎn)的星型網(wǎng)絡(luò)的中 心節(jié)點(diǎn)的度數(shù)為N-1，但它的核數(shù)為0。7小世界實(shí)驗(yàn) a六度分離米爾格倫的實(shí)驗(yàn)過程是：他計劃通過人傳人的送信方式來統(tǒng)計人 與人之間的聯(lián)系。首先把信交給志愿者 A告訴他信最終要送給收信人 S。如果他不認(rèn)識S,那么就送信到某個他認(rèn)識的人 B手里，理由是A認(rèn)為在他的交集圈里B是

26、最可能認(rèn)識S的。但是如果B也不認(rèn)識S,那么B同 樣把信送到他的一個朋友 C手中，,就這樣一步步最后信終于到達(dá)S那里。這樣就從A到B到C至卜最后到S連成了一個鏈。斯坦 利？米爾格倫就是通過對這個鏈做了統(tǒng)計后做出了六度分離的結(jié)論。然而在這個實(shí)驗(yàn)中，實(shí)際上只有三分之一的信送到了收信人那里，因此實(shí)驗(yàn)的完成率很低。我們或許有過這樣的經(jīng)歷：偶爾碰到一個陌生人,同他聊了一會后發(fā)現(xiàn)你認(rèn)識的某個人居然他也認(rèn)識，然后一起發(fā)出”這個世界真小”第四者這樣的感嘆。那么對于世界上任意兩個人來說，借助第三者、 的間接關(guān)系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人 呢？美國社會心理學(xué)家斯坦利？米爾格倫(Stanley M

27、ilgram)在1967年通過一些實(shí)驗(yàn)后得出結(jié)論：中間的聯(lián)系人平均只需要5個。他把這個 結(jié)論稱為“六度分離”。六度分離：平均只要通過5個人，你就能與世界任何一個角落的 任何一個人發(fā)生聯(lián)系。這個結(jié)論定量地說明了我們世界的”大小” 或者說人與人關(guān)系的緊密程度。30多年來，六度分離理論一直被作為社會心理學(xué)的經(jīng)典范例之一。盡管如此，實(shí)際上這個理論并沒有得到嚴(yán)格的證實(shí)。 美國心理學(xué)教授 朱迪斯？克蘭菲爾德Judith Kleinfeld)對米爾格倫最初的實(shí)驗(yàn)提出不同意見，因?yàn)樗l(fā)現(xiàn)實(shí)驗(yàn)的完成率極低。b Bacon數(shù)截止到幾天前，世界電影史上共產(chǎn)生了大約23萬部電影，78多萬名電影演員，Kavin Bac

28、on在許多部電影中飾演小角色。幾年前,Virginia大學(xué)的計算機(jī)專家Brett Tjaden設(shè)計了一個游戲,他聲稱電影演員Kevin Bacon是電影界的中心。在游戲里定義了一個所謂的 Bacon數(shù)：隨便想一個演員，如果他（她）和Kavin Bacon一起演過電影，那么他（她）的Bacon數(shù)就為1；如果他（她）沒有和Bacon演過電影，但是和Bacon數(shù)為1的演員一起演過電影，那么他的Bacon數(shù)就為2;依此類推。發(fā)現(xiàn):在曾經(jīng)參演的美國電影演員中，沒有一個人的 Bacon數(shù)超過4。在網(wǎng)上有一個網(wǎng)頁 http:/www.cs.virgi /oracle/網(wǎng)站的數(shù)據(jù)庫里總共存有有7

29、83940個世界各地的演員的信息以及231,088 部電影信息。通過簡單地輸入演員名字就可以知道這個演員的bacon數(shù)。目前比如輸入Stephen Chow（周星馳）就可以得到這樣的結(jié)果：周星馳在1991年的豪門夜宴（Haomen yeyan）中與洪金寶（Sammo HungKam-Bo合作；而洪金寶又在李小龍的最后一部電影，即1978年的死亡的游戲(Game of Death)中與 Colleen Camp 合作；Colleen Camp在去年的電影Trapped中與Kevin Bacon合作。這樣周星馳的Bacon數(shù)為3。對78萬個演員所做的統(tǒng)計：演員的最大Bacon數(shù)僅僅為8,平均Bac

30、on數(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位。但若加上別人所做但曾獲他關(guān)鍵性提示之論文，則他的論文應(yīng)有數(shù)萬篇。他的研究領(lǐng)域主要是數(shù)論和組合數(shù)學(xué)， 但他的論文中涵蓋的學(xué)科 有逼近論、初等幾何、集合論、概率論、數(shù)理邏輯、格與序代數(shù)結(jié)構(gòu)、 線性代數(shù)、群論、拓?fù)淙?、多項式、測度論、單復(fù)變函數(shù)、差分方程 與函數(shù)方程、數(shù)列、Fourier分析、泛函分析、一般拓?fù)浜痛鷶?shù)拓?fù)洹?

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

32、題和他討論，于是很快地一篇論文便誕生了。數(shù)學(xué)家以下述方式來定義 Erdos數(shù)(Erdos number) : Erdos本人之Erdos數(shù)為0，任何人若曾與Erdos合寫過論文，則其 Erdos數(shù)為1。任何人若曾與一位Erdos數(shù)為1(且不曾與有更少的Erdos數(shù))的人合寫 過論文，則他的Erdos數(shù)為2幾乎每一個當(dāng)代數(shù)學(xué)家都有一個有限的Erdos數(shù)，而且這個數(shù)往往非常小，小得出乎本人的預(yù)料。比如說證明Fermat大定理的An drewWiles，他的研究方向與Erdos相去甚遠(yuǎn)，但他的Erdos數(shù)只有3,是通過這個途徑實(shí)現(xiàn)的：Erdos-Andrew Odlyzko-ChrisM.Ski n

33、n er-A ndrew Wiles。Fields獎得主的Erdos數(shù)都不超過5,(只有Cohen和Grothendieck的Erdos數(shù)是5), Neva niinna獎得主的Erdos數(shù)不超過3,(只有Valia nt的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)域的專 家，如：比爾蓋茲(Bill Gates),他的Erdos數(shù)是4,通過如下途徑實(shí)現(xiàn):Erdos-Pavol Hell-Xiao

34、Tie Deng-Christos H. Papadimitriou-WilliamH.(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ò)、社會、經(jīng) 濟(jì)管理等領(lǐng)域。在論述已有工作的基礎(chǔ)上，構(gòu)建了一個In ternet的復(fù)雜網(wǎng)絡(luò)模型，對病毒的傳播行為進(jìn)行了仿真研究，結(jié)果表明，構(gòu)建的網(wǎng)絡(luò)模型真實(shí)地反映了 In ter net的特性，通過對某些參數(shù)的調(diào)整，病毒傳播可以得到有效控制。通信網(wǎng)絡(luò)可以看成是由成千上萬個路由器節(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ù)據(jù)傳輸過程，用