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

復(fù)雜網(wǎng)絡(luò)第二講網(wǎng)絡(luò)拓?fù)浠灸Ｐ图捌湫再|(zhì)李凱凱復(fù)雜網(wǎng)絡(luò)第二講1規(guī)則網(wǎng)絡(luò)隨機(jī)圖小世界網(wǎng)絡(luò)模型無標(biāo)度網(wǎng)絡(luò)模型局域世界演化網(wǎng)絡(luò)模型模塊性與等級網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的自相似性規(guī)則網(wǎng)絡(luò)2規(guī)則網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)及其與邊的關(guān)系是固定的。(a)全局耦合網(wǎng)絡(luò);(b)最近鄰耦合網(wǎng)絡(luò);(c)星形網(wǎng)絡(luò)全員耦合網(wǎng)具有最小的平均路徑長度L。=1和最大的聚類系數(shù)C=1規(guī)則網(wǎng)絡(luò)3最近鄰命參包含N個圍成一個環(huán)的點(diǎn),其中每個節(jié)點(diǎn)都與它左右各K/2個鄰居點(diǎn)相連(K為偶數(shù)),對于較大的K值,最近鄰耦合網(wǎng)絡(luò)的聚類系數(shù)為3(K-2)34(K-1)4因此,這樣的網(wǎng)絡(luò)是高度聚類的。對于固定的K值,網(wǎng)絡(luò)平均路徑長度為(N→∞)2K星形耦合網(wǎng)參:有一個中心點(diǎn),其余N-1個點(diǎn)都只與這個中心點(diǎn)連接,其平均路徑長度為2(N-1)N-1→>2(N→)聚類系數(shù)為N-1最近鄰命參包含N個圍成一個環(huán)的點(diǎn),其中每個節(jié)點(diǎn)都4隨機(jī)圖隨機(jī)圖是與規(guī)則網(wǎng)絡(luò)相反的網(wǎng)絡(luò),一個典型模型是Erdos和Renⅵi于40多年前開始研究的隨機(jī)圖模型假設(shè)有大量的紐扣(N》1)散落在地上,并以相同的概率p給每對紐扣系上一根線。這樣就會得到一個有N個節(jié)點(diǎn),約pN(N-1)/2條邊的ER隨機(jī)圖的實(shí)例ep=15隨機(jī)圖5ER隨機(jī)圖的性質(zhì)隨機(jī)圖理論的一個主要研究課題是當(dāng)概率p為多大時,隨機(jī)圖會產(chǎn)生一些特殊的屬性?巸rdos和Renyi系統(tǒng)地研究了當(dāng)N→∞時,BR隨機(jī)圖的性質(zhì)與概率p之間的關(guān)系,他們采用了如下定義:如果當(dāng)M_時產(chǎn)生一個具有性質(zhì)Q的即隨機(jī)圖的概率為1,那么就稱幾乎每一個ER隨機(jī)圖都具有性質(zhì)QErdos和Renyi的最重要的發(fā)現(xiàn)時B隨機(jī)圖具有如下的涌現(xiàn)或變性質(zhì)ER隨機(jī)圖的許多重要的性質(zhì)都是突然涌現(xiàn)的。也就是說,對于任意給定的概率p,要么幾乎每一個圖都具有性質(zhì)Q,要么幾乎每一個圖都不具有該性質(zhì)上述紐扣網(wǎng)絡(luò),如果p大于某個臨界值Pc∞(mM/N,那么幾乎每一個隨機(jī)圖都是連通的ER隨機(jī)圖的性質(zhì)6ER隨機(jī)圖的平均度是<k>=p(N-1)≈pN,平均路徑長度LE1nN/lnxk>。L為網(wǎng)絡(luò)規(guī)模的對數(shù)增長函數(shù)是典型的小世界特征。ER隨機(jī)圖的聚類系數(shù)是C=p=<k>/N《1,這意味著大規(guī)模的稀疏ER隨機(jī)圖沒有聚類特性。實(shí)際網(wǎng)絡(luò)的聚類系數(shù)要比相同規(guī)模的BR隨機(jī)圖的聚類系數(shù)要高得多ER隨機(jī)圖的度分布可用Poission分布來表示P(k)kp(-p)*sskses因此,ER隨機(jī)圖也稱為“Poission隨機(jī)圖”ER隨機(jī)圖的平均度是<k>=p(N-1)≈pN,平均路徑長度7小世界網(wǎng)絡(luò)模型作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過渡,Watts和Strogtz于1998年引入了一個小世界網(wǎng)絡(luò)模型,稱為W小世界模型。其構(gòu)造算法如下①從規(guī)則圖開始:考慮一個含有N個點(diǎn)的最近鄰耦合網(wǎng)絡(luò),它們圍成個環(huán),其中每個節(jié)點(diǎn)都與它左右相鄰的各2個節(jié)點(diǎn)相連,是偶數(shù)②隨機(jī)化重連:以概率p隨機(jī)地重連網(wǎng)絡(luò)中的每個邊,即將邊的一個端點(diǎn)保持不變,而另一個端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個節(jié)點(diǎn)。其中規(guī)定,任意兩個不同節(jié)點(diǎn)之一間至多只能有一條邊,并且每一個節(jié)點(diǎn)都不能有邊與自身相連小}界網(wǎng)緡阿網(wǎng)絡(luò)Pao增人陽機(jī)連概嶂p小世界網(wǎng)絡(luò)模型8氣p}F口s小世網(wǎng)絡(luò)的聚類系數(shù)平均長度連概率P要化具有較短的平均路徑長度又具有較高的聚類系數(shù)的網(wǎng)絡(luò)就稱為小世界網(wǎng)絡(luò)Newman和Watts提出了NW小世界模型,用“隨機(jī)化加邊”取代WS小世界模型構(gòu)造中的“隨機(jī)化重連”。算法如下①從規(guī)則圖開始:含有N個節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)。②隨機(jī)化加邊:以概率P在隨機(jī)選取的一對節(jié)點(diǎn)之間加上條邊Nw小世界模型中,p=0對應(yīng)于原來的最近鄰耦合網(wǎng)絡(luò)p=1對應(yīng)于全局耦合網(wǎng)絡(luò)氣p}F口9小世界網(wǎng)絡(luò)的性質(zhì)聚類系數(shù)NS小世界網(wǎng)絡(luò)的聚類系數(shù)為3(K-2)C(p)(14(K-1)NW小世界網(wǎng)絡(luò)的聚類系數(shù)為3(KC(p)4(K-1)+4Kp(P+2)·2.平均路徑長度2NL(P)Kf(NKp/2)小世界網(wǎng)絡(luò)的性質(zhì)10復(fù)雜網(wǎng)絡(luò)第二講課件11復(fù)雜網(wǎng)絡(luò)第二講課件12復(fù)雜網(wǎng)絡(luò)第二講課件13復(fù)雜網(wǎng)絡(luò)第二講課件14復(fù)雜網(wǎng)絡(luò)第二講課件15復(fù)雜網(wǎng)絡(luò)第二講課件16復(fù)雜網(wǎng)絡(luò)第二講課件17復(fù)雜網(wǎng)絡(luò)第二講課件18復(fù)雜網(wǎng)絡(luò)第二講課件19復(fù)雜網(wǎng)絡(luò)第二講課件20復(fù)雜網(wǎng)絡(luò)第二講課件21復(fù)雜網(wǎng)絡(luò)第二講課件22復(fù)雜網(wǎng)絡(luò)第二講課件23復(fù)雜網(wǎng)絡(luò)第二講課件24復(fù)雜網(wǎng)絡(luò)第二講課件25復(fù)雜網(wǎng)絡(luò)第二講課件26復(fù)雜網(wǎng)絡(luò)第二講課件27復(fù)雜網(wǎng)絡(luò)第二講課件28復(fù)雜網(wǎng)絡(luò)第二講課件29復(fù)雜網(wǎng)絡(luò)第二講課件30復(fù)雜網(wǎng)絡(luò)第二講課件31復(fù)雜網(wǎng)絡(luò)第二講課件32復(fù)雜網(wǎng)絡(luò)第二講課件33復(fù)雜網(wǎng)絡(luò)第二講課件34復(fù)雜網(wǎng)絡(luò)第二講課件