復雜網(wǎng)絡(luò)的無標度特性課件

目錄概率統(tǒng)計預備知識網(wǎng)絡(luò)(圖)的基本概念規(guī)則圖和隨機網(wǎng)Scale-free網(wǎng)絡(luò)常用軟件參考文獻目錄1一、概率統(tǒng)計預備知識一、概率統(tǒng)計預備知識2目錄隨機變量與分布函數(shù)（離散、連續(xù)）隨機變量的數(shù)字特征（數(shù)學期望、方差）泊松分布冪函數(shù)指數(shù)函數(shù)目錄隨機變量與分布函數(shù)（離散、連續(xù)）3隨機變量與分布函數(shù)對某個隨機試驗，如果每次試驗的結(jié)果可以用一個數(shù)X來表示，而且對任何實數(shù)k，X<x有著確定的概率，則稱X是隨機變量。隨機變量X的值小于實數(shù)k的概率P(X<x)是x的函數(shù)，記作F(k)=P(X<x),函數(shù)F(x)叫做隨機變量X的分布函數(shù)。隨機變量與分布函數(shù)對某個隨機試驗，如果每次試驗的結(jié)果可以4離散型分布若隨機變量X只取有限個或可數(shù)個孤立的值，并且對應(yīng)這些值有確定的概率，即，則稱X是離散隨機變量（或X是離散分布的），稱為的概率分布，它滿足下列條件：離散型分布若隨機變量X只取有限個或可數(shù)個孤立的值5連續(xù)型分布若存在一個非負函數(shù)，使隨機變量X的分布函數(shù)可以表示為則X稱為連續(xù)隨機變量（或X是連續(xù)分布的），稱為隨機變量X的概率密度。

連續(xù)型分布若存在一個非負函數(shù)，使隨機變量X的分布6的性質(zhì)的性質(zhì)7隨機變量的數(shù)字特征隨機變量的數(shù)學期望定義1設(shè)x是離散型隨機變量，它的概率函數(shù)是隨機變量的數(shù)字特征隨機變量的數(shù)學期望8隨機變量的數(shù)學期望，反映了隨機變量取值的平均水平，即均值，是隨機變量的算術(shù)平均。

隨機變量的數(shù)學期望，反映了隨機變量取值的平均水平，即均值，是9方差為隨機變量的方差。方差是刻劃隨機變量取值離差程度的一個數(shù)。X的方差的算術(shù)平方根稱為標準差(或均方差）

方差為隨機變量的方差。方差是刻劃隨機變量取值離差程度的10若X是離散型隨機變量，則方差為：若X是離散型隨機變量，則方差為：11泊松定理設(shè)隨機變量Xn(n=0，1，2，…)服從二項分布，其分布律為其中設(shè)為常數(shù)則泊松定理設(shè)隨機變量Xn(n=0，1，2，…)服從二項分12泊松分布

設(shè)隨機變量X所有可能取的值為0，1，2，…，而取各個可能值的概率為：

若>0是常數(shù)，則稱變量X服從參數(shù)為泊松分布，記為

泊松分布設(shè)隨機變量X所有可能取的值為0，1，2，…，而取13<k><k>14于是，x的數(shù)學期望為：即于是，x的數(shù)學期望為：即15復雜網(wǎng)絡(luò)的無標度特性課件16所以，X的方差和均方差分別為：

所以，X的方差和均方差分別為：17指數(shù)函數(shù)對公式線性化，兩邊取對數(shù)得令則指數(shù)函數(shù)對公式線性化，兩邊取對數(shù)得18指數(shù)函數(shù)指數(shù)函數(shù)19冪函數(shù)式中為實數(shù)。對公式線性化，兩邊取對數(shù)，得令，，得函數(shù)形式為：冪函數(shù)式中為實數(shù)。令，20冪函數(shù)變量代換可在雙對數(shù)坐標上得直線，

冪函數(shù)變量代換可在雙對數(shù)坐標上得直線，21二、網(wǎng)絡(luò)(圖)的基本概念二、網(wǎng)絡(luò)(圖)的基本概念22中國教科網(wǎng)中國教科網(wǎng)23網(wǎng)絡(luò)(圖)的基本概念節(jié)點通常用來表示系統(tǒng)中的部件；邊通常用來表示系統(tǒng)中部件之間的關(guān)系。網(wǎng)絡(luò)(圖)就是由節(jié)點與節(jié)點之間的關(guān)系構(gòu)成的一張圖。網(wǎng)絡(luò)(圖)的基本概念節(jié)點通常用來表示系統(tǒng)中的部件；24中國教科網(wǎng)拓撲結(jié)構(gòu)中國教科網(wǎng)拓撲結(jié)構(gòu)25網(wǎng)絡(luò)（圖）的基本概念關(guān)聯(lián)與鄰接度、平均度節(jié)點的度分布最短路徑與平均路徑長度群系數(shù)網(wǎng)絡(luò)（圖）的基本概念關(guān)聯(lián)與鄰接26網(wǎng)絡(luò)(圖)的基本概念aedcb網(wǎng)絡(luò)(圖)的基本概念aedcb27有向圖、無向圖、不連通圖有向圖、無向圖、不連通圖28網(wǎng)絡(luò)(圖)的基本概念節(jié)點的度分布是指網(wǎng)絡(luò)（圖）中度為的節(jié)點的概率隨節(jié)點度的變化規(guī)律。網(wǎng)絡(luò)(圖)的基本概念節(jié)點的度分布是指網(wǎng)絡(luò)（圖）中度為的節(jié)29網(wǎng)絡(luò)(圖)的基本概念最短路徑就是從指定始點到指定終點的所有路徑中總權(quán)最小的一條路經(jīng)。平均路徑長度是指所有點對之間的最短路徑的算術(shù)平均值。網(wǎng)絡(luò)(圖)的基本概念最短路徑就是從指定始點到指定終點的所有路30網(wǎng)絡(luò)(圖)的基本概念集群系數(shù)(Clusteringcoefficient)反映網(wǎng)絡(luò)的群集程度，定義為網(wǎng)絡(luò)的平均度與網(wǎng)絡(luò)規(guī)模之比。網(wǎng)絡(luò)(圖)的基本概念集群系數(shù)(Clusteringcoef312277

55553311網(wǎng)絡(luò)(圖)的基本概念227755553311網(wǎng)絡(luò)(圖)的基本概念32節(jié)點1到7之間的最短路13，平均路徑長度5.47，平均度為3.4，集群系數(shù)為0.48。網(wǎng)絡(luò)(圖)的基本概念節(jié)點1到7之間的最短路13，平均路徑長度5.47，網(wǎng)絡(luò)(圖)33三、規(guī)則圖和隨機圖規(guī)則圖的特征如果系統(tǒng)中節(jié)點及其與邊的關(guān)系是固定的，每個節(jié)點都有相同的度數(shù)，就可以用規(guī)則圖來表示這個系統(tǒng)。隨機圖的特征如果系統(tǒng)中節(jié)點及其與邊的關(guān)系不確定，就只能用隨機圖來表示這個系統(tǒng)。三、規(guī)則圖和隨機圖規(guī)則圖的特征34規(guī)則圖的特征平均度為3。規(guī)則圖的特征平均度為3。35隨機圖的特征節(jié)點確定，但邊以概率任意連接。節(jié)點不確定，點邊關(guān)系也不確定。隨機圖的特征節(jié)點確定，但邊以概率任意連接。36隨機圖——節(jié)點19，邊43平均度為2.42，集群系數(shù)為0.13。隨機圖——節(jié)點19，邊43平均度為2.42，集群系數(shù)為0.137隨機圖——節(jié)點42，邊118平均度為5.62，集群系數(shù)為0.133。隨機圖——節(jié)點42，邊118平均度為5.62，集群系數(shù)為0.38四、Scale-free網(wǎng)絡(luò)四、Scale-free網(wǎng)絡(luò)39目錄早期網(wǎng)絡(luò)模型無標度Scale-free網(wǎng)絡(luò)BA模型目錄早期網(wǎng)絡(luò)模型40早期網(wǎng)絡(luò)模型ER模型小世界模型早期網(wǎng)絡(luò)模型ER模型41ER模型Erd?s和Rényi（ER）最早提出隨機網(wǎng)絡(luò)模型并對模型進行了深入研究，他們是用概率統(tǒng)計方法研究隨機圖統(tǒng)計特性的創(chuàng)始人。在模型開始階段給定N個節(jié)點，沒有邊，以概率p用邊連接任意一對節(jié)點，用這樣的方法產(chǎn)生一隨機網(wǎng)絡(luò)。ER模型Erd?s和Rényi（ER）最早提出隨機網(wǎng)絡(luò)模型42復雜網(wǎng)絡(luò)的無標度特性課件43ER模型Erd?s和Rényi（1959）首先研究了在隨機網(wǎng)絡(luò)中最大和最小度的分布，Bollobás(1981)隨后得到了所有度分布的形式，推導出度數(shù)為k的節(jié)點數(shù)遵從平均值為的泊松分布，即ER模型Erd?s和Rényi（1959）首先研究了在隨機網(wǎng)44Connectwithprobabilitypp=1/6N=10k~1.5PoissondistributionConnectwithprobabilitypp=1/45小世界模型為了描述從一個局部有序系統(tǒng)到一個隨機網(wǎng)絡(luò)的轉(zhuǎn)移過程，Watts和Strogatz（WS）提出了一個新模型，通常稱為小世界網(wǎng)絡(luò)模型。WS模型始于一具有N個節(jié)點的一維網(wǎng)絡(luò)，網(wǎng)絡(luò)的節(jié)點與其最近的鄰接點和次鄰接點相連接，然后每條邊以概率p重新連接。約束條件為節(jié)點間無重邊，無自環(huán)。小世界模型為了描述從一個局部有序系統(tǒng)到一個隨機網(wǎng)絡(luò)的轉(zhuǎn)移過程46C(p):clusteringcoeff.L(p):averagepathlengthP(k)=0.1p(k)=0.3C(p):clusteringcoeff.47小世界模型當p等于0時，對應(yīng)的網(wǎng)絡(luò)規(guī)則圖。兩個節(jié)點間的平均距離<L>線性地隨N增長而增長，集群系數(shù)大。當p等于1時，系統(tǒng)變?yōu)殡S機圖。<L>對數(shù)地隨N增長而增長，且集群系數(shù)隨N減少而減少。在p等于（0，1）區(qū)間任意值時，模型顯示出小世界特性，<L>約等于隨機圖的值，網(wǎng)絡(luò)具有高度集群性。小世界模型當p等于0時，對應(yīng)的網(wǎng)絡(luò)規(guī)則圖。兩個節(jié)點間的平均距48復雜網(wǎng)絡(luò)都具有分布于平均值兩邊的度分布曲線嗎？復雜網(wǎng)絡(luò)都具有分布于平均值兩邊的度分布曲線嗎？49無標度(Scale-free)網(wǎng)絡(luò)Scale-free網(wǎng)絡(luò)的發(fā)現(xiàn)Scale-free網(wǎng)絡(luò)的特性無標度(Scale-free)網(wǎng)絡(luò)Scale-free網(wǎng)絡(luò)的50Scale-free)網(wǎng)絡(luò)的發(fā)現(xiàn)信息交換網(wǎng)（萬維網(wǎng)、國際互聯(lián)網(wǎng)、電話網(wǎng)、電力網(wǎng)）社會網(wǎng)絡(luò)（電影演員合作網(wǎng)、科研合作圖、引文網(wǎng)、人類性接觸網(wǎng)、語言學網(wǎng)）生物網(wǎng)絡(luò)（細胞網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)、蛋白質(zhì)折疊）Scale-free)網(wǎng)絡(luò)的發(fā)現(xiàn)信息交換網(wǎng)（萬維網(wǎng)、國際互聯(lián)51復雜網(wǎng)絡(luò)的無標度特性課件52復雜網(wǎng)絡(luò)的無標度特性課件53Scale-free網(wǎng)絡(luò)的特性度分布呈冪率分布中樞節(jié)點出現(xiàn)穩(wěn)健性脆弱性Scale-free網(wǎng)絡(luò)的特性度分布呈冪率分布54復雜網(wǎng)絡(luò)的無標度特性課件55復雜網(wǎng)絡(luò)的無標度特性課件56無標度網(wǎng)絡(luò)與隨機圖特性比較無標度網(wǎng)絡(luò)與隨機圖特性比較57無標度（Scale-free）網(wǎng)絡(luò)無標度模型由Albert-LászlóBarabási和RékaAlbert在1999年首先提出，現(xiàn)實網(wǎng)絡(luò)的無標度特性源于眾多網(wǎng)絡(luò)所共有的兩種生成機制：（?。┚W(wǎng)絡(luò)通過增添新節(jié)點而連續(xù)擴張；（ⅱ）新節(jié)點擇優(yōu)連接到具有大量連接的節(jié)點上。無標度（Scale-free）網(wǎng)絡(luò)無標度模型由Albert-58BA模型增長和擇優(yōu)連接這兩種要素激勵了Barabási－Albert模型的提出，該模型首次導出度分布按冪函數(shù)規(guī)律變化的網(wǎng)絡(luò)。模型的算法如下：（1）增長：開始于較少的節(jié)點數(shù)量（m0），在每個時間間隔增添一個具有m（≤m0）條邊的新節(jié)點，連接這個新節(jié)點到m個不同的已經(jīng)存在于系統(tǒng)中的節(jié)點上。（2）擇優(yōu)連接：在選擇新節(jié)點的連接點時，假設(shè)新節(jié)點連接到節(jié)點i的概率π取決于節(jié)點i的度數(shù)即BA模型增長和擇優(yōu)連接這兩種要素激勵了Barabási－Al59經(jīng)過t時間間隔后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點，mt條邊的網(wǎng)絡(luò)。數(shù)量模擬表明具有k條邊的節(jié)點的概率服從指數(shù)為r=3的冪指數(shù)分布。經(jīng)過t時間間隔后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點，m60P(k)~k-3A.-L.Barabási,R.Albert,Science286,509(1999)P(k)~k-3A.-L.Barabási,R.Alb61BA模型（a)Barabási-Albert模擬的度分布。（b）不同系統(tǒng)規(guī)模下的。

BA模型（a)Barabási-Albert模擬的度分布。62BA模型設(shè)節(jié)點i的度滿足動態(tài)方程：分母求和是對系統(tǒng)中除新進入系統(tǒng)的節(jié)點外的所有節(jié)點進行的，則BA模型設(shè)節(jié)點i的度滿足動態(tài)方程：63BA模型當t足夠大時，有解微分方程，有BA模型當t足夠大時，有64由初始條件得解為式中可給出度小于k的節(jié)點的概率

由初始條件得解為65設(shè)在相同的時間間隔，添加節(jié)點到網(wǎng)絡(luò)中，值具有常數(shù)概率密度

代入前式t趨于無窮時度分布

式中設(shè)在相同的時間間隔，添加節(jié)點到網(wǎng)絡(luò)中，值具有常數(shù)66模型的度分布是與時間無關(guān)的漸進分布且與系統(tǒng)規(guī)模無關(guān)。冪律度分布的系數(shù)與成正比。無標度模型的動態(tài)特性可以用各種分析方法給出：連續(xù)域理論主方程法變化率方程法模型的度分布是與時間無關(guān)的漸進分布且與系統(tǒng)規(guī)模無關(guān)。67Baralási-Albert模型的限制條件保持了網(wǎng)絡(luò)的增長特性，不考慮擇優(yōu)連接，網(wǎng)絡(luò)度分布呈指數(shù)衰減。消除了增長過程，只考慮擇優(yōu)連接，絡(luò)度分布圍繞其均值為一高斯分布。Baralási-Albert模型的限制條件保持了網(wǎng)絡(luò)的增68Baralási-Albert模型擴展研究初始吸引度非線性擇優(yōu)連接擇優(yōu)連接的更迭機理增長制約條件及增長方式局部相互作用適應(yīng)度模型Baralási-Albert模型擴展研究初始吸引度69五、常用軟件SasMatlabPajekOriginNetdrawWaxmanGt-itmTiersBriteInetPlarg五、常用軟件SasWaxman70六、主要參考文獻Albert,R.,H.Jeong,andA.-L.Barabási,DiameteroftheWorld-Wide-Web,1999,Nature(London)401,130.Barabási,A.-L.,andR.Albert,Emergenceofscalinginrandomnetworks,1999,Science286,509.Barabási,A.-L.,R.Albert,andH.Jeong,Mean-fieldtheoryforscale-freerandomnetworks,1999,PhysicaA272,173.Albert,R.,andA.-L.Barabási,statisticalMechanicsofcomplexnetwork,2002,Rev.Mod.Phys.Vol.74,No.1,47-97.六、主要參考文獻Albert,R.,H.Jeong,71精品課件！精品課件！72精品課件！精品課件！73謝謝！謝謝！74目錄概率統(tǒng)計預備知識網(wǎng)絡(luò)(圖)的基本概念規(guī)則圖和隨機網(wǎng)Scale-free網(wǎng)絡(luò)常用軟件參考文獻目錄75一、概率統(tǒng)計預備知識一、概率統(tǒng)計預備知識76目錄隨機變量與分布函數(shù)（離散、連續(xù)）隨機變量的數(shù)字特征（數(shù)學期望、方差）泊松分布冪函數(shù)指數(shù)函數(shù)目錄隨機變量與分布函數(shù)（離散、連續(xù)）77隨機變量與分布函數(shù)對某個隨機試驗，如果每次試驗的結(jié)果可以用一個數(shù)X來表示，而且對任何實數(shù)k，X<x有著確定的概率，則稱X是隨機變量。隨機變量X的值小于實數(shù)k的概率P(X<x)是x的函數(shù)，記作F(k)=P(X<x),函數(shù)F(x)叫做隨機變量X的分布函數(shù)。隨機變量與分布函數(shù)對某個隨機試驗，如果每次試驗的結(jié)果可以78離散型分布若隨機變量X只取有限個或可數(shù)個孤立的值，并且對應(yīng)這些值有確定的概率，即，則稱X是離散隨機變量（或X是離散分布的），稱為的概率分布，它滿足下列條件：離散型分布若隨機變量X只取有限個或可數(shù)個孤立的值79連續(xù)型分布若存在一個非負函數(shù)，使隨機變量X的分布函數(shù)可以表示為則X稱為連續(xù)隨機變量（或X是連續(xù)分布的），稱為隨機變量X的概率密度。

連續(xù)型分布若存在一個非負函數(shù)，使隨機變量X的分布80的性質(zhì)的性質(zhì)81隨機變量的數(shù)字特征隨機變量的數(shù)學期望定義1設(shè)x是離散型隨機變量，它的概率函數(shù)是隨機變量的數(shù)字特征隨機變量的數(shù)學期望82隨機變量的數(shù)學期望，反映了隨機變量取值的平均水平，即均值，是隨機變量的算術(shù)平均。

隨機變量的數(shù)學期望，反映了隨機變量取值的平均水平，即均值，是83方差為隨機變量的方差。方差是刻劃隨機變量取值離差程度的一個數(shù)。X的方差的算術(shù)平方根稱為標準差(或均方差）

方差為隨機變量的方差。方差是刻劃隨機變量取值離差程度的84若X是離散型隨機變量，則方差為：若X是離散型隨機變量，則方差為：85泊松定理設(shè)隨機變量Xn(n=0，1，2，…)服從二項分布，其分布律為其中設(shè)為常數(shù)則泊松定理設(shè)隨機變量Xn(n=0，1，2，…)服從二項分86泊松分布

設(shè)隨機變量X所有可能取的值為0，1，2，…，而取各個可能值的概率為：

若>0是常數(shù)，則稱變量X服從參數(shù)為泊松分布，記為

泊松分布設(shè)隨機變量X所有可能取的值為0，1，2，…，而取87<k><k>88于是，x的數(shù)學期望為：即于是，x的數(shù)學期望為：即89復雜網(wǎng)絡(luò)的無標度特性課件90所以，X的方差和均方差分別為：

所以，X的方差和均方差分別為：91指數(shù)函數(shù)對公式線性化，兩邊取對數(shù)得令則指數(shù)函數(shù)對公式線性化，兩邊取對數(shù)得92指數(shù)函數(shù)指數(shù)函數(shù)93冪函數(shù)式中為實數(shù)。對公式線性化，兩邊取對數(shù)，得令，，得函數(shù)形式為：冪函數(shù)式中為實數(shù)。令，94冪函數(shù)變量代換可在雙對數(shù)坐標上得直線，

冪函數(shù)變量代換可在雙對數(shù)坐標上得直線，95二、網(wǎng)絡(luò)(圖)的基本概念二、網(wǎng)絡(luò)(圖)的基本概念96中國教科網(wǎng)中國教科網(wǎng)97網(wǎng)絡(luò)(圖)的基本概念節(jié)點通常用來表示系統(tǒng)中的部件；邊通常用來表示系統(tǒng)中部件之間的關(guān)系。網(wǎng)絡(luò)(圖)就是由節(jié)點與節(jié)點之間的關(guān)系構(gòu)成的一張圖。網(wǎng)絡(luò)(圖)的基本概念節(jié)點通常用來表示系統(tǒng)中的部件；98中國教科網(wǎng)拓撲結(jié)構(gòu)中國教科網(wǎng)拓撲結(jié)構(gòu)99網(wǎng)絡(luò)（圖）的基本概念關(guān)聯(lián)與鄰接度、平均度節(jié)點的度分布最短路徑與平均路徑長度群系數(shù)網(wǎng)絡(luò)（圖）的基本概念關(guān)聯(lián)與鄰接100網(wǎng)絡(luò)(圖)的基本概念aedcb網(wǎng)絡(luò)(圖)的基本概念aedcb101有向圖、無向圖、不連通圖有向圖、無向圖、不連通圖102網(wǎng)絡(luò)(圖)的基本概念節(jié)點的度分布是指網(wǎng)絡(luò)（圖）中度為的節(jié)點的概率隨節(jié)點度的變化規(guī)律。網(wǎng)絡(luò)(圖)的基本概念節(jié)點的度分布是指網(wǎng)絡(luò)（圖）中度為的節(jié)103網(wǎng)絡(luò)(圖)的基本概念最短路徑就是從指定始點到指定終點的所有路徑中總權(quán)最小的一條路經(jīng)。平均路徑長度是指所有點對之間的最短路徑的算術(shù)平均值。網(wǎng)絡(luò)(圖)的基本概念最短路徑就是從指定始點到指定終點的所有路104網(wǎng)絡(luò)(圖)的基本概念集群系數(shù)(Clusteringcoefficient)反映網(wǎng)絡(luò)的群集程度，定義為網(wǎng)絡(luò)的平均度與網(wǎng)絡(luò)規(guī)模之比。網(wǎng)絡(luò)(圖)的基本概念集群系數(shù)(Clusteringcoef1052277

55553311網(wǎng)絡(luò)(圖)的基本概念227755553311網(wǎng)絡(luò)(圖)的基本概念106節(jié)點1到7之間的最短路13，平均路徑長度5.47，平均度為3.4，集群系數(shù)為0.48。網(wǎng)絡(luò)(圖)的基本概念節(jié)點1到7之間的最短路13，平均路徑長度5.47，網(wǎng)絡(luò)(圖)107三、規(guī)則圖和隨機圖規(guī)則圖的特征如果系統(tǒng)中節(jié)點及其與邊的關(guān)系是固定的，每個節(jié)點都有相同的度數(shù)，就可以用規(guī)則圖來表示這個系統(tǒng)。隨機圖的特征如果系統(tǒng)中節(jié)點及其與邊的關(guān)系不確定，就只能用隨機圖來表示這個系統(tǒng)。三、規(guī)則圖和隨機圖規(guī)則圖的特征108規(guī)則圖的特征平均度為3。規(guī)則圖的特征平均度為3。109隨機圖的特征節(jié)點確定，但邊以概率任意連接。節(jié)點不確定，點邊關(guān)系也不確定。隨機圖的特征節(jié)點確定，但邊以概率任意連接。110隨機圖——節(jié)點19，邊43平均度為2.42，集群系數(shù)為0.13。隨機圖——節(jié)點19，邊43平均度為2.42，集群系數(shù)為0.1111隨機圖——節(jié)點42，邊118平均度為5.62，集群系數(shù)為0.133。隨機圖——節(jié)點42，邊118平均度為5.62，集群系數(shù)為0.112四、Scale-free網(wǎng)絡(luò)四、Scale-free網(wǎng)絡(luò)113目錄早期網(wǎng)絡(luò)模型無標度Scale-free網(wǎng)絡(luò)BA模型目錄早期網(wǎng)絡(luò)模型114早期網(wǎng)絡(luò)模型ER模型小世界模型早期網(wǎng)絡(luò)模型ER模型115ER模型Erd?s和Rényi（ER）最早提出隨機網(wǎng)絡(luò)模型并對模型進行了深入研究，他們是用概率統(tǒng)計方法研究隨機圖統(tǒng)計特性的創(chuàng)始人。在模型開始階段給定N個節(jié)點，沒有邊，以概率p用邊連接任意一對節(jié)點，用這樣的方法產(chǎn)生一隨機網(wǎng)絡(luò)。ER模型Erd?s和Rényi（ER）最早提出隨機網(wǎng)絡(luò)模型116復雜網(wǎng)絡(luò)的無標度特性課件117ER模型Erd?s和Rényi（1959）首先研究了在隨機網(wǎng)絡(luò)中最大和最小度的分布，Bollobás(1981)隨后得到了所有度分布的形式，推導出度數(shù)為k的節(jié)點數(shù)遵從平均值為的泊松分布，即ER模型Erd?s和Rényi（1959）首先研究了在隨機網(wǎng)118Connectwithprobabilitypp=1/6N=10k~1.5PoissondistributionConnectwithprobabilitypp=1/119小世界模型為了描述從一個局部有序系統(tǒng)到一個隨機網(wǎng)絡(luò)的轉(zhuǎn)移過程，Watts和Strogatz（WS）提出了一個新模型，通常稱為小世界網(wǎng)絡(luò)模型。WS模型始于一具有N個節(jié)點的一維網(wǎng)絡(luò)，網(wǎng)絡(luò)的節(jié)點與其最近的鄰接點和次鄰接點相連接，然后每條邊以概率p重新連接。約束條件為節(jié)點間無重邊，無自環(huán)。小世界模型為了描述從一個局部有序系統(tǒng)到一個隨機網(wǎng)絡(luò)的轉(zhuǎn)移過程120C(p):clusteringcoeff.L(p):averagepathlengthP(k)=0.1p(k)=0.3C(p):clusteringcoeff.121小世界模型當p等于0時，對應(yīng)的網(wǎng)絡(luò)規(guī)則圖。兩個節(jié)點間的平均距離<L>線性地隨N增長而增長，集群系數(shù)大。當p等于1時，系統(tǒng)變?yōu)殡S機圖。<L>對數(shù)地隨N增長而增長，且集群系數(shù)隨N減少而減少。在p等于（0，1）區(qū)間任意值時，模型顯示出小世界特性，<L>約等于隨機圖的值，網(wǎng)絡(luò)具有高度集群性。小世界模型當p等于0時，對應(yīng)的網(wǎng)絡(luò)規(guī)則圖。兩個節(jié)點間的平均距122復雜網(wǎng)絡(luò)都具有分布于平均值兩邊的度分布曲線嗎？復雜網(wǎng)絡(luò)都具有分布于平均值兩邊的度分布曲線嗎？123無標度(Scale-free)網(wǎng)絡(luò)Scale-free網(wǎng)絡(luò)的發(fā)現(xiàn)Scale-free網(wǎng)絡(luò)的特性無標度(Scale-free)網(wǎng)絡(luò)Scale-free網(wǎng)絡(luò)的124Scale-free)網(wǎng)絡(luò)的發(fā)現(xiàn)信息交換網(wǎng)（萬維網(wǎng)、國際互聯(lián)網(wǎng)、電話網(wǎng)、電力網(wǎng)）社會網(wǎng)絡(luò)（電影演員合作網(wǎng)、科研合作圖、引文網(wǎng)、人類性接觸網(wǎng)、語言學網(wǎng)）生物網(wǎng)絡(luò)（細胞網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)、蛋白質(zhì)折疊）Scale-free)網(wǎng)絡(luò)的發(fā)現(xiàn)信息交換網(wǎng)（萬維網(wǎng)、國際互聯(lián)125復雜網(wǎng)絡(luò)的無標度特性課件126復雜網(wǎng)絡(luò)的無標度特性課件127Scale-free網(wǎng)絡(luò)的特性度分布呈冪率分布中樞節(jié)點出現(xiàn)穩(wěn)健性脆弱性Scale-free網(wǎng)絡(luò)的特性度分布呈冪率分布128復雜網(wǎng)絡(luò)的無標度特性課件129復雜網(wǎng)絡(luò)的無標度特性課件130無標度網(wǎng)絡(luò)與隨機圖特性比較無標度網(wǎng)絡(luò)與隨機圖特性比較131無標度（Scale-free）網(wǎng)絡(luò)無標度模型由Albert-LászlóBarabási和RékaAlbert在1999年首先提出，現(xiàn)實網(wǎng)絡(luò)的無標度特性源于眾多網(wǎng)絡(luò)所共有的兩種生成機制：（?。┚W(wǎng)絡(luò)通過增添新節(jié)點而連續(xù)擴張；（ⅱ）新節(jié)點擇優(yōu)連接到具有大量連接的節(jié)點上。無標度（Scale-free）網(wǎng)絡(luò)無標度模型由Albert-132BA模型增長和擇優(yōu)連接這兩種要素激勵了Barabási－Albert模型的提出，該模型首次導出度分布按冪函數(shù)規(guī)律變化的網(wǎng)絡(luò)。模型的算法如下：（1）增長：開始于較少的節(jié)點數(shù)量（m0），在每個時間間隔增添一個具有m（≤m0）條邊的新節(jié)點，連接這個新節(jié)點到m個不同的已經(jīng)存在于系統(tǒng)中的節(jié)點上。（2）擇優(yōu)連接：在選擇新節(jié)點的連接點時，假設(shè)新節(jié)點連接到節(jié)點i的概率π取決于節(jié)點i的度數(shù)即BA模型增長和擇優(yōu)連接這兩種要素激勵了Barabási－Al133經(jīng)過t時間間隔后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點，mt條邊的網(wǎng)絡(luò)。數(shù)量模擬表明具有k條邊的節(jié)點的概率服從指數(shù)為r=3的冪指數(shù)分布。經(jīng)過t時間間隔后，該算法程序產(chǎn)生一具有N=t+m0個節(jié)點，m134P(k)~k-3A.-L.Barabási,R.Albert,Science286,509(1999)P(k)~k-3A.-L.Barabási,R.Alb135BA模型（a)Barabási-Albert模擬的度分布。（b）不同系統(tǒng)規(guī)模下的。

BA模型（a)Barabási-Albert模擬的度分布。136BA模型設(shè)節(jié)點i的度滿足動態(tài)方程：分母求和是對系統(tǒng)中除新進入系統(tǒng)的節(jié)點外的所有節(jié)點進行的，則BA模型設(shè)節(jié)點i的度滿足動態(tài)方程：137BA模型當t足夠大時，有