復(fù)雜網(wǎng)絡(luò)的自相似性研究.ppt

《復(fù)雜網(wǎng)絡(luò)的自相似性研究.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、復(fù)雜網(wǎng)絡(luò)的自相似性研究報告人：陶少華導(dǎo)師：劉玉華教授2006年1月引言復(fù)雜網(wǎng)絡(luò)模型簡介復(fù)雜網(wǎng)絡(luò)的自相似性研究仿真分析結(jié)論參考文獻1.引言1960年數(shù)學(xué)家Erdos和Renyi提出了隨機圖理論，研究復(fù)雜網(wǎng)絡(luò)中隨機的拓撲模型，自此ER模型一直是研究復(fù)雜網(wǎng)絡(luò)的基本模型。但是，但是近年的研究發(fā)現(xiàn)：現(xiàn)實網(wǎng)絡(luò)中得到的許多實驗數(shù)據(jù)結(jié)果與隨機圖模型并不符合，因此需要新的網(wǎng)絡(luò)模型合理描述實際網(wǎng)絡(luò)。1998年Watts和Strgatz提出了小世界（WS）模型[2]，刻畫了真實的網(wǎng)絡(luò)所兼有的大聚簇和短平均路徑距離的特性。然而現(xiàn)實世界中的網(wǎng)絡(luò)還被統(tǒng)計到極少數(shù)接點擁有大

2、量的連接，而眾多的接點僅具有少量連接的特性，這些也無法用隨機圖模型加以合理解釋。1999年Barabasi和Albert提出了無尺度模型（BA）[3]。BA模型指出了決定互聯(lián)網(wǎng)、萬維網(wǎng)等網(wǎng)絡(luò)具有無尺度模型的兩個基本原理：增長性和擇優(yōu)連接。雖然小世界網(wǎng)絡(luò)與無尺度網(wǎng)絡(luò)刻畫了網(wǎng)絡(luò)的基本特性，但它們是基于對現(xiàn)實網(wǎng)絡(luò)進行簡化的前提下得到的結(jié)果。因此我們有必要對復(fù)雜網(wǎng)絡(luò)建模進行深入研究，使它更加符合現(xiàn)實世界。本文提出了網(wǎng)絡(luò)的自相似性，網(wǎng)絡(luò)通過節(jié)點與節(jié)點相連匯聚形成，節(jié)點與節(jié)點之間是通過某種共性而連接在一起的。如人際關(guān)系之間的“物以類聚，人以群分”。。2.復(fù)

3、雜網(wǎng)絡(luò)模型簡介復(fù)雜網(wǎng)絡(luò)就是具有復(fù)雜拓撲結(jié)構(gòu)和動力行為的大規(guī)模網(wǎng)絡(luò)，它是由大量的節(jié)點通過邊的相互連結(jié)而構(gòu)成的圖。根據(jù)不同的拓撲結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)可以分為規(guī)則網(wǎng)絡(luò)，隨機網(wǎng)絡(luò)，小世界網(wǎng)絡(luò)，無尺度網(wǎng)絡(luò)等等。2.1小世界網(wǎng)絡(luò)模型1998年，Watts和Strogatz提出了小世界網(wǎng)絡(luò)模型。這個模型介于規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)之間并在他們之間起橋梁作用。建立網(wǎng)絡(luò)模型步驟如下：初始化：從具有個節(jié)點的環(huán)形網(wǎng)絡(luò)開始，其中每一節(jié)點都與它初始的個鄰居相連（在每一邊有個鄰居）。隨機化：以概率隨機為規(guī)則網(wǎng)絡(luò)的每條邊重新連線，同時保證沒有自連結(jié)和重連邊，這一過程引進條長距離捷徑（重新

4、連結(jié)的邊）邊，它們連結(jié)那些擁有不同鄰居的部分節(jié)點。當=0時，對就的為網(wǎng)絡(luò)規(guī)則圖，當時，對應(yīng)的為隨機網(wǎng)絡(luò)圖，當介于（0,1）區(qū)間任意值時，模型顯示出小世界特性。（1）規(guī)則圖（2）小世界（3）隨機圖小世界網(wǎng)絡(luò)的主要特點：度分布為指數(shù)分布且峰值取平均值，每個節(jié)點有大致相同數(shù)目的連結(jié)數(shù)，平均路徑短且聚集系數(shù)大如圖，其中為平均路徑，為聚集系數(shù)。小世界網(wǎng)絡(luò)介于規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)之間，它實現(xiàn)了從規(guī)則到完全隨機之間的連續(xù)演變。2.2無尺度網(wǎng)絡(luò)模型1999年，Barabasi和Albert提出了無尺度網(wǎng)絡(luò)模型，它通過增加新的節(jié)點而實現(xiàn)連續(xù)增長，同時這些新的節(jié)點總

5、是傾向于選擇連結(jié)已經(jīng)具有大量連結(jié)的節(jié)點。BA模型具體描述如下：增長性：假設(shè)網(wǎng)絡(luò)最初有個節(jié)點。每一次加入一個新節(jié)點，每次加入的新節(jié)點通過條新加入的連結(jié)邊與網(wǎng)絡(luò)中已有的個節(jié)點相連。優(yōu)先連結(jié)：我們假設(shè)每個新節(jié)點與節(jié)點相連的概率都依賴于節(jié)點的度，并且這個概率服從如下的規(guī)則：根據(jù)上述步驟重復(fù)次后得到一個有個節(jié)點和條邊的網(wǎng)絡(luò)。在1999年.Barabási,與Albert用數(shù)量模擬表明具有k條邊的節(jié)點的概率服從指數(shù)為r=3的冪律分布，如圖3：無尺度網(wǎng)絡(luò)的主要特點為度分布為冪律分布，極少數(shù)節(jié)點有大量的連結(jié)，而大多數(shù)節(jié)點只有很少的連結(jié)。同時，無尺度還具有某些重

6、要特性，可以承受意外的故障，但對惡意攻擊卻很脆弱。3.自相似性復(fù)雜網(wǎng)絡(luò)3.1問題的提出雖然小世界網(wǎng)絡(luò)、無尺度網(wǎng)絡(luò)比較準確地把握了現(xiàn)實世界中網(wǎng)絡(luò)最基本的特性，但它們?nèi)匀淮嬖谝欢ǖ木窒扌?。在現(xiàn)實世界中一些網(wǎng)絡(luò)常常并不具有冪律特征，如指數(shù)中止、小變量飽和等。為了在微觀層面更深入研究復(fù)雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和演化規(guī)律，研究人員作了大量新的嘗試和努力，對網(wǎng)絡(luò)的演化與建模已經(jīng)有了長足的進展，演化因素包括各種類型的擇優(yōu)連接、局域世界、適應(yīng)度[4]、競爭等。盡管眾多的網(wǎng)絡(luò)演化模型已經(jīng)被用來分析和研究可能潛藏的演化規(guī)律，但這些研究仍然忽視了一些重要因素。例如計算機網(wǎng)絡(luò)

7、節(jié)點之間的連接。如果是按照擇優(yōu)連接概率：則新的節(jié)點會全部連接到同一個節(jié)點上，但現(xiàn)實網(wǎng)絡(luò)并非如此，而是形成不同的集散節(jié)點。這個例子說明了網(wǎng)絡(luò)節(jié)點之間的連接有可能是基于一些相似的性質(zhì)，節(jié)點與節(jié)點之間有某種共性才相連。因此建立并研究基于相似性的網(wǎng)絡(luò)演化模型有利于我們更好地認識現(xiàn)實世界中的復(fù)雜網(wǎng)絡(luò)。3.2自相似性網(wǎng)絡(luò)容量維數(shù)1975年美國數(shù)學(xué)系教授曼德布羅特首次提出了“分形”概念，其原意是“不規(guī)則的、非整數(shù)的、支離破碎的”物體，我們把具有某種自相似性的圖形或集合稱為分形。大自然中存在的不規(guī)則的物體，可能存在不同尺度上的相似性，稱為自相似性。自相似性就是

8、局部與整體相似，局部中又有相似的局部，每一小局部中包含的細節(jié)并不比整體所包含的少，不斷重復(fù)的無窮嵌套，形成了奇妙的分形圖案，它不但包括嚴格的幾何相似性