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

1、復(fù)雜網(wǎng)絡(luò)及其應(yīng)用研究新進展學(xué)生： 學(xué)號：復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的含義：我國著名科學(xué)家錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)一個較嚴(yán)格的定義：具有自組織、自相似、吸引子、小世界、無標(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ò):

2、 規(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ò)系統(tǒng)中節(jié)點及其與邊的關(guān)系是固定的。（a）全局耦合網(wǎng)絡(luò)； （b）最近鄰耦合網(wǎng)絡(luò)； （c）星形網(wǎng)絡(luò)全局耦合網(wǎng)絡(luò)具有最小的平均路徑長度Lgc =1和最大的聚類系數(shù)Cgc =1；最近鄰耦合網(wǎng)絡(luò):包含N個圍成一個環(huán)的點，其中每個節(jié)點都與它左右各K

3、/2個鄰居點相連（K為偶數(shù)），對于較大的K值，最近鄰耦合網(wǎng)絡(luò)的聚類系數(shù)為因此，這樣的網(wǎng)絡(luò)是高度聚類的。對于固定的K值，網(wǎng)絡(luò)平均路徑長度為 星形耦合網(wǎng)絡(luò)：有一個中心點，其余N-1個點都只與這個中心點連接，其平均路徑長度為 聚類系數(shù)為 隨機圖隨機圖是與規(guī)則網(wǎng)絡(luò)相反的網(wǎng)絡(luò)，一個典型模型是Erdos和Renyi于40多年前開始研究的隨機圖模型。 假設(shè)有大量的紐扣（N1）散落在地上，并以相同的概率p給每對紐扣系上一根線。這樣就會得到一個有N個節(jié)點，約pN(N-1)/2條邊的ER隨機圖的實例。2019，Watts和Strogatz：WS小世界網(wǎng)絡(luò)WS小世界模型NW小世界模型C(p) : 平均聚集系數(shù) L(

4、p) : 平均最短路徑小世界網(wǎng)絡(luò)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機圖的過渡，Watts和Strogtz于2019年引入了一個小世界網(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小世

5、界模型，用“隨機化加邊”取代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

6、個節(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ò)受到隨意攻擊細(xì)胞復(fù)雜網(wǎng)絡(luò)的應(yīng)用： 肺部細(xì)胞形成一個復(fù)雜網(wǎng)絡(luò)因特網(wǎng)復(fù)雜網(wǎng)絡(luò)的應(yīng)用： 因特網(wǎng)形成的復(fù)雜網(wǎng)絡(luò)交通運輸復(fù)雜網(wǎng)

7、絡(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é)點的度和的平均值 ，記作。事實上，=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ò)的聚類

8、系數(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é)點或邊的作用和影響力。

9、如果一對節(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é)點后，所剩余的子圖

10、 若一個節(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ò)拓?fù)浣Y(jié)構(gòu)性能的因素：密度：只要某個社區(qū)的密度超過閾值，停止該社區(qū)的聚合。聚合網(wǎng)絡(luò)的映射函數(shù)f：聚合網(wǎng)絡(luò)密度的計算公式：其中，|E|=V(V-1)/2 復(fù)雜網(wǎng)絡(luò)研究新進展 復(fù)雜網(wǎng)絡(luò)的應(yīng)用復(fù)