復雜網(wǎng)絡的無標度特性

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

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

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

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

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

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

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

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

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

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

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

12、alsi-Albert模型限制條件 保持了網(wǎng)絡增加特征，不考慮擇優(yōu)連接，網(wǎng)絡度分布呈指數(shù)衰減。 消除了增加過程，只考慮擇優(yōu)連接，絡度分布圍繞其均值為一高斯分布。復雜網(wǎng)絡的無標度特性第69頁Baralsi-Albert模型擴展研究初始吸引度非線性擇優(yōu)連接擇優(yōu)連接更迭機理 增加制約條件及增加方式局部相互作用適應度模型復雜網(wǎng)絡的無標度特性第70頁五、常見軟件SasMatlabPajekOriginNetdrawWaxmanGt-itmTiers BriteInetPlarg復雜網(wǎng)絡的無標度特性第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