復(fù)雜網(wǎng)絡(luò)課件

復(fù)雜網(wǎng)絡(luò)及其應(yīng)用研究新進展學(xué)生：學(xué)號：復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的含義：我國著名科學(xué)家錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)一個較嚴格的定義：具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的研究歷史：哥尼斯堡七橋——>隨機圖論——>小世界和無標(biāo)度網(wǎng)絡(luò)自組織：如果一個系統(tǒng)靠外部指令而形成組織，就是他組織；如果不存在外部指令，系統(tǒng)按照相互默契的某種規(guī)則，各盡其責(zé)而又協(xié)調(diào)地自動地形成有序結(jié)構(gòu)，就是自組織。自相似：一種形狀的每一部分在幾何上相似于整體，一般對分形而言。吸引子：相空間（可以表示出一個系統(tǒng)所有可能狀態(tài)的空間）中穩(wěn)定的不動點集。小世界：

無標(biāo)度：小世界網(wǎng)絡(luò)圖無標(biāo)度網(wǎng)絡(luò)圖網(wǎng)絡(luò)分類規(guī)則網(wǎng)絡(luò):規(guī)則網(wǎng)絡(luò)具有很強規(guī)則性，例如全連接網(wǎng)絡(luò)，環(huán)形，鏈形，星形網(wǎng)絡(luò)以及格點和分形圖等

隨機網(wǎng)絡(luò):隨機網(wǎng)絡(luò)是指按照某種明確的統(tǒng)計規(guī)律生成的網(wǎng)絡(luò)，與規(guī)則網(wǎng)絡(luò)相對應(yīng)，主要是經(jīng)典的隨機圖模型及其派生出來的相關(guān)模型

小世界網(wǎng)絡(luò):主要有WS改邊小世界網(wǎng)絡(luò)和NW加邊小世界網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)：BA無標(biāo)度網(wǎng)絡(luò)是第一個無標(biāo)度網(wǎng)絡(luò)。我們將主要討論此類網(wǎng)絡(luò)上的同步與傳播問題可導(dǎo)航網(wǎng)絡(luò)隨機圖隨機圖是與規(guī)則網(wǎng)絡(luò)相反的網(wǎng)絡(luò)，一個典型模型是Erdos和Renyi于40多年前開始研究的隨機圖模型。假設(shè)有大量的紐扣（N》1）散落在地上，并以相同的概率p給每對紐扣系上一根線。這樣就會得到一個有N個節(jié)點，約pN(N-1)/2條邊的ER隨機圖的實例。1998，Watts和Strogatz：WS小世界網(wǎng)絡(luò)WS小世界模型NW小世界模型C(p):平均聚集系數(shù)

L(p):平均最短路徑小世界網(wǎng)絡(luò)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機圖的過渡，Watts和Strogtz于1998年引入了一個小世界網(wǎng)絡(luò)模型，稱為WS小世界模型。其構(gòu)造算法如下：①從規(guī)則圖開始：考慮一個含有N個點的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個環(huán)，其中每個節(jié)點都與它左右相鄰的各K/2個節(jié)點相連，K是偶數(shù)。②隨機化重連：以概率p隨機地重連網(wǎng)絡(luò)中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網(wǎng)絡(luò)中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同節(jié)點之-間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。具有較短的平均路徑長度又具有較高的聚類系數(shù)的網(wǎng)絡(luò)就稱為小世界網(wǎng)絡(luò)。

Newman和Watts提出了NW小世界模型，用“隨機化加邊”取代WS小世界模型構(gòu)造中的“隨機化重連”。算法如下：①從規(guī)則圖開始：含有N個節(jié)點的最近鄰耦合網(wǎng)絡(luò)。②隨機化加邊：以概率P在隨機選取的一對節(jié)點之間加上一條邊。

NW小世界模型中，p=0對應(yīng)于原來的最近鄰耦合網(wǎng)絡(luò)，p=1對應(yīng)于全局耦合網(wǎng)絡(luò)。無標(biāo)度網(wǎng)絡(luò)模型

研究發(fā)現(xiàn)許多復(fù)雜網(wǎng)絡(luò)的連接度分布函數(shù)具有冪律形式，由于這類網(wǎng)絡(luò)的節(jié)點的連接度沒有明顯的特征長度，故稱為無標(biāo)度網(wǎng)絡(luò)。

Barabasi和Albert提出了一個無標(biāo)度網(wǎng)絡(luò)模型，稱為BA模型。該模型考慮到了實際網(wǎng)絡(luò)的兩個重要特性：①增長特性；②優(yōu)先連接特性?；谶@兩個特性，BA無標(biāo)度網(wǎng)絡(luò)模型構(gòu)造算法如下：①增長：從一個具有m0個節(jié)點的網(wǎng)絡(luò)開始，每次引入一個新的節(jié)點，并且連到m個已存在的節(jié)點上，這里。②優(yōu)先連接：一個新節(jié)點與一個已經(jīng)存在的節(jié)點i相連接的概率與節(jié)點i的度ki，節(jié)點j的度kj之間滿足如下關(guān)系：

冪律分布函數(shù)的無標(biāo)度性質(zhì)：考慮一個概率分布函數(shù)f(x)，如果對任意給定常數(shù)a，存在常數(shù)b使得函數(shù)f(x)滿足如下“無標(biāo)度條件”:f(ax)=bf(x)

那么必有(假定)

也就是說，冪律分布函數(shù)是唯一滿足“無標(biāo)度條件”的概率分布函數(shù)。復(fù)雜網(wǎng)絡(luò)應(yīng)用電力系統(tǒng)復(fù)雜網(wǎng)絡(luò)的應(yīng)用：電力系統(tǒng)復(fù)雜網(wǎng)絡(luò)受到隨意攻擊細胞復(fù)雜網(wǎng)絡(luò)的應(yīng)用：

肺部細胞形成一個復(fù)雜網(wǎng)絡(luò)因特網(wǎng)復(fù)雜網(wǎng)絡(luò)的應(yīng)用：

因特網(wǎng)形成的復(fù)雜網(wǎng)絡(luò)交通運輸復(fù)雜網(wǎng)絡(luò)的應(yīng)用：城市公共交通網(wǎng)道路交通網(wǎng)航空網(wǎng)復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特征度(degree)：節(jié)點i的度

ki

定義為與該節(jié)點連接的其他節(jié)點的數(shù)目。

★直觀上看，一個節(jié)點的度越大就意味著這個節(jié)點在某種意義上越“重要”（“能力大”）。

網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)中所有節(jié)點的度和的平均值，記作<k>。事實上，<k>=2q/p度分布函數(shù)p(k):隨機選定節(jié)點的度恰好為k的概率

節(jié)點的聚類系數(shù)（簇系數(shù)）：在簡單圖中，設(shè)節(jié)點v的鄰集為N(v),|N(v)|=ki，則節(jié)點v的聚類系數(shù)定義為這ki個節(jié)點之間存在邊數(shù)Ei與總的可能邊數(shù)ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)★節(jié)點v的鄰點間關(guān)系的密切程度

網(wǎng)絡(luò)的聚類系數(shù)C：所有節(jié)點i的聚類系數(shù)Ci的平均值。（0C1）

C=0網(wǎng)絡(luò)中所有節(jié)點都是孤立點

C=1網(wǎng)絡(luò)中任意節(jié)點間都有邊相連

★網(wǎng)絡(luò)節(jié)點間聯(lián)系的密切程度,體現(xiàn)網(wǎng)絡(luò)的凝聚力

★許多大規(guī)模的實際網(wǎng)絡(luò)都具有明顯的聚類效應(yīng)。事實上，在很多類型的網(wǎng)絡(luò)(如社會關(guān)系網(wǎng)絡(luò))中，你的朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于某個非零常數(shù)，即當(dāng)N→∞時，C=O(1)。這意味著這些實際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機的，而是在某種程度上具有類似于社會關(guān)系網(wǎng)絡(luò)中“物以類聚，人以群分”的特性。介數(shù)（Betweenness）★點介數(shù)：網(wǎng)絡(luò)中通過該節(jié)點的最短路徑的條數(shù)★

邊介數(shù)：網(wǎng)絡(luò)中通過該邊的最短路徑的條數(shù)★反映了節(jié)點或邊的作用和影響力。如果一對節(jié)點間共有B條不同的最短路徑，其中有b條經(jīng)過節(jié)點i，那么節(jié)點i對這對節(jié)點的介數(shù)的貢獻為b/B。把節(jié)點i對所有節(jié)點對的貢獻累加起來再除以節(jié)點對總數(shù)，就可得到節(jié)點i的介數(shù)。類似的，邊的介數(shù)定義為所有節(jié)點對的最短路徑中經(jīng)過該邊的數(shù)量比例?！锝閿?shù)越大，說明經(jīng)過該節(jié)點（邊）的最短路徑越多。在信息傳播過程中，通過該節(jié)點（邊）的信息量就越大，于是就越容易發(fā)生擁塞。

★研究表明，節(jié)點介數(shù)與度之間有很強的相關(guān)性，不同類型的網(wǎng)絡(luò)，其介數(shù)分布也大不一樣。網(wǎng)絡(luò)介數(shù)

★網(wǎng)絡(luò)點介數(shù)，網(wǎng)絡(luò)邊介數(shù)：所有節(jié)點（邊）的平均介數(shù)

★網(wǎng)絡(luò)介數(shù)說明了網(wǎng)絡(luò)的什么性質(zhì)

核數(shù)

★一個圖的k-核：反復(fù)去掉圖中度小于k的節(jié)點后，所剩余的子圖★若一個節(jié)點存在于k-核，而在(k+1)-核中被去掉，則此節(jié)點核數(shù)為k★節(jié)點核數(shù)中的最大值稱為網(wǎng)絡(luò)圖的核數(shù)★節(jié)點核數(shù)可以表明節(jié)點在核中的深度；即便一個節(jié)點的度數(shù)很高，它的核數(shù)也可能很小。例如：包含N個節(jié)點的星型網(wǎng)絡(luò)的中心節(jié)點的度數(shù)為N-1，但它的核數(shù)為1

復(fù)雜網(wǎng)絡(luò)的研究內(nèi)容1）復(fù)雜網(wǎng)絡(luò)模型典型的復(fù)雜網(wǎng)絡(luò)：隨機網(wǎng)、小世界網(wǎng)、無標(biāo)度網(wǎng)等；實際網(wǎng)絡(luò)及其分類。2）網(wǎng)絡(luò)的統(tǒng)計量及與網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)性度分布的定義和意義，聚集性、連通性的統(tǒng)計量及其實際意義等。3）復(fù)雜網(wǎng)絡(luò)性質(zhì)與結(jié)構(gòu)的關(guān)系同步性、魯棒性和穩(wěn)定性與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系。4）復(fù)雜網(wǎng)絡(luò)的動力學(xué)信息傳播動力學(xué)、網(wǎng)絡(luò)演化動力學(xué)、網(wǎng)絡(luò)混沌動力學(xué)。5）復(fù)雜網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu)社團結(jié)構(gòu)、層次結(jié)構(gòu)、節(jié)點分類結(jié)構(gòu)等。6）網(wǎng)絡(luò)控制關(guān)鍵節(jié)點控制、主參數(shù)控制和控制的穩(wěn)定性和有效性。7）復(fù)雜網(wǎng)絡(luò)建模機理建模、數(shù)據(jù)建模和實際系統(tǒng)的復(fù)雜網(wǎng)絡(luò)正向與逆向建模。8）復(fù)雜邏輯網(wǎng)絡(luò)邏輯與高階邏輯定義、分類、判定算法，高階邏輯的實際意義等等。影響復(fù)雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)性能的因素：密度：只要某個社區(qū)的密度超過閾值，停止該社區(qū)的聚合。