復雜網絡課件

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

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

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

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

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

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

NW小世界模型中，p=0對應于原來的最近鄰耦合網絡，p=1對應于全局耦合網絡。無標度網絡模型

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

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

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

那么必有(假定)

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

肺部細胞形成一個復雜網絡因特網復雜網絡的應用：

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

ki

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

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

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

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

網絡的聚類系數C：所有節(jié)點i的聚類系數Ci的平均值。（0C1）

C=0網絡中所有節(jié)點都是孤立點

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

★網絡節(jié)點間聯系的密切程度,體現網絡的凝聚力

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

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

★研究表明，節(jié)點介數與度之間有很強的相關性，不同類型的網絡，其介數分布也大不一樣。網絡介數

★網絡點介數，網絡邊介數：所有節(jié)點（邊）的平均介數

★網絡介數說明了網絡的什么性質

核數

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

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