復(fù)雜網(wǎng)絡(luò)數(shù)學(xué)建模-課件

1、復(fù)雜網(wǎng)絡(luò)數(shù)學(xué)建模概述一、網(wǎng)絡(luò)圖的基本概念節(jié)點(diǎn)、邊關(guān)聯(lián)與鄰接度 k、平均度 節(jié)點(diǎn)的度分布p(k)最短路徑與平均路徑長(zhǎng)度 （Dijkstra算法）集聚系數(shù) Caedcb有向圖、無(wú)向圖、不連通圖節(jié)點(diǎn)的度分布是指網(wǎng)絡(luò)（圖）中度為 的節(jié)點(diǎn)的概率 隨節(jié)點(diǎn)度 的變化規(guī)律。兩點(diǎn)之間的最短路徑：從指定始點(diǎn)到指定終點(diǎn)的所有路徑中長(zhǎng)度最小的一條路徑。網(wǎng)絡(luò)平均路徑長(zhǎng)度：所有點(diǎn)對(duì)之間的最短路徑的算術(shù)平均值。22 77 55553311節(jié)點(diǎn)1到7之間的最短路13，平均路徑長(zhǎng)度5.47，平均度為3.4，集聚系數(shù)為0.48。二、早期網(wǎng)絡(luò)模型規(guī)則圖和隨機(jī)圖規(guī)則圖系統(tǒng)中節(jié)點(diǎn)及其與邊的關(guān)系是固定的，每個(gè)節(jié)點(diǎn)都有相同的度數(shù)。隨機(jī)圖平

2、均說(shuō)來(lái)系統(tǒng)中節(jié)點(diǎn)及其與邊的關(guān)系不確定。規(guī)則圖的特征平均度為3。隨機(jī)圖的特征節(jié)點(diǎn)確定，但邊以概率 任意連接。節(jié)點(diǎn)不確定，點(diǎn)邊關(guān)系也不確定。隨機(jī)圖節(jié)點(diǎn)19，邊43平均度為2.42，集聚系數(shù)為0.13。隨機(jī)圖節(jié)點(diǎn)42，邊118平均度為5.62，集聚系數(shù)為0.133。ER模型Erds和Rnyi （ER）最早提出隨機(jī)網(wǎng)絡(luò)模型并進(jìn)行了深入研究，他們是用概率統(tǒng)計(jì)方法研究隨機(jī)圖統(tǒng)計(jì)特性的創(chuàng)始人。給定N個(gè)節(jié)點(diǎn)，沒(méi)有邊，以概率p用邊連接任意一對(duì)節(jié)點(diǎn)，用這樣的方法產(chǎn)生一隨機(jī)網(wǎng)絡(luò)。ER模型節(jié)點(diǎn)的度分布：平均值為 的泊松分布 Connect with probability pp=1/6 N=10 k 1.5Poiss

3、on distribution三、復(fù)雜網(wǎng)絡(luò)模型小世界（small-world) 網(wǎng)絡(luò)模型無(wú)標(biāo)度 （scale-free)網(wǎng)絡(luò)模型小世界模型為了描述從一個(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)。C(p) : clustering coeff. L(p) : average path lengthP(k)=0.1 p(k)=0.3當(dāng)p等于0時(shí)，對(duì)應(yīng)于規(guī)則圖。兩個(gè)節(jié)點(diǎn)間的平均距離線性

4、地隨N增長(zhǎng)而增長(zhǎng)，集聚系數(shù)大。當(dāng)p等于1時(shí)，系統(tǒng)變?yōu)殡S機(jī)圖。 對(duì)數(shù)地隨N增長(zhǎng)而增長(zhǎng)，且集聚系數(shù)隨N減少而減少。在p等于（0，1）區(qū)間任意值時(shí)，約等于隨機(jī)圖的值，網(wǎng)絡(luò)具有高度集聚性-小世界效應(yīng)。復(fù)雜網(wǎng)絡(luò)都具有分布于平均值兩邊的度分布曲線嗎？無(wú)標(biāo)度(Scale-free)網(wǎng)絡(luò)Scale-free網(wǎng)絡(luò)的發(fā)現(xiàn)Scale-free網(wǎng)絡(luò)的特性Scale-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)、人類(lèi)性接觸網(wǎng)、語(yǔ)言學(xué)網(wǎng)）生物網(wǎng)絡(luò)（細(xì)胞網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)、蛋白質(zhì)折疊）Scale-free網(wǎng)絡(luò)的特性度分布呈冪率分布中樞節(jié)點(diǎn)出現(xiàn)魯棒性脆弱性無(wú)標(biāo)度

5、網(wǎng)絡(luò)與隨機(jī)圖特性比較無(wú)標(biāo)度（Scale-free）網(wǎng)絡(luò)無(wú)標(biāo)度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，現(xiàn)實(shí)網(wǎng)絡(luò)的無(wú)標(biāo)度特性源于眾多網(wǎng)絡(luò)所共有的兩種生成機(jī)制： （）網(wǎng)絡(luò)通過(guò)增添新節(jié)點(diǎn)而連續(xù)擴(kuò)張； （）新節(jié)點(diǎn)擇優(yōu)連接到具有大量連接的節(jié)點(diǎn)上。BA模型增長(zhǎng)和擇優(yōu)連接這兩種要素激勵(lì)了BarabsiAlbert模型的提出，該模型首次導(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í)

6、，假設(shè)新節(jié)點(diǎn)連接到節(jié)點(diǎn)i的概率取決于節(jié)點(diǎn)i的度數(shù)即經(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ù)分布。P(k) k-3A.-L.Barabsi, R. Albert, Science 286, 509 (1999)BA模型（a)Barabsi-Albert模擬的度分布。（b）不同系統(tǒng)規(guī)模下的 。 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)行的 ，則BA模型當(dāng)t足夠大時(shí)，有解微分方程，有由初始條件得解為 式中可給出度小于k的節(jié)點(diǎn)的概率 設(shè)在相同的時(shí)間間隔，添加節(jié)點(diǎn)

7、到網(wǎng)絡(luò) 中， 值具有常數(shù)概率密度 代入前式t趨于無(wú)窮時(shí)度分布 式中模型的度分布是與時(shí)間無(wú)關(guān)的漸進(jìn)分布且與系統(tǒng)規(guī)模無(wú)關(guān)。 冪律度分布的系數(shù)與 成正比 。無(wú)標(biāo)度模型的動(dòng)態(tài)特性可以用各種分析方法給出 ： 平均場(chǎng)理論 主方程法 變化率方程法 Baralsi-Albert模型的限制條件 保持了網(wǎng)絡(luò)的增長(zhǎng)特性，不考慮擇優(yōu)連接，網(wǎng)絡(luò)度分布呈指數(shù)衰減。 消除了增長(zhǎng)過(guò)程，只考慮擇優(yōu)連接，絡(luò)度分布圍繞其均值為一高斯分布。BA認(rèn)為，這兩個(gè)條件缺一不可，否則不能出現(xiàn)冪率度分布。Baralsi-Albert模型擴(kuò)展研究初始吸引度非線性擇優(yōu)連接擇優(yōu)連接的更迭機(jī)理 增長(zhǎng)制約條件及增長(zhǎng)方式局部相互作用適應(yīng)度模型其他工作流驅(qū)動(dòng)

8、的復(fù)雜網(wǎng)絡(luò)模型（科大王文旭等）具有隨機(jī)響應(yīng)的動(dòng)態(tài)有向小世界模型（南航朱陳平等）六、主要參考文獻(xiàn)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, Mean-field theory for scale-free random networks, 1999, Physica A 272, 173. Albert, R., and A.-L. Barabsi, statistical Mechanics of complex network, 2002, Rev. Mo