復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性

1、復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第1頁目錄概率統(tǒng)計(jì)預(yù)備知識(shí)網(wǎng)絡(luò)(圖)基礎(chǔ)概念規(guī)則圖和隨機(jī)網(wǎng)Scale-free網(wǎng)絡(luò)常見軟件參考文件復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第2頁一、概率統(tǒng)計(jì)預(yù)備知識(shí)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第3頁目錄隨機(jī)變量與分布函數(shù)（離散、連續(xù)）隨機(jī)變量數(shù)字特征（數(shù)學(xué)期望、方差）泊松分布冪函數(shù)指數(shù)函數(shù)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第4頁隨機(jī)變量與分布函數(shù)對(duì)某個(gè)隨機(jī)試驗(yàn) ，假如每次試驗(yàn)結(jié)果能夠用一個(gè)數(shù)X來表示，而且對(duì)任何實(shí)數(shù)k，Xx有著確定概率，則稱X是隨機(jī)變量。隨機(jī)變量X值小于實(shí)數(shù)k概率P(Xx)是x函數(shù)，記作 F(k)=P(X0是常數(shù)，則稱變量X服從參數(shù)為 泊松分布，記為 復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第14頁

2、復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第15頁于是，x數(shù)學(xué)期望為：即復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第16頁復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第17頁所以，X方差和均方差分別為： 復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第18頁指數(shù)函數(shù)對(duì)公式線性化，兩邊取對(duì)數(shù)得令則復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第19頁指數(shù)函數(shù)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第20頁冪函數(shù)式中 為實(shí)數(shù)。對(duì)公式線性化，兩邊取對(duì)數(shù)，得令 ， ， 得函數(shù)形式為：復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第21頁冪函數(shù)變量代換可在雙對(duì)數(shù)坐標(biāo)上得直線， 復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第22頁二、網(wǎng)絡(luò)(圖)基礎(chǔ)概念復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第23頁中國(guó)教科網(wǎng)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第24頁網(wǎng)絡(luò)(圖)基礎(chǔ)概念節(jié)點(diǎn)通常見來表示系統(tǒng)中部件；邊通常見來表示系統(tǒng)中部件之間關(guān)

3、系。網(wǎng)絡(luò)(圖)就是由節(jié)點(diǎn)與節(jié)點(diǎn)之間關(guān)系組成一張圖。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第25頁中國(guó)教科網(wǎng)拓?fù)浣Y(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第26頁網(wǎng)絡(luò)（圖）基礎(chǔ)概念關(guān)聯(lián)與鄰接度、平均度節(jié)點(diǎn)度分布最短路徑與平均路徑長(zhǎng)度群系數(shù)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第27頁網(wǎng)絡(luò)(圖)基礎(chǔ)概念aedcb復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第28頁有向圖、無向圖、不連通圖復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第29頁網(wǎng)絡(luò)(圖)基礎(chǔ)概念節(jié)點(diǎn)度分布是指網(wǎng)絡(luò)（圖）中度為 節(jié)點(diǎn)概率 隨節(jié)點(diǎn)度 改變規(guī)律。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第30頁網(wǎng)絡(luò)(圖)基礎(chǔ)概念最短路徑就是從指定始點(diǎn)到指定終點(diǎn)全部路徑中總權(quán)最小一條路經(jīng)。平均路徑長(zhǎng)度是指全部點(diǎn)對(duì)之間最短路徑算術(shù)平均值。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第31頁網(wǎng)

4、絡(luò)(圖)基礎(chǔ)概念集群系數(shù)(Clustering coefficient)反應(yīng)網(wǎng)絡(luò)群集程度，定義為網(wǎng)絡(luò)平均度與網(wǎng)絡(luò)規(guī)模之比。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第32頁22 77 55553311網(wǎng)絡(luò)(圖)基礎(chǔ)概念復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第33頁節(jié)點(diǎn)1到7之間最短路13，平均路徑長(zhǎng)度5.47，平均度為3.4，集群系數(shù)為0.48。網(wǎng)絡(luò)(圖)基礎(chǔ)概念復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第34頁三、規(guī)則圖和隨機(jī)圖規(guī)則圖特征假如系統(tǒng)中節(jié)點(diǎn)及其與邊關(guān)系是固定，每個(gè)節(jié)點(diǎn)都有相同度數(shù)，就能夠用規(guī)則圖來表示這個(gè)系統(tǒng)。隨機(jī)圖特征假如系統(tǒng)中節(jié)點(diǎn)及其與邊關(guān)系不確定，就只能用隨機(jī)圖來表示這個(gè)系統(tǒng)。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第35頁規(guī)則圖特征平均度為3。復(fù)雜網(wǎng)絡(luò)

5、的無標(biāo)度特性第36頁隨機(jī)圖特征節(jié)點(diǎn)確定，但邊以概率 任意連接。節(jié)點(diǎn)不確定，點(diǎn)邊關(guān)系也不確定。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第37頁隨機(jī)圖節(jié)點(diǎn)19，邊43平均度為2.42，集群系數(shù)為0.13。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第38頁隨機(jī)圖節(jié)點(diǎn)42，邊118平均度為5.62，集群系數(shù)為0.133。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第39頁四、Scale-free網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第40頁目錄早期網(wǎng)絡(luò)模型無標(biāo)度Scale-free網(wǎng)絡(luò)BA模型復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第41頁早期網(wǎng)絡(luò)模型ER模型小世界模型復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第42頁ER模型Erds和Rnyi （ER）最早提出隨機(jī)網(wǎng)絡(luò)模型并對(duì)模型進(jìn)行了深入研究，他們是用概率統(tǒng)計(jì)方法研究

6、隨機(jī)圖統(tǒng)計(jì)特征創(chuàng)始人。在模型開始階段給定N個(gè)節(jié)點(diǎn)，沒有邊，以概率p用邊連接任意一對(duì)節(jié)點(diǎn)，用這么方法產(chǎn)生一隨機(jī)網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第43頁復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第44頁ER模型Erds和Rnyi（1959）首先研究了在隨機(jī)網(wǎng)絡(luò)中最大和最小度分布，Bollobs(1981)隨即得到了全部度分布形式，推導(dǎo)出度數(shù)為k節(jié)點(diǎn)數(shù)遵從平均值為 泊松分布，即 復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第45頁Connect with probability pp=1/6 N=10 k 1.5Poisson distribution復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第46頁小世界模型為了描述從一個(gè)局部有序系統(tǒng)到一個(gè)隨機(jī)網(wǎng)絡(luò)轉(zhuǎn)移過程，Watts和

7、 Strogatz（WS）提出了一個(gè)新模型，通常稱為小世界網(wǎng)絡(luò)模型。WS模型始于一含有N個(gè)節(jié)點(diǎn)一維網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)與其最近鄰接點(diǎn)和次鄰接點(diǎn)相連接，然后每條邊以概率p重新連接。約束條件為節(jié)點(diǎn)間無重邊，無自環(huán)。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第47頁C(p) : clustering coeff. L(p) : average path lengthP(k)=0.1 p(k)=0.3復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第48頁小世界模型當(dāng)p等于0時(shí)，對(duì)應(yīng)網(wǎng)絡(luò)規(guī)則圖。兩個(gè)節(jié)點(diǎn)間平均距離線性地隨N增加而增加，集群系數(shù)大。當(dāng)p等于1時(shí)，系統(tǒng)變?yōu)殡S機(jī)圖。 對(duì)數(shù)地隨N增加而增加，且集群系數(shù)隨N降低而降低。在p等于（0，1）區(qū)間任意值時(shí)，

8、模型顯示出小世界特征，約等于隨機(jī)圖值，網(wǎng)絡(luò)含有高度集群性。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第49頁復(fù)雜網(wǎng)絡(luò)都含有分布于平均值兩邊度分布曲線嗎？復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第50頁無標(biāo)度(Scale-free)網(wǎng)絡(luò)Scale-free網(wǎng)絡(luò)發(fā)覺Scale-free網(wǎng)絡(luò)特征復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第51頁Scale-free)網(wǎng)絡(luò)發(fā)覺信息交換網(wǎng)（萬維網(wǎng)、國(guó)際互聯(lián)網(wǎng)、電話網(wǎng)、電力網(wǎng)）社會(huì)網(wǎng)絡(luò)（電影演員合作網(wǎng)、科研合作圖、引文網(wǎng)、人類性接觸網(wǎng)、語言學(xué)網(wǎng)）生物網(wǎng)絡(luò)（細(xì)胞網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)、蛋白質(zhì)折疊）復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第52頁復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第53頁復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第54頁Scale-free網(wǎng)絡(luò)特征度分布呈冪率分布中樞節(jié)

9、點(diǎn)出現(xiàn)穩(wěn)健性脆弱性復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第55頁復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第56頁復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第57頁無標(biāo)度網(wǎng)絡(luò)與隨機(jī)圖特征比較復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第58頁無標(biāo)度（Scale-free）網(wǎng)絡(luò)無標(biāo)度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，現(xiàn)實(shí)網(wǎng)絡(luò)無標(biāo)度特征源于眾多網(wǎng)絡(luò)所共有兩種生成機(jī)制： （）網(wǎng)絡(luò)經(jīng)過增添新節(jié)點(diǎn)而連續(xù)擴(kuò)張； （）新節(jié)點(diǎn)擇優(yōu)連接到含有大量連接節(jié)點(diǎn)上。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第59頁BA模型增加和擇優(yōu)連接這兩種要素激勵(lì)了BarabsiAlbert模型提出，該模型首次導(dǎo)出度分布按冪函數(shù)規(guī)律改變網(wǎng)絡(luò)。模型算法以下：（1）增加：開始于較少節(jié)點(diǎn)數(shù)量

10、（m0），在每個(gè)時(shí)間間隔增添一個(gè)含有m（m0）條邊新節(jié)點(diǎn)，連接這個(gè)新節(jié)點(diǎn)到m個(gè)不一樣已經(jīng)存在于系統(tǒng)中節(jié)點(diǎn)上。（2）擇優(yōu)連接：在選擇新節(jié)點(diǎn)連接點(diǎn)時(shí)，假設(shè)新節(jié)點(diǎn)連接到節(jié)點(diǎn)i概率取決于節(jié)點(diǎn)i度數(shù)即復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第60頁經(jīng)過t時(shí)間間隔后，該算法程序產(chǎn)生一含有N=t+m0個(gè)節(jié)點(diǎn)，mt條邊網(wǎng)絡(luò)。數(shù)量模擬表明含有k條邊節(jié)點(diǎn)概率服從指數(shù)為r=3冪指數(shù)分布。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第61頁P(yáng)(k) k-3A.-L.Barabsi, R. Albert, Science 286, 509 (1999)復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第62頁BA模型（a)Barabsi-Albert模擬度分布。（b）不一樣系統(tǒng)規(guī)模下 。 復(fù)

11、雜網(wǎng)絡(luò)的無標(biāo)度特性第63頁BA模型設(shè)節(jié)點(diǎn) i 度 滿足動(dòng)態(tài)方程：分母求和是對(duì)系統(tǒng)中除新進(jìn)入系統(tǒng)節(jié)點(diǎn)外全部節(jié)點(diǎn)進(jìn)行 ，則復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第64頁BA模型當(dāng)t足夠大時(shí)，有解微分方程，有復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第65頁由初始條件得解為 式中可給出度小于k節(jié)點(diǎn)概率 復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第66頁設(shè)在相同時(shí)間間隔，添加節(jié)點(diǎn)到網(wǎng)絡(luò) 中， 值含有常數(shù)概率密度 代入前式t趨于無窮時(shí)度分布 式中復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第67頁模型度分布是與時(shí)間無關(guān)漸進(jìn)分布且與系統(tǒng)規(guī)模無關(guān)。 冪律度分布系數(shù)與 成正比 。無標(biāo)度模型動(dòng)態(tài)特征能夠用各種分析方法給出 ： 連續(xù)域理論 主方程法 改變率方程法 復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第68頁Bar

12、alsi-Albert模型限制條件 保持了網(wǎng)絡(luò)增加特征，不考慮擇優(yōu)連接，網(wǎng)絡(luò)度分布呈指數(shù)衰減。 消除了增加過程，只考慮擇優(yōu)連接，絡(luò)度分布圍繞其均值為一高斯分布。復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第69頁Baralsi-Albert模型擴(kuò)展研究初始吸引度非線性擇優(yōu)連接擇優(yōu)連接更迭機(jī)理 增加制約條件及增加方式局部相互作用適應(yīng)度模型復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第70頁五、常見軟件SasMatlabPajekOriginNetdrawWaxmanGt-itmTiers BriteInetPlarg復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性第71頁六、主要參考文件Albert, R., H. Jeong, and A.-L. Barabsi, Diameter of the World-Wide-Web,1999, Nature (London)401, 130. Barabsi, A.-L., and R. Albert, Emergence of scaling in random networks, 1999, Science 286, 509 .Barabsi, A.-L., R. Albert, and H. Jeong, Me