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

1、復雜網(wǎng)絡的無標度特性第1頁，共73頁，2022年，5月20日，13點27分，星期二目錄概率統(tǒng)計預備知識網(wǎng)絡(圖)的基本概念規(guī)則圖和隨機網(wǎng)Scale-free網(wǎng)絡常用軟件參考文獻第2頁，共73頁，2022年，5月20日，13點27分，星期二一、概率統(tǒng)計預備知識第3頁，共73頁，2022年，5月20日，13點27分，星期二目錄隨機變量與分布函數(shù)（離散、連續(xù)）隨機變量的數(shù)字特征（數(shù)學期望、方差）泊松分布冪函數(shù)指數(shù)函數(shù)第4頁，共73頁，2022年，5月20日，13點27分，星期二隨機變量與分布函數(shù)對某個隨機試驗 ，如果每次試驗的結(jié)果可以用一個數(shù)X來表示，而且對任何實數(shù)k，Xx有著確定的概率，則稱X是隨

2、機變量。隨機變量X的值小于實數(shù)k的概率P(Xx)是x的函數(shù)，記作 F(k)=P(X0是常數(shù)，則稱變量X服從參數(shù)為 泊松分布，記為 第14頁，共73頁，2022年，5月20日，13點27分，星期二第15頁，共73頁，2022年，5月20日，13點27分，星期二于是，x的數(shù)學期望為：即第16頁，共73頁，2022年，5月20日，13點27分，星期二第17頁，共73頁，2022年，5月20日，13點27分，星期二所以，X的方差和均方差分別為： 第18頁，共73頁，2022年，5月20日，13點27分，星期二指數(shù)函數(shù)對公式線性化，兩邊取對數(shù)得令則第19頁，共73頁，2022年，5月20日，13點27分

3、，星期二指數(shù)函數(shù)第20頁，共73頁，2022年，5月20日，13點27分，星期二冪函數(shù)式中 為實數(shù)。對公式線性化，兩邊取對數(shù)，得令 ， ， 得函數(shù)形式為：第21頁，共73頁，2022年，5月20日，13點27分，星期二冪函數(shù)變量代換可在雙對數(shù)坐標上得直線， 第22頁，共73頁，2022年，5月20日，13點27分，星期二二、網(wǎng)絡(圖)的基本概念第23頁，共73頁，2022年，5月20日，13點27分，星期二中國教科網(wǎng)第24頁，共73頁，2022年，5月20日，13點27分，星期二網(wǎng)絡(圖)的基本概念節(jié)點通常用來表示系統(tǒng)中的部件；邊通常用來表示系統(tǒng)中部件之間的關(guān)系。網(wǎng)絡(圖)就是由節(jié)點與節(jié)點之間

4、的關(guān)系構(gòu)成的一張圖。第25頁，共73頁，2022年，5月20日，13點27分，星期二中國教科網(wǎng)拓撲結(jié)構(gòu)第26頁，共73頁，2022年，5月20日，13點27分，星期二網(wǎng)絡（圖）的基本概念關(guān)聯(lián)與鄰接度、平均度節(jié)點的度分布最短路徑與平均路徑長度群系數(shù)第27頁，共73頁，2022年，5月20日，13點27分，星期二網(wǎng)絡(圖)的基本概念aedcb第28頁，共73頁，2022年，5月20日，13點27分，星期二有向圖、無向圖、不連通圖第29頁，共73頁，2022年，5月20日，13點27分，星期二網(wǎng)絡(圖)的基本概念節(jié)點的度分布是指網(wǎng)絡（圖）中度為 的節(jié)點的概率 隨節(jié)點度 的變化規(guī)律。第30頁，共73頁

5、，2022年，5月20日，13點27分，星期二網(wǎng)絡(圖)的基本概念最短路徑就是從指定始點到指定終點的所有路徑中總權(quán)最小的一條路經(jīng)。平均路徑長度是指所有點對之間的最短路徑的算術(shù)平均值。第31頁，共73頁，2022年，5月20日，13點27分，星期二網(wǎng)絡(圖)的基本概念集群系數(shù)(Clustering coefficient)反映網(wǎng)絡的群集程度，定義為網(wǎng)絡的平均度與網(wǎng)絡規(guī)模之比。第32頁，共73頁，2022年，5月20日，13點27分，星期二22 77 55553311網(wǎng)絡(圖)的基本概念第33頁，共73頁，2022年，5月20日，13點27分，星期二節(jié)點1到7之間的最短路13，平均路徑長度5.47

6、，平均度為3.4，集群系數(shù)為0.48。網(wǎng)絡(圖)的基本概念第34頁，共73頁，2022年，5月20日，13點27分，星期二三、規(guī)則圖和隨機圖規(guī)則圖的特征如果系統(tǒng)中節(jié)點及其與邊的關(guān)系是固定的，每個節(jié)點都有相同的度數(shù)，就可以用規(guī)則圖來表示這個系統(tǒng)。隨機圖的特征如果系統(tǒng)中節(jié)點及其與邊的關(guān)系不確定，就只能用隨機圖來表示這個系統(tǒng)。第35頁，共73頁，2022年，5月20日，13點27分，星期二規(guī)則圖的特征平均度為3。第36頁，共73頁，2022年，5月20日，13點27分，星期二隨機圖的特征節(jié)點確定，但邊以概率 任意連接。節(jié)點不確定，點邊關(guān)系也不確定。第37頁，共73頁，2022年，5月20日，13點2

7、7分，星期二隨機圖節(jié)點19，邊43平均度為2.42，集群系數(shù)為0.13。第38頁，共73頁，2022年，5月20日，13點27分，星期二隨機圖節(jié)點42，邊118平均度為5.62，集群系數(shù)為0.133。第39頁，共73頁，2022年，5月20日，13點27分，星期二四、Scale-free網(wǎng)絡第40頁，共73頁，2022年，5月20日，13點27分，星期二目錄早期網(wǎng)絡模型無標度Scale-free網(wǎng)絡BA模型第41頁，共73頁，2022年，5月20日，13點27分，星期二早期網(wǎng)絡模型ER模型小世界模型第42頁，共73頁，2022年，5月20日，13點27分，星期二ER模型Erds和Rnyi （E

8、R）最早提出隨機網(wǎng)絡模型并對模型進行了深入研究，他們是用概率統(tǒng)計方法研究隨機圖統(tǒng)計特性的創(chuàng)始人。在模型開始階段給定N個節(jié)點，沒有邊，以概率p用邊連接任意一對節(jié)點，用這樣的方法產(chǎn)生一隨機網(wǎng)絡。第43頁，共73頁，2022年，5月20日，13點27分，星期二第44頁，共73頁，2022年，5月20日，13點27分，星期二ER模型Erds和Rnyi（1959）首先研究了在隨機網(wǎng)絡中最大和最小度的分布，Bollobs(1981)隨后得到了所有度分布的形式，推導出度數(shù)為k的節(jié)點數(shù)遵從平均值為 的泊松分布，即 第45頁，共73頁，2022年，5月20日，13點27分，星期二Connect with pro

9、bability pp=1/6 N=10 k 1.5Poisson distribution第46頁，共73頁，2022年，5月20日，13點27分，星期二小世界模型為了描述從一個局部有序系統(tǒng)到一個隨機網(wǎng)絡的轉(zhuǎn)移過程，Watts和 Strogatz（WS）提出了一個新模型，通常稱為小世界網(wǎng)絡模型。WS模型始于一具有N個節(jié)點的一維網(wǎng)絡，網(wǎng)絡的節(jié)點與其最近的鄰接點和次鄰接點相連接，然后每條邊以概率p重新連接。約束條件為節(jié)點間無重邊，無自環(huán)。第47頁，共73頁，2022年，5月20日，13點27分，星期二C(p) : clustering coeff. L(p) : average path len

10、gthP(k)=0.1 p(k)=0.3第48頁，共73頁，2022年，5月20日，13點27分，星期二小世界模型當p等于0時，對應的網(wǎng)絡規(guī)則圖。兩個節(jié)點間的平均距離線性地隨N增長而增長，集群系數(shù)大。當p等于1時，系統(tǒng)變?yōu)殡S機圖。 對數(shù)地隨N增長而增長，且集群系數(shù)隨N減少而減少。在p等于（0，1）區(qū)間任意值時，模型顯示出小世界特性，約等于隨機圖的值，網(wǎng)絡具有高度集群性。第49頁，共73頁，2022年，5月20日，13點27分，星期二復雜網(wǎng)絡都具有分布于平均值兩邊的度分布曲線嗎？第50頁，共73頁，2022年，5月20日，13點27分，星期二無標度(Scale-free)網(wǎng)絡Scale-free

11、網(wǎng)絡的發(fā)現(xiàn)Scale-free網(wǎng)絡的特性第51頁，共73頁，2022年，5月20日，13點27分，星期二Scale-free)網(wǎng)絡的發(fā)現(xiàn)信息交換網(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)絡、蛋白質(zhì)折疊）第52頁，共73頁，2022年，5月20日，13點27分，星期二第53頁，共73頁，2022年，5月20日，13點27分，星期二第54頁，共73頁，2022年，5月20日，13點27分，星期二Scale-free網(wǎng)絡的特性度分布呈冪率分布中樞節(jié)點出現(xiàn)穩(wěn)健性脆弱性第55頁，共73頁，2022年，5月20日

12、，13點27分，星期二第56頁，共73頁，2022年，5月20日，13點27分，星期二第57頁，共73頁，2022年，5月20日，13點27分，星期二無標度網(wǎng)絡與隨機圖特性比較第58頁，共73頁，2022年，5月20日，13點27分，星期二無標度（Scale-free）網(wǎng)絡無標度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，現(xiàn)實網(wǎng)絡的無標度特性源于眾多網(wǎng)絡所共有的兩種生成機制： （）網(wǎng)絡通過增添新節(jié)點而連續(xù)擴張； （）新節(jié)點擇優(yōu)連接到具有大量連接的節(jié)點上。第59頁，共73頁，2022年，5月20日，13點27分，星期二BA模型增長和擇優(yōu)連接這兩種要素激

13、勵了BarabsiAlbert模型的提出，該模型首次導出度分布按冪函數(shù)規(guī)律變化的網(wǎng)絡。模型的算法如下：（1）增長：開始于較少的節(jié)點數(shù)量（m0），在每個時間間隔增添一個具有m（m0）條邊的新節(jié)點，連接這個新節(jié)點到m個不同的已經(jīng)存在于系統(tǒng)中的節(jié)點上。（2）擇優(yōu)連接：在選擇新節(jié)點的連接點時，假設新節(jié)點連接到節(jié)點i的概率取決于節(jié)點i的度數(shù)即第60頁，共73頁，2022年，5月20日，13點27分，星期二經(jīng)過t時間間隔后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點，mt條邊的網(wǎng)絡。數(shù)量模擬表明具有k條邊的節(jié)點的概率服從指數(shù)為r=3的冪指數(shù)分布。第61頁，共73頁，2022年，5月20日，13點27分，星期二

14、P(k) k-3A.-L.Barabsi, R. Albert, Science 286, 509 (1999)第62頁，共73頁，2022年，5月20日，13點27分，星期二BA模型（a)Barabsi-Albert模擬的度分布。（b）不同系統(tǒng)規(guī)模下的 。 第63頁，共73頁，2022年，5月20日，13點27分，星期二BA模型設節(jié)點 i 的度 滿足動態(tài)方程：分母求和是對系統(tǒng)中除新進入系統(tǒng)的節(jié)點外的所有節(jié)點進行的 ，則第64頁，共73頁，2022年，5月20日，13點27分，星期二BA模型當t足夠大時，有解微分方程，有第65頁，共73頁，2022年，5月20日，13點27分，星期二由初始條件

15、得解為 式中可給出度小于k的節(jié)點的概率 第66頁，共73頁，2022年，5月20日，13點27分，星期二設在相同的時間間隔，添加節(jié)點到網(wǎng)絡 中， 值具有常數(shù)概率密度 代入前式t趨于無窮時度分布 式中第67頁，共73頁，2022年，5月20日，13點27分，星期二模型的度分布是與時間無關(guān)的漸進分布且與系統(tǒng)規(guī)模無關(guān)。 冪律度分布的系數(shù)與 成正比 。無標度模型的動態(tài)特性可以用各種分析方法給出 ： 連續(xù)域理論 主方程法 變化率方程法 第68頁，共73頁，2022年，5月20日，13點27分，星期二Baralsi-Albert模型的限制條件 保持了網(wǎng)絡的增長特性，不考慮擇優(yōu)連接，網(wǎng)絡度分布呈指數(shù)衰減。

16、消除了增長過程，只考慮擇優(yōu)連接，絡度分布圍繞其均值為一高斯分布。第69頁，共73頁，2022年，5月20日，13點27分，星期二Baralsi-Albert模型擴展研究初始吸引度非線性擇優(yōu)連接擇優(yōu)連接的更迭機理 增長制約條件及增長方式局部相互作用適應度模型第70頁，共73頁，2022年，5月20日，13點27分，星期二五、常用軟件SasMatlabPajekOriginNetdrawWaxmanGt-itmTiers BriteInetPlarg第71頁，共73頁，2022年，5月20日，13點27分，星期二六、主要參考文獻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. Jeo