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

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

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

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

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

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

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

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

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

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

冪律分布函數(shù)的無標(biāo)度性質(zhì)：考慮一個(gè)概率分布函數(shù)f(x)，如果對(duì)任意給定常數(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ò)受到隨意攻擊細(xì)胞復(fù)雜網(wǎng)絡(luò)的應(yīng)用：

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

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

ki

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

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

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

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

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

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

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

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

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

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

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

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

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

核數(shù)

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

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