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

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

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

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

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

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

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

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

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

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