復雜網絡及其matlab模擬

1、 畢 業(yè) 論 文題 目： 復雜網絡及其matlab模擬 學 院： 物理與電子工程學院 專 業(yè)： 物理學 畢業(yè)年限： 2015 學生姓名： 學 號： 指導教師： 復雜網絡及其matlab模擬 班級：物理學2班 姓名： 指導教師： 摘 要 近年來,關于復雜網絡的研究正方興未艾,1998年Watts和Strogatz在Nature雜志上發(fā)表文章,引入了小世界(Small一World)網絡模型。本文對復雜網絡的特性還有無標度與小世界網絡進行簡單介紹，詳細介紹各個模型的生成與算法，并用matlab軟件進行了模擬。關鍵詞 復雜網絡 無標度 小世界 模擬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引言 在人類生存的整個空間甚至宇宙中都存在著大量復雜系統(tǒng)，這些系統(tǒng)可以通過形形色色的網絡加以描述。一個典型的網絡是由許多節(jié)點與連接兩個節(jié)點之間的一些邊組成的，其中節(jié)點用來代表真實系統(tǒng)中不同的個體，而邊則用來表示個體間的關系，往往是兩個節(jié)點之間具有某種特定的關系則連一條邊，反

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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