復(fù)雜網(wǎng)絡(luò)及其matlab模擬

1、 畢 業(yè) 論 文題 目： 復(fù)雜網(wǎng)絡(luò)及其matlab模擬 學(xué) 院： 物理與電子工程學(xué)院 專 業(yè)： 物理學(xué) 畢業(yè)年限： 2015 學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 復(fù)雜網(wǎng)絡(luò)及其matlab模擬 班級：物理學(xué)2班 姓名： 指導(dǎo)教師： 摘 要 近年來,關(guān)于復(fù)雜網(wǎng)絡(luò)的研究正方興未艾,1998年Watts和Strogatz在Nature雜志上發(fā)表文章,引入了小世界(Small一World)網(wǎng)絡(luò)模型。本文對復(fù)雜網(wǎng)絡(luò)的特性還有無標度與小世界網(wǎng)絡(luò)進行簡單介紹，詳細介紹各個模型的生成與算法，并用matlab軟件進行了模擬。關(guān)鍵詞 復(fù)雜網(wǎng)絡(luò) 無標度 小世界 模擬Abstract In recent years, t

2、he research on complex networks of academia is be just unfolding, in particular, the two pioneering work set off an upsurge in the study of complex networks.In 1998 Watts and Strogatz published an article In this paper, the properties of complex networks are scale-free and small world networks are b

3、riefly introduced,Generation and algorithm details of each model, and use MATLAB software to simulate.Key word Complex network； Scale free； Small World； Simulation引言 在人類生存的整個空間甚至宇宙中都存在著大量復(fù)雜系統(tǒng)，這些系統(tǒng)可以通過形形色色的網(wǎng)絡(luò)加以描述。一個典型的網(wǎng)絡(luò)是由許多節(jié)點與連接兩個節(jié)點之間的一些邊組成的，其中節(jié)點用來代表真實系統(tǒng)中不同的個體，而邊則用來表示個體間的關(guān)系，往往是兩個節(jié)點之間具有某種特定的關(guān)系則連一條邊，反

4、之則不連邊，有邊相連的兩個節(jié)點在網(wǎng)絡(luò)中被看作是相鄰的。例如，神經(jīng)系統(tǒng)可以看作大量神經(jīng)細胞通過神經(jīng)纖維相互連接形成的網(wǎng)絡(luò)1；計算機網(wǎng)絡(luò)可以看作是自主工作的計算機通過通信介質(zhì)如光纜、雙絞線、同軸電纜等相互連接形成的網(wǎng)絡(luò)2,類似的還有電力網(wǎng)絡(luò)1、社會關(guān)系網(wǎng)絡(luò)1,4、交通網(wǎng)絡(luò)等等。數(shù)學(xué)家和物理學(xué)家在研究網(wǎng)絡(luò)的時候，往往只關(guān)心節(jié)點之間有沒有邊相連，至于節(jié)點到底在什么位置，邊是長還是短，是彎曲還是平直，有沒有相交等等都是他們不在意的。在這里，我們把網(wǎng)絡(luò)不依賴于節(jié)點的具體位置和邊的具體形態(tài)就能表現(xiàn)出來的性質(zhì)叫做網(wǎng)絡(luò)的拓撲性質(zhì)，相應(yīng)的結(jié)構(gòu)叫做網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。那么，什么樣的拓撲結(jié)構(gòu)比較適合用來描述真實的系統(tǒng)呢？

5、 本文首先介紹了復(fù)雜網(wǎng)絡(luò)的研究進展及其統(tǒng)計特征，然后對小世界網(wǎng)絡(luò)和無標度網(wǎng)絡(luò)模型及各模型的matlab模擬作了詳細介紹。1 復(fù)雜網(wǎng)絡(luò)的發(fā)展及統(tǒng)計特征1.1復(fù)雜網(wǎng)絡(luò)的發(fā)展由于現(xiàn)實世界網(wǎng)絡(luò)的規(guī)模大，節(jié)點間相互作用復(fù)雜，其拓撲結(jié)構(gòu)基本上未知或未曾探索。兩百多年來，人們對描述真實系統(tǒng)拓撲結(jié)構(gòu)的研究經(jīng)歷了三個階段。在最初的一百多年里，科學(xué)家們認為真實系統(tǒng)要素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示，例如大數(shù)學(xué)家歐拉的哥尼斯堡七橋問題8，哥尼斯堡是當(dāng)時東普魯士的首都，今俄羅斯加里寧格勒市，普萊格爾河橫貫其中，這條河上建有七座橋，將河中間的兩個島和河岸聯(lián)結(jié)起來，。有人在閑暇散步時提出：能不能每座橋都只走一遍，最后

6、又回到原來的位置。大數(shù)學(xué)家歐拉用一種獨特的方法給出了解答。他把兩座小島和河的兩岸分別看作四個點，分別用A、B、C和D表示，而把七座橋看作這四個點之間的連線，分別用a、b、c、d、e、f和g表示（如圖1）。于是這個問題就簡化成：能不能用一筆就把這個圖形畫出來？經(jīng)過進一步的分析，歐拉得出結(jié)論：不可能每座橋都走一遍，最后回到原來的位置，并且給出了所有能夠一筆畫出來的圖形所應(yīng)具有的條件。圖1 歐拉哥尼斯堡七橋問題英國數(shù)學(xué)家哈密頓于1859年以游戲的形式提出：把一個正十二面體的二十個節(jié)點看成二十個城市，要求找出一條經(jīng)過每個城市恰好一次而回到出發(fā)點的路線，這條路線就稱“哈密頓圈”9。1852年，畢業(yè)于倫敦

7、大學(xué)的格思里來到一家科研單位做地圖著色工作時，發(fā)現(xiàn)了一個有趣的現(xiàn)象：每幅地圖都可以用四種顏色著色，使得有共同邊界的國家著上不同的顏色9。1959年，兩個匈牙利著名的數(shù)學(xué)家Erdös和Rényi建立了著名的隨機圖理論，用相對簡單的隨機圖來描述網(wǎng)絡(luò)，簡稱ER隨機圖理論5。ER隨機圖理論對圖論理論研究的影響長達近40年，以至于在隨后的近半個世紀，隨機圖一直是科學(xué)家研究真實網(wǎng)絡(luò)最有力的武器。直到最近幾年，科學(xué)家們發(fā)現(xiàn)大量的真實網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò)，也不是隨機網(wǎng)絡(luò)，而是具有與前兩者皆不同的統(tǒng)計特性的網(wǎng)絡(luò)，其中最有影響的是美國的 Watts和Strogatz于1998年發(fā)表了題為“小世界

8、”網(wǎng)絡(luò)的群體動力行為的論文1，推廣了“六度分離”的科學(xué)假設(shè)8，提出了小世界網(wǎng)絡(luò)模型?！傲确蛛x”最早來自于20世紀60年代美國哈佛大學(xué)心理學(xué)家Milgram對社會調(diào)查的推斷，是指在大多數(shù)人中，任意兩個素不相識的人通過朋友的朋友，平均最多通過6個人就能夠彼此認識。隨后Barabasi等人于1999年發(fā)表了題為隨機網(wǎng)絡(luò)中標度的涌現(xiàn)的論文6，提出了一個無標度網(wǎng)絡(luò)模型，指出在復(fù)雜網(wǎng)絡(luò)中節(jié)點的度分布具有冪指數(shù)函數(shù)的規(guī)（節(jié)點的度是指與該節(jié)點連接的邊數(shù)，而度分布是指網(wǎng)絡(luò)中所有節(jié)點的度的分布情況），其度分布可以用冪律形式進行描述。 近10年來，復(fù)雜網(wǎng)絡(luò)的研究正滲透到眾多不同的學(xué)科。推進復(fù)雜性科學(xué)的交叉研究，深

9、入探索和科學(xué)理解復(fù)雜網(wǎng)絡(luò)的定性特征與定量規(guī)律，使它獲得廣泛的應(yīng)用，對全球科學(xué)和社會的發(fā)展具有十分重大的長遠意義。1.2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特征平均路徑長度：網(wǎng)絡(luò)中兩個節(jié)點i到j(luò)之間的距離定義為連接這兩個節(jié)點的最短路徑上的邊數(shù)。網(wǎng)絡(luò)中任意兩個節(jié)點之間的距離的最大值稱為網(wǎng)絡(luò)的直徑，記為D。即：D=max(d)。網(wǎng)絡(luò)的平均路徑長度L定義為任意兩節(jié)點之間距離的平均值，即： （1）其中，N為網(wǎng)絡(luò)的總節(jié)點數(shù)，網(wǎng)絡(luò)的平均路徑長度也稱為網(wǎng)絡(luò)的特征路徑長度。集聚系數(shù)：集聚系數(shù)又稱作簇系數(shù)，它衡量的是網(wǎng)絡(luò)的集團化程度，是網(wǎng)絡(luò)的另一個重要參數(shù)。簇系數(shù)的概念有其深刻的社會根源。對社會網(wǎng)絡(luò)而言，集團化形態(tài)是其一個重要特征，集

10、團表示網(wǎng)絡(luò)中的朋友圈或熟人圈，集團中的成員往往相互熟悉，為衡量這種群集現(xiàn)象，科學(xué)家們提出了簇系數(shù)的概念。節(jié)點i的簇系數(shù)描述的是網(wǎng)絡(luò)中與該節(jié)點直接相連的節(jié)點之間的連接關(guān)系，即與該節(jié)點直接相鄰的節(jié)點間實際存在的邊數(shù)目占最大可能存在的邊數(shù)的比例，的表達式為： （2）式中表示節(jié)點i的度，表示節(jié)點i的鄰接點之間實際存在的邊數(shù)。網(wǎng)絡(luò)的簇系數(shù)為所有節(jié)點簇系數(shù)的算術(shù)平均值，即： （3）其中為網(wǎng)絡(luò)的階。不盡盡是社會網(wǎng)絡(luò)，在其它類型的網(wǎng)絡(luò)中，也普遍存在集聚現(xiàn)象。計算下面簡單網(wǎng)絡(luò)的直徑、平均距離和各節(jié)點的集聚系數(shù)。圖2網(wǎng)絡(luò)統(tǒng)計特征計算示意圖解：首先計算出所有節(jié)點對的距離：d121；d131；d142；d151；d1

11、62；d231；d241；d252；d262；d342；d352；d361；d453；d461；d563。由此可得直徑和平均距離和集聚系數(shù)分別為：直徑，平均距離，集聚系數(shù)。度分布：度分布是網(wǎng)絡(luò)的一個重要統(tǒng)計特征。這里的度（Degree）也稱為連通度（Connectivity），節(jié)點的度指的是與該節(jié)點連接的邊數(shù)。對網(wǎng)絡(luò)中所有節(jié)點的度求平均，可得到網(wǎng)絡(luò)的平均度k。度分布則表示節(jié)點度的概率分布函數(shù)，它指的是節(jié)點有條邊連接的概率。2小世界網(wǎng)絡(luò)模型及其模擬 1929 年，匈牙利作家 F.Karinthy 最早提出了“小世界現(xiàn)象”的論斷。他認為，在地球上的任何兩個人都可以平均通過一條由六位聯(lián)系人組成的鏈條

12、而聯(lián)系起來。而后，在1967 年，美國哈佛大學(xué)社會心理學(xué)教授Milgram 通過設(shè)計一個連鎖信件實驗，提出了著名的“六度分離”假說，即“小世界現(xiàn)象”1。這體現(xiàn)了一個似乎很普遍的規(guī)律：在如今的信息化時代，人們之間的關(guān)系已經(jīng)完全社會化，任何兩位素不相識的人都可能通過“六度空間”產(chǎn)生必然聯(lián)系或關(guān)聯(lián)。這一現(xiàn)象表明，在看似龐大的網(wǎng)絡(luò)中各要素之間的間隔實際上是非常“近”的，大家在世界上通過一步一步的社會相識尋找到目標的這個短鏈子理論普遍存在于各種社會、經(jīng)濟網(wǎng)絡(luò)中，科學(xué)家們把這種現(xiàn)象稱為小世界效應(yīng)1（Small-world effect）。為了用網(wǎng)絡(luò)圖來解釋“六度分離”的小世界效應(yīng)，Watts 和 Stro

13、gatz在對規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)理論研究的基礎(chǔ)上，于 1998 年提出了著名的 WS 小世界網(wǎng)絡(luò)1。WS模型提出后，很多學(xué)者在此基礎(chǔ)作了近一步改進，其中應(yīng)用最多的是Newman和Watts提出的所謂NW小世界模型。事實上，當(dāng)p很小N很大的時候，這兩個模型理論分析的結(jié)果是相同的，現(xiàn)在我們統(tǒng)稱它們?yōu)樾∈澜缒Ｐ?。前面我們已?jīng)簡單的介紹了一下小世界網(wǎng)絡(luò)的WS和NW模型，下面將著重介紹小世界網(wǎng)絡(luò)的ws模型的特點。2.1WS 模型構(gòu)造算法1998年, Watts和Strogatz 提出了小世界網(wǎng)絡(luò)這一概念,并建立了WS模型1。 實證結(jié)果表明,大多數(shù)的真實網(wǎng)絡(luò)都具有小世界特性(較小的最短路徑) 和聚類特性(較

14、大的聚類系數(shù)) 。 傳統(tǒng)的規(guī)則最近鄰耦合網(wǎng)絡(luò)具有高聚類的特性,但并不具有小世界特性;而ER 隨機網(wǎng)絡(luò)具有小世界特性但卻沒有高聚類特性。 因此這兩種傳統(tǒng)的網(wǎng)絡(luò)模型都不能很好的來表示實際的真實網(wǎng)絡(luò)。 Watts和Strogatz建立的WS小世界網(wǎng)絡(luò)模型就介于這兩種網(wǎng)絡(luò)之間,同時具有小世界特性和聚類特性,可以很好的來表示真實網(wǎng)絡(luò)1。WS 網(wǎng)絡(luò)模型同時具有平均路徑長度短集群系數(shù)高的特點，但是，它的度分布仍是一個輕尾的Poisson 分布，而且WS 網(wǎng)絡(luò)中不存在具有大量連接邊的中樞點，因此，它仍然是一個平衡網(wǎng)絡(luò)。近年來，研究人員對小世界網(wǎng)絡(luò)得結(jié)構(gòu)性質(zhì)和動力學(xué)行為進行了深入的探索，取得了豐富成果。研究表明

15、小世界網(wǎng)絡(luò)能夠增強信號的傳播速度、提高計、提高計算能力和網(wǎng)絡(luò)同步能力8。特別地，傳染性疾病在小世界網(wǎng)絡(luò)中傳播要比在規(guī)則網(wǎng)絡(luò)中容易得多。WS 模型的生成算法為：給定一個具有N 個結(jié)點的環(huán)形網(wǎng)絡(luò)規(guī)則，每一個結(jié)點對稱地與它最近的m(m<<N)個鄰點相連。而后對每個結(jié)點的每一條順時針邊以概率P 重連，對每個結(jié)點重復(fù)上述過程，得到的網(wǎng)絡(luò)稱為小世界網(wǎng)絡(luò)10。2.2小世界網(wǎng)絡(luò)模型設(shè)計及實現(xiàn)1、從規(guī)則圖開始：考慮一個含有N個點的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個環(huán)，其中每個節(jié)點都與它左右相鄰的各K/2節(jié)點相連，K是偶數(shù)。2、隨機化重連：以概率p隨機地重新連接網(wǎng)絡(luò)中的每個邊，即將邊的一個端點保持不變，而另

16、一個端點取為網(wǎng)絡(luò)中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。在上述模型中，p=0對應(yīng)于完全規(guī)則網(wǎng)絡(luò)，p=1則對應(yīng)于完全隨機網(wǎng)絡(luò)，通過調(diào)節(jié)p的值就可以控制從完全規(guī)則網(wǎng)絡(luò)到完全隨機網(wǎng)絡(luò)的過渡。網(wǎng)絡(luò)圖像如下：圖3不同概率下網(wǎng)絡(luò)示意圖網(wǎng)絡(luò)圖中各節(jié)點度的概率分布如下：圖4不同概率下各節(jié)點度的概率分布圖上面P=0.2時網(wǎng)絡(luò)圖顯示，大部分連邊保持不變，出現(xiàn)了少量捷徑，正是由于這少量捷徑造成了網(wǎng)絡(luò)的小世界效應(yīng)。3.無標度網(wǎng)絡(luò)模型及其模擬1999年，Alber和Barabds發(fā)現(xiàn)WWW 網(wǎng)頁的度分布不是通常認為的Poisson分布，而是重尾特征的冪

17、律分布，而且WWW 基本上是由少數(shù)具有大量超鏈接的網(wǎng)頁串連起來的，絕大部分網(wǎng)頁的鏈接很少，他們把網(wǎng)絡(luò)的這個特性稱為無標度性3(Scale-free nature，SF)。研究人員對大量的實際網(wǎng)絡(luò)進行了實證分析，發(fā)現(xiàn)許多網(wǎng)絡(luò)的度分布都是冪律的，要描述這些網(wǎng)絡(luò)的結(jié)構(gòu)和演化過程，隨機圖模型和小世界網(wǎng)絡(luò)模型顯然無能為力。1999年Barabdsi和Albert考察了實際網(wǎng)絡(luò)的生成機制，發(fā)現(xiàn)增長和擇優(yōu)連接是實際網(wǎng)絡(luò)演化過程的兩個基本要素，他們創(chuàng)造性地構(gòu)建了能夠產(chǎn)生無標度特性的第一個網(wǎng)絡(luò)模型BA模型6。BA模型的生成算法如下：(1)增長：網(wǎng)絡(luò)開始于少數(shù)幾個結(jié)點(個)，每個相等時問間隔增加一個新點，新點與m

18、()個不同的已經(jīng)存在于網(wǎng)絡(luò)中的舊點相連產(chǎn)生m條新邊。(2)擇優(yōu)連接：假設(shè)新點與舊點i相連的概率p取決于結(jié)點i的度數(shù)，即 （4）經(jīng)過t步時間步后，BA模型演化成一個具有N=t+個結(jié)點mt條邊的網(wǎng)絡(luò)。BA網(wǎng)絡(luò)主要具有以下特性：具有冪律度分布，是一個無標度網(wǎng)絡(luò)；具有小世界特征。冪律度分布的重尾特征導(dǎo)致無標度網(wǎng)絡(luò)中有少數(shù)具有大量連接邊的中樞點，擇優(yōu)連接必然產(chǎn)生“富者愈富”現(xiàn)象。BA 網(wǎng)絡(luò)同時具有魯棒性和脆弱性，面對結(jié)點的隨機失效，網(wǎng)絡(luò)具有魯棒性；但面對蓄意攻擊時，由于中樞點的存在，網(wǎng)絡(luò)變得十分脆弱，很容易陷于癱瘓9。3.1. 無標度網(wǎng)絡(luò)模型構(gòu)造算法按照BA模型的定義，針對Matlab語言的特點，以初始

19、節(jié)點等于3為例，設(shè)計如下算法11：第1：生成=3個結(jié)點的初始完全網(wǎng)絡(luò)，設(shè)置網(wǎng)絡(luò)規(guī)模為N()，并用Matlab特有的稀疏矩陣處理函數(shù)。第2：每隔一個固定時段加入一個新的結(jié)點，按照概率p()與原有網(wǎng)絡(luò)結(jié)點產(chǎn)生m條無重復(fù)連邊，重復(fù)上述過程N-次；第3：存儲N=100個結(jié)點的網(wǎng)絡(luò)鄰接矩陣。下面分別就N=10、N=60、N=100、 做圖：圖5無標度網(wǎng)絡(luò)生成的演化圖上面三幅圖對應(yīng)的網(wǎng)絡(luò)圖中各節(jié)點度的概率分布如下： 圖6節(jié)點數(shù)不同時各節(jié)點度的概率分布圖上面組圖顯示，大部分結(jié)點的連邊較少，少數(shù)結(jié)點具有大量的連邊，這些具有大量連邊的結(jié)點構(gòu)成了網(wǎng)絡(luò)的中樞點。當(dāng)結(jié)點個數(shù)無限增加時，網(wǎng)絡(luò)結(jié)點的度分布為冪律分布，可以

20、用冪律形式P（k）k即P（k）=ak網(wǎng)絡(luò)即為無標度網(wǎng)絡(luò)。轉(zhuǎn)換為對數(shù)函數(shù)：lnP（k）=lna-lnk令lnP為y，k為x則y=lna-x，當(dāng)=2，a=1時函數(shù)圖如下：圖7各節(jié)點度的概率分布雙對數(shù)曲線許多實際大規(guī)模無標度網(wǎng)絡(luò)，其冪指數(shù)通常為23，絕大多數(shù)節(jié)點的度相對很低，也存在少量度值相對很高的節(jié)點，把這類網(wǎng)絡(luò)稱為無標度網(wǎng)絡(luò)。4. 結(jié)語現(xiàn)實世界中許許多多的復(fù)雜網(wǎng)絡(luò)都是具有小世界或無尺度特征的復(fù)雜網(wǎng)絡(luò)，從生物體中的大腦結(jié)構(gòu)到各種新陳代謝網(wǎng)絡(luò),從Internet到WWW,從大型電力網(wǎng)絡(luò)到全球交通網(wǎng)絡(luò),從科研合作網(wǎng)絡(luò)到各種政治、經(jīng)濟、社會關(guān)系網(wǎng)絡(luò)等等,數(shù)不勝數(shù)。因此，對小世界網(wǎng)絡(luò)和無標度網(wǎng)絡(luò)及其模型進

21、行更深入的研究是非常必要的。參考文獻1 Watts, D.J. and Strogatz, S.H. Collective dynamics of “small world” networks. Nature,393, 440-442,（1998）2 Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topologyC/ACM SIGCOMM Computer Communication Review. ACM, 1999, 29(4): 251-262.3 Albert R, Barabasi A.L.，Statistical mechanics of complex networksJ. Reviews of Modern Phys