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

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

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

隨機(jī)變量的數(shù)學(xué)期望，反映了隨機(jī)變量取值的平均水平，即均值，是9方差為隨機(jī)變量的方差。方差是刻劃隨機(jī)變量取值離差程度的一個(gè)數(shù)。X的方差的算術(shù)平方根稱為標(biāo)準(zhǔn)差(或均方差）

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

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

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

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

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

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

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

代入前式t趨于無(wú)窮時(shí)度分布

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

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

隨機(jī)變量的數(shù)學(xué)期望，反映了隨機(jī)變量取值的平均水平，即均值，是83方差為隨機(jī)變量的方差。方差是刻劃隨機(jī)變量取值離差程度的一個(gè)數(shù)。X的方差的算術(shù)平方根稱為標(biāo)準(zhǔn)差(或均方差）

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

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

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

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

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

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