《復雜網(wǎng)絡理論及其應用》讀書筆記

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

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

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

4、是隨機網(wǎng)絡。隨后，Newma n和Watts給出了一種新的網(wǎng)絡的構造方法，在他們的網(wǎng)絡（NW網(wǎng)絡） 中，原有的連邊并不會被破壞，平均距離的縮短源于以一個很小的概 率在原來的規(guī)則網(wǎng)絡上添加新的連邊。后來物理學家把大的簇系數(shù)和 小的平均距離兩個統(tǒng)計特征合在一起稱為小世界效應，具有這種效應 的網(wǎng)絡就是小世界網(wǎng)絡（small-world networks ）。圖1 :小世界網(wǎng)絡拓撲結構示意圖左邊的網(wǎng)絡是規(guī)則的，右邊的網(wǎng) 絡是隨機的，中間的網(wǎng)絡是在規(guī)則網(wǎng)絡上加上一點隨機的因素而形成 的小世界網(wǎng)絡，它同時具有大的簇系數(shù)和小的平均距離。大量的實證研究表明， 真實網(wǎng)絡幾乎都具有小世界效應， 同時科 學家還發(fā)現(xiàn)

5、大量真實網(wǎng)絡的節(jié)點度服從冪率分布， 這里某節(jié)點的度是 指該節(jié)點擁有相鄰節(jié)點的數(shù)目， 或者說與該節(jié)點關聯(lián)的邊的數(shù)目。 節(jié) 點度服從冪律分布就是說具有某個特定度的節(jié)點數(shù)目與這個特定的 度之間的關系可以用一個冪函數(shù)近似地表示。 冪函數(shù)曲線是一條下降 相對緩慢的曲線， 這使得度很大的節(jié)點可以在網(wǎng)絡中存在。 對于隨機 網(wǎng)絡和規(guī)則網(wǎng)絡， 度分布區(qū)間非常狹窄， 幾乎找不到偏離節(jié)點度均值 較大的點， 故其平均度可以被看作其節(jié)點度的一個特征標度。 在這個 意義上，我們把節(jié)點度服從冪律分布的網(wǎng)絡叫做無標度網(wǎng)絡（ scale -free networks ），并稱這種節(jié)點度的冪律分布為網(wǎng)絡的無標度特性。 1999年

6、，Barabdsi和Albert給出了構造無標度網(wǎng)絡的演化模型，他們 所用的方法與Price的方法是類似的。Barabdsi和Albert把真實系 統(tǒng)通過自組織生成無標度的網(wǎng)絡歸功于兩個主要因素： 生長和優(yōu)先連 接，而他們的網(wǎng)絡模型 （BA 網(wǎng)絡）正是模擬這兩個關鍵機制設計的。除了小世界效應和無標度特性外， 真實網(wǎng)絡還有很多統(tǒng)計上的特 征，例如混合模式，度相關特性，超小世界性質等等。 3復雜系統(tǒng)與復雜網(wǎng)絡3.1 復雜系統(tǒng)與復雜網(wǎng)絡的概念系統(tǒng)定義：集合（具體元素） + 結構 +功能。例：不同角度分析 系統(tǒng)，人。系統(tǒng)的結構是： 一切系統(tǒng)的基礎結構都是網(wǎng)絡； 一切系統(tǒng)的核 心結構都是邏輯網(wǎng)絡； 復雜

7、系統(tǒng)的結構就是復雜網(wǎng)絡。復雜網(wǎng)絡是構成復雜系統(tǒng)的基本結構， 每個復雜系統(tǒng)都可以看作 是單元或個體之間的相互作用網(wǎng)絡； 復雜網(wǎng)絡在刻畫復雜性方面的重 要性是由于結構決定功能的。 復雜網(wǎng)絡是研究復雜系統(tǒng)的一種角度和 方法，它關注系統(tǒng)中因子相互關聯(lián)作用的拓撲結構， 是理解復雜系統(tǒng) 性質和功能的基礎。3.2 復雜系統(tǒng)與復雜網(wǎng)絡的主要特性：a 開放性。即與環(huán)境和其它系統(tǒng)進行相互作用， 交換物質、 能量、 信息，保持和發(fā)展系統(tǒng)內部的有序性與結構穩(wěn)定性。在這種交換中， 系統(tǒng)經歷著從低級向高級、 從簡單到復雜、 從無序向有序的不斷優(yōu)化 的動態(tài)發(fā)展過程。 雖然開放性是所有真實系統(tǒng)的基本屬性， 但這里的 開放非指

8、一般意義上的相互作用與交流，而開放的度量、性質、強度 對復雜系統(tǒng)的性態(tài)、 演化具有決定性的意義。 例子，人，城市網(wǎng)絡簇。b 涌現(xiàn)性。即內部元素通過非線性相互作用，在宏觀層次上產生 出新的、元素不具有的整體屬性，表現(xiàn)為整體斑圖、模式等。雖然涌 現(xiàn)同樣是所有系統(tǒng)都具有的，但這里涌現(xiàn)意味著新的整體屬性的產 生。例子， “整體大于部分之和 ”， 大腦的神經網(wǎng)絡系統(tǒng)。c 演化性（不可逆性） 。即通過與所在環(huán)境中的其它系統(tǒng)的相互 作用和內部的自組織，使系統(tǒng)發(fā)展到新的階段，表現(xiàn)出階段性、臨界 性，完成系統(tǒng)演化的生命周期。例 :社會網(wǎng)絡中的人，生物群體的自 組織系統(tǒng)（鳥群）。d 復雜性。包括系統(tǒng)的結構、行為、

9、功能等多個方面同時具有的 復雜性。結構復雜性表現(xiàn)為多元性， 非對稱性， 非均勻性，非線性（分 岔(Bifurcation),混沌(Chaos),分形Fractal);行為復雜性表現(xiàn)為學 習，自適應性，混沌同步，混沌邊沿，隨機性等等；認識復雜性又稱 為主觀復雜性，它表現(xiàn)為不確定性，描述復雜性與計算復雜性等等。 例:神經網(wǎng)絡中的突觸有強有弱，可抑制也可興奮。e網(wǎng)絡結構。即系統(tǒng)內部和系統(tǒng)之間的相互作用可以看成由節(jié)點、 邊(連接)構成的體系，出現(xiàn)網(wǎng)絡復雜性、小世界特征與無標度特征 等。3.3網(wǎng)絡系統(tǒng)的復雜性a 結構復雜性網(wǎng)絡連接結構錯綜復雜、極其混亂，同時又蘊含著豐富的結構： 社區(qū)、基序、聚集性、生成

10、規(guī)律性等等，而且網(wǎng)絡連接結構可能是隨 時間變化的，例如，WWW上每天都不停地有頁面和鏈接的產生和刪 除。 靜態(tài)結構的復雜性和結構動態(tài)演化的復雜性。 例：神經系統(tǒng)由 神經元互連形成，連接以 “突觸連接結構 ”實現(xiàn)，突觸有強弱、興奮與 抑制、不同的神經遞質;連接不斷改變，形成連接結構變化。 (重邊， 加權等)。b 節(jié)點復雜性1】節(jié)點的獨立或固有特性網(wǎng)絡中的節(jié)點可能是具有分岔和混沌等復雜非線 性行為的動力 系統(tǒng)。例如，基因網(wǎng)絡中每個節(jié)點都具有復雜的時間演化行為。 而且， 一個網(wǎng)絡中可能存在多種不同類型的節(jié)點。 例如，控制哺乳動物中細 胞分裂的生化網(wǎng)絡就包含各種各樣的基質和酶。2】關聯(lián)引發(fā)的節(jié)點特性當

11、關聯(lián)失去時這類特性會在節(jié)點處消失或改變。 例如，耦合神經 元重復地被同時激活， 那么它們之間的連接就會加強， 這被認為是記 憶和學習的基礎。3】復雜網(wǎng)絡之間相互影響的復雜性實際的復雜網(wǎng)絡會受到各種各樣因素的影響和作用。 例如，電力 網(wǎng)絡故障會導致 Internet 網(wǎng)速變慢， 運輸系統(tǒng)失控等一系列不同網(wǎng)絡 間的連鎖反應。4】網(wǎng)絡分層結構的復雜性 例如，行政管理網(wǎng)絡是具有層結構的， 多數(shù)網(wǎng)絡都有節(jié)點的分層 結構，只是在許多網(wǎng)絡中沒有意識到是一種造成復雜性的重要結構。復雜網(wǎng)絡是二十一世紀科學研究的思想和理念， 它啟發(fā)我們用什 么觀點理解這個世界： 整個世界以及組成世界的任何細部都是由網(wǎng)絡 及其變化

12、形成的。 復雜網(wǎng)絡也是研究復雜系統(tǒng)的一種技術和方法， 它 關注系統(tǒng)中個體相互作用的拓撲結構， 是理解復雜系統(tǒng)性質和功能的 基本方法。4復雜網(wǎng)絡上的物理過程對于物理學家而言， 研究復雜網(wǎng)絡的終極目標是理解網(wǎng)絡拓撲結 構對物理過程的影響。 在以前的研究中， 物理學家往往忽略了網(wǎng)絡的 拓撲性質，在討論逾滲、傳播、同步等物理過程時，他們自然地選擇 了最容易模擬和分析的規(guī)則網(wǎng)絡或者隨機網(wǎng)絡， 而沒有仔細思考和研 究這種選擇是不是應該的， 不同的選擇會不會對物理過程產生不可忽略的影響。以網(wǎng)絡上的傳播動力學模型為例，由于傳統(tǒng)的網(wǎng)絡傳播模 型大都是基于規(guī)則網(wǎng)絡的，因此，復雜網(wǎng)絡不同統(tǒng)計特征的發(fā)現(xiàn)使科 學家面臨

13、更改既有結論的危險。當然，如果理論研究和實驗結果都說 明復雜網(wǎng)絡上的傳播動力學行為與規(guī)則網(wǎng)絡別無二致，那么我們至少暫時還可以心安理得地使用以前的結論。但是，不幸的是，復雜網(wǎng)絡 上的傳播行為與規(guī)則網(wǎng)絡相比確實存在根本上的不同。類似的情況還出現(xiàn)在其他的物理過程中，下面我們將簡略地介紹網(wǎng)絡拓撲性質對某 些典型物理過程的影響。逾滲模型與疾病傳播動力學。之所以在這里把逾滲模型和網(wǎng)絡上 的疾病傳播動力學問題歸在一起討論，是因為網(wǎng)絡上的疾病傳播模型 可以等價于鍵逾滲模型。以前的基于規(guī)則網(wǎng)絡的研究表明，疾病在網(wǎng) 絡中的平均波及范圍與疾病的傳染強度正相關， 而疾病的傳染強度有 一個閾值，只有當其值大于這個閾值時

14、，疾病才能在網(wǎng)絡中長期存在， 否則感染人數(shù)會指數(shù)衰減。根據(jù)這個理論，疾病若是持久存在，則必 然波及大量個體。但實證研究表明，計算機病毒，麻疹等一般僅波及 少數(shù)個體但能夠長期存在。這一理論與實證的矛盾在很長時間里一直 困擾著科學界。近年來的研究表明在無標度網(wǎng)絡中沒有正的傳播閾 值，也就是說即使疾病的傳染強度接近零，只波及非常少的個體，也 能在網(wǎng)絡中長期存在。由于大部分真實網(wǎng)絡是無標度網(wǎng)絡，因此該結 論很好地解決了上面的矛盾?；煦缤?。近十余年來，混沌動力系統(tǒng) 在網(wǎng)絡上的同步性能吸引了大量科學家的關注。 早期的研究主要是針 對以最近鄰環(huán)網(wǎng)為代表的規(guī)則網(wǎng)絡，研究表明對于給定的非零耦合強 度，當節(jié)點數(shù)

15、目很大時網(wǎng)絡無法實現(xiàn)同步。最近幾年的研究卻表明， 盡管小世界網(wǎng)絡只是在規(guī)則網(wǎng)絡進行一個非常小的修正的結果， 但其 實現(xiàn)混沌同步的能力卻遠遠好于規(guī)則網(wǎng)絡。 對于小世界上的廣義混沌 同步與超混沌同步的研究同樣表明， 小世界網(wǎng)絡有明顯好于規(guī)則網(wǎng)絡 的同步能力。 物理學家還考察了無標度網(wǎng)絡， 研究表明其混沌同步的 能力與星形網(wǎng)絡幾乎是一樣的， 這可能是因為它與星形網(wǎng)絡都具有很 不均勻的節(jié)點度分布。沙堆模型與自組織臨界性 。網(wǎng)絡拓撲結構是否會影響沙堆模型中 的自組織臨界現(xiàn)象，一直以來就是該領域爭論的焦點。 Zhou 和 Wang 對復雜網(wǎng)絡上沙堆模型的研究表明， 沙堆模型中的雪崩動力學性質對 網(wǎng)絡拓撲結

16、構非常敏感， 相比規(guī)則網(wǎng)絡， 無標度網(wǎng)絡上大雪崩發(fā)生更 為頻繁，最大雪崩的規(guī)模也大得多。 物理性質明顯依賴于網(wǎng)絡拓撲結 構的物理過程還很多， 例如隨機游走， 玻色愛因斯坦凝聚 49-51 ， XY 臨界模型等等。總的來說，物理學家已經開始學會把網(wǎng)絡拓撲性 質看作影響系統(tǒng)行為的一個特征量， 這也很大程度上改變了我們對很 多物理過程原有的認識。5復雜網(wǎng)絡研究簡史a 格尼斯堡七橋問題。b隨機圖理論。20世紀60年代，由兩位匈牙利數(shù)學家 Erdcs和 Re ny建立的隨機圖理論(random graph theory)被公認為是在數(shù)學上 開創(chuàng)了復雜網(wǎng)絡理論的系統(tǒng)性研究。 Erdcs和Re nyi的最重

17、要的發(fā)現(xiàn) 是：ER隨機圖的許多重要性質都是突然涌現(xiàn)的。也就是說，對于任 一給定的概率p,要么幾乎每一個圖都具有某個性質 Q （比如說，連 通性），要么幾乎每一個圖都不具有該性質。 在 20世紀的后 40年中， 隨機圖理論一直是研究復雜網(wǎng)絡的基本理論。c 小世界實驗。 20 世紀 60 年代美國哈佛大學的社會心理學家Stanley Milgram通過一些社會調查后給出的推斷是：地球上任意兩個人之間的平均距離是 6。這就是著名的 六度分離”（six degrees of separation）推斷。為了檢驗 六度分離”的正確性，小世界實驗一Bacon 數(shù)。美國 Virginia 大學計算機系的科學

18、家建立了一個電影演員的數(shù)據(jù) 庫,放在網(wǎng)上供人們隨意查詢。網(wǎng)站的數(shù)據(jù)庫里目前總共存有近 60 萬個世界各地的演員的信息以及近 30 萬部電影信息。通過簡單地輸 入演員名字就可以知道這個演員的 Bacon數(shù)。有兩篇開創(chuàng)性的文章可以看作是復雜網(wǎng)絡研究新紀元開始的標志：一篇是美國康奈爾（Cornell）大學理論和應用力學系的博士生Watts及其導師、非線性動力學專家 Strogatz教授于1998年6月在 Nature雜志上發(fā)表的題為 小世界”網(wǎng)絡的集體動力學（Collective Dynamics of SmOWorld ' Networks）的文章；另一篇是美國NotreDame大學物理系

19、的Barabcsi教授及其博士生Albert于1999年10月 在Scienee雜志上發(fā)表的題為隨機網(wǎng)絡中標度的涌現(xiàn)（Emergenee of Scali ng in Ran dom Network®的文章。這兩篇文章分別揭示了復雜網(wǎng) 絡的小世界特征和無標度性質,并建立了相應的模型以闡述這些特性 的產生機理。不同領域的復雜網(wǎng)絡：社會網(wǎng)：演員合作網(wǎng)，友誼網(wǎng)，姻親關系網(wǎng)，科研合作網(wǎng)， Email 網(wǎng)；生物網(wǎng)：食物鏈網(wǎng)，神經網(wǎng)，新陳代謝網(wǎng)， 蛋白質網(wǎng)， 基因網(wǎng)絡； 信息網(wǎng)絡：WWW,專利使用，論文引用，計算機共享；技術網(wǎng)絡： 電力網(wǎng)，In ternet，電話線路網(wǎng)；交通運輸網(wǎng)：航線網(wǎng)，鐵路

20、網(wǎng)，公 路網(wǎng),自然河流網(wǎng)。6 復雜網(wǎng)絡研究內容6.11）復雜網(wǎng)絡模型 典型的復雜網(wǎng)絡：隨機網(wǎng)、小世界網(wǎng)、無標度網(wǎng)等；實際網(wǎng)絡及其分類。2）網(wǎng)絡的統(tǒng)計量及與網(wǎng)絡結構的相關性度分布的定義和意義, 聚集性、連通性的統(tǒng)計量及其實際 意義等。3）復雜網(wǎng)絡性質與結構的關系同步性、魯棒性和穩(wěn)定性與網(wǎng)絡結構的關系。4）復雜網(wǎng)絡的動力學 信息傳播動力學、網(wǎng)絡演化動力學、網(wǎng)絡混沌動力學。5）復雜網(wǎng)絡的復雜結構 社團結構、層次結構、節(jié)點分類結構等。6）網(wǎng)絡控制關鍵節(jié)點控制、主參數(shù)控制和控制的穩(wěn)定性和有效性。7）復雜網(wǎng)絡建模機理建模、數(shù)據(jù)建模和實際系統(tǒng)的復雜網(wǎng)絡正向與逆向建模。8) 復雜邏輯網(wǎng)絡 邏輯與高階邏輯定義、

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

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

23、v的鄰集為N(v), |N(v)|=ki,則節(jié)點v的聚類系數(shù)定義為這ki個節(jié)點之間存在邊數(shù) E 與總的可能邊數(shù)ki(ki-1)/2之比，即：Ci=2E/ki(ki-1)，節(jié)點v的鄰點間 關系的密切程度。網(wǎng)絡的聚類系數(shù) C:所有節(jié)點i的聚類系數(shù)C的平 均值。(OC1) C=0=網(wǎng)絡中所有節(jié)點都是孤立點； C=1=網(wǎng)絡中任 意節(jié)點間都有邊相連，網(wǎng)絡節(jié)點間聯(lián)系的密切程度，體現(xiàn)網(wǎng)絡的凝聚 力。許多大規(guī)模的實際網(wǎng)絡都具有明顯的聚類效應。事實上，在很多類型的網(wǎng)絡(如社會關系網(wǎng)絡)中，你的朋友同時也是朋友的概率會隨 著網(wǎng)絡規(guī)模的增加而趨向于某個非零常數(shù)，即當N-k時，C=0(1。這意味著這些實際的復雜網(wǎng)絡并

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

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

26、可以表明節(jié)點在核中的深度； 即便一個節(jié)點的度 數(shù)很高，它的核數(shù)也可能很小。例如：包含N個節(jié)點的星型網(wǎng)絡的中 心節(jié)點的度數(shù)為N-1，但它的核數(shù)為0。7 小世界實驗a 六度分離米爾格倫的實驗過程是： 他計劃通過人傳人的送信方式來統(tǒng)計人 與人之間的聯(lián)系。首先把信交給志愿者 A,告訴他信最終要送給收信人 S。如果他 不認識S,那么就送信到某個他認識的人 B手里，理由是A認為在他 的交集圈里B是最可能認識S的。但是如果B也不認識S,那么B同 樣把信送到他的一個朋友 C手中，,就這樣一步步最后信終于到達S那里。這樣就從A到B到C至卜最后到S連成了一個鏈。斯坦 利?米爾格倫就是通過對這個鏈做了統(tǒng)計后做出了六

27、度分離的結論。然而在這個實驗中，實際上只有三分之一的信送到了收信人那 里，因此實驗的完成率很低。我們或許有過這樣的經歷： 偶爾碰到一個陌生人， 同他聊了一會 后發(fā)現(xiàn)你認識的某個人居然他也認識， 然后一起發(fā)出”這個世界真小” 的感嘆。那么對于世界上任意兩個人來說，借助第三者、第四者這樣 的間接關系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人 呢？美國社會心理學家斯坦利？米爾格倫(Stanley Milgram)在1967年 通過一些實驗后得出結論： 中間的聯(lián)系人平均只需要 5 個。他把這個 結論稱為“六度分離”。六度分離 : 平均只要通過 5 個人，你就能與世界任何一個角落的 任何一個人發(fā)生聯(lián)

28、系。這個結論定量地說明了我們世界的”大小” ， 或者說人與人關系的緊密程度。30多年來，六度分離理論一直被作為社會心理學的經典范例之一。 盡管如此， 實際上這個理論并沒有得到嚴格的證實。 美國心理學教授 朱迪斯？克蘭菲爾德(Judith Kleinfeld)對米爾格倫最初的實驗提出不同意見，因為她發(fā)現(xiàn)實驗的完成率極低b Bacor數(shù)截止到幾天前，世界電影史上共產生了大約23萬部電影，78多萬名電影演員，Kavi n Bacon在許多部電影中飾演小角色。幾年前,Virginia大學的計算機專家Brett Tjaden設計了一個游戲， 他聲稱電影演員Kevin Bacon是電影界的中心。在游戲里定

29、義了一個所謂的 Bacon數(shù)：隨便想一個演員，如果他 （她）和Kavin Bacon一起演過電影，那么他（她）的Bacon數(shù)就為1; 如果他（她）沒有和Bacon演過電影，但是和Bacon數(shù)為1的演員一 起演過電影，那么他的Bacon數(shù)就為2;依此類推。發(fā)現(xiàn)：在曾經參 演的美國電影演員中，沒有一個人的 Bacon數(shù)超過4。在網(wǎng)上有一個網(wǎng)頁 /oracle/。網(wǎng)站的數(shù) 據(jù)庫里總共存有有783940個世界各地的演員的信息以及 231,088部 電影信息。通過簡單地輸入演員名字就可以知道這個演員的bacon數(shù)。目前比如輸入Stephen Chow（周星

30、馳）就可以得到這樣的結果：周星馳在 1991年的豪門夜宴（Haomen yeyan）中與洪金寶（Sammo Hung Kam-Bo合作；而洪金寶又在李小龍的最后一部電影，即1978年的死 亡的游戲（Game of Death）中與 Colleen Camp 合作；Colleen Camp 在去年的電影Trapped中與Kevin Bacon合作。這樣周星馳的Bacon 數(shù)為3。對78萬個演員所做的統(tǒng)計：演員的最大Bacon數(shù)僅僅為8,平 均 Bacon 數(shù)僅為 2.948。c Erdos數(shù)Paul Erdos(1913-1996)是出生于匈牙利的猶太籍數(shù)學家，被公 認為 20 世紀最偉大的天才

31、之一。Erdos 畢生發(fā)表的論文超過 1500 篇(在數(shù)學史上僅次于歐拉 (Euler ， 1707-1783)，超長的合作者名單 ,合作者超過 450 位。但若加 上別人所做但曾獲他關鍵性提示之論文，則他的論文應有數(shù)萬篇。他的研究領域主要是數(shù)論和組合數(shù)學， 但他的論文中涵蓋的學科 有逼近論、初等幾何、集合論、概率論、數(shù)理邏輯、格與序代數(shù)結構、 線性代數(shù)、群論、拓撲群、多項式、測度論、單復變函數(shù)、差分方程 與函數(shù)方程、數(shù)列、Fourier分析、泛函分析、一般拓撲和代數(shù)拓撲、 統(tǒng)計、數(shù)值分析、計算機科學、信息論等等。"Mathematical Reviews" 曾把數(shù)學劃分為

32、大約六十個分支， Erdos 的論文涉及到了其中的 40%.Erdos 從來沒有一個固定的職位，從來不定居在一個地方，也沒 有結婚，帶著一半空的手提箱，穿梭于學術研討會，浪跡天涯，頗富 傳奇色彩。有人稱他為流浪學者 (wande ring scholar)。他效忠的是科學的皇后， 而非一特定的地方。各地都有熱心的 數(shù)學家提供他舒適的食宿，安排他的一切，他則對招待他的主人，給 出一些挑戰(zhàn)性的數(shù)學難題，或給予研究上的指導做為回饋。他可以和許多不同領域的數(shù)學家合作。 數(shù)學家常將本身長久解決 不了的問題和他討論，于是很快地一篇論文便誕生了。數(shù)學家以下述方式來定義 Erdos數(shù)（Erdos number

33、） : Erdos本人之Erdos數(shù)為0,任何人若曾與 Erdos合寫過論文，則其 Erdos數(shù)為1。 任何人若曾與一位Erdos數(shù)為1（且不曾與有更少的Erdos數(shù)）的人合寫 過論文，則他的Erdos數(shù)為2幾乎每一個當代數(shù)學家都有一個有限的Erdos數(shù)，而且這個數(shù)往往非常小，小得出乎本人的預料。比如說證明Fermat大定理的An drew Wiles，他的研究方向與Erdos相去甚遠，但他的Erdos數(shù)只有3,是 通 過 這 個 途 徑 實 現(xiàn) 的 ： Erdos-Andrew Odlyzko-Chris M.Skinner-Andrew Wiles。Fields獎得主的Erdos數(shù)都不超過

34、5,（只有Cohen和Grothendieck 的Erdos數(shù)是5）, Neva nlinna獎得主的Erdos數(shù)不超過3,（只有Valia nt 的Erdos數(shù)是3）, Wolf數(shù)學獎得主的Erdos數(shù)不超過6,（只有V丄Arnold 是6,且只有Kolmogorov是5）, Steele獎的終身成就獎得主的 Erdos 數(shù)不超過 4。在具有有限Erdos數(shù)的人名單中往往還能發(fā)現(xiàn)一些其他領域的專 家，如：比爾蓋茲（Bill Gates）,他的Erdos數(shù)是4,通過如下途徑實現(xiàn)： Erdos-Pavol Hell-Xiao Tie Deng-Christos H. Papadimitriou-

35、William H.（Bill） Gates。愛因斯坦的Erdos數(shù)是2。8 復雜網(wǎng)絡理論的應用研究目前國內關于復雜網(wǎng)絡的應用研究主要涉及信息網(wǎng)絡、 社會、經 濟管理等領域。 在論述已有工作的基礎上， 構建了一個 Internet 的復 雜網(wǎng)絡模型，對病毒的傳播行為進行了仿真研究，結果表明，構建的 網(wǎng)絡模型真實地反映了 Internet 的特性， 通過對某些參數(shù)的調整， 病 毒傳播可以得到有效控制。通信網(wǎng)絡可以看成是由成千上萬個路由器節(jié)點以及節(jié)點之間的 數(shù)百萬條通信線路組成的邊所構成的復雜網(wǎng)絡。 實際通信網(wǎng)絡經常承 受超負荷的流量，導致?lián)砣漠a生。陳振毅等利用 BA 無標度網(wǎng)絡模 型來模擬通信網(wǎng)絡中的數(shù)據(jù)傳輸過程， 用節(jié)