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

1、復(fù)雜網(wǎng)絡(luò)第二講網(wǎng)絡(luò)拓?fù)浠灸Ｐ图捌湫再|(zhì)李凱凱 規(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ò)系統(tǒng)中節(jié)點(diǎn)及其與邊的關(guān)系是固定的。（a）全局耦合網(wǎng)絡(luò)； （b）最近鄰耦合網(wǎng)絡(luò)； （c）星形網(wǎng)絡(luò)具有最小的平均路徑長度Lgc =1和最大的聚類系數(shù)Cgc =1；:含N個(gè)圍成一個(gè)環(huán)的點(diǎn)，其中每個(gè)節(jié)點(diǎn)都與它左右各K/2個(gè)鄰居點(diǎn)相連（K為偶數(shù)），對于較大的K值，最近鄰耦合網(wǎng)絡(luò)的聚類系數(shù)為因此，這樣的網(wǎng)絡(luò)是高度聚類的。對于固定的K值，網(wǎng)絡(luò)平均路徑長度為 ：有一個(gè)中心點(diǎn)，其余N-1個(gè)點(diǎn)都只與這個(gè)中心點(diǎn)連接，其平均路徑長度為 聚類系數(shù)為 43)1(

2、4)2(3KKCnc)(N)(N2) 1() 1(22NNNLstar11NNCstar)(NKNLnc2隨機(jī)圖 隨機(jī)圖是與規(guī)則網(wǎng)絡(luò)相反的網(wǎng)絡(luò)，一個(gè)典型模型是Erdos和Renyi于40多年前開始研究的隨機(jī)圖模型。 假設(shè)有大量的紐扣（N1）散落在地上，并以相同的概率p給每對紐扣系上一根線。這樣就會(huì)得到一個(gè)有N個(gè)節(jié)點(diǎn)，約pN(N-1)/2條邊的ER隨機(jī)圖的實(shí)例。 ER隨機(jī)圖的性質(zhì)隨機(jī)圖理論的一個(gè)主要研究課題是：當(dāng)概率p為多大時(shí)，隨機(jī)圖會(huì)產(chǎn)生一些特殊的屬性？Erdos和Renyi系統(tǒng)地研究了當(dāng) 時(shí)，ER隨機(jī)圖的性質(zhì)與概率p之間的關(guān)系，他們采用了如下定義：如果當(dāng) 時(shí)產(chǎn)生一個(gè)具有性質(zhì)Q的ER隨機(jī)圖的概

3、率為1，那么就稱幾乎每一個(gè)ER隨機(jī)圖都具有性質(zhì)Q。Erdos和Renyi的最重要的發(fā)現(xiàn)時(shí)ER隨機(jī)圖具有如下的涌現(xiàn)或相變性質(zhì)：ER隨機(jī)圖的許多重要的性質(zhì)都是突然涌現(xiàn)的。也就是說，對于任意給定的概率p，要么幾乎每一個(gè)圖都具有性質(zhì)Q，要么幾乎每一個(gè)圖都不具有該性質(zhì)。上述紐扣網(wǎng)絡(luò)，如果p大于某個(gè)臨界值 ，那么幾乎每一個(gè)隨機(jī)圖都是連通的。NNNNpc/ )(lnER 隨機(jī)圖的平均度是 ,平均路徑長度 。LER為網(wǎng)絡(luò)規(guī)模的對數(shù)增長函數(shù)是典型的小世界特征。ER隨機(jī)圖的聚類系數(shù)是C=p=/N1，這意味著大規(guī)模的稀疏ER隨機(jī)圖沒有聚類特性。實(shí)際網(wǎng)絡(luò)的聚類系數(shù)要比相同規(guī)模的ER隨機(jī)圖的聚類系數(shù)要高得多。ER隨機(jī)圖

4、的度分布可用Poission分布來表示：因此，ER隨機(jī)圖也稱為“Poission隨機(jī)圖”。kNLERln/lnpN1)-p(Nk!)1 ()(kppkNkPekkkkNk小世界網(wǎng)絡(luò)模型作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過渡，作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過渡，WattsWatts和和StrogtzStrogtz于于19981998年引年引入了一個(gè)小世界網(wǎng)絡(luò)模型，稱為入了一個(gè)小世界網(wǎng)絡(luò)模型，稱為WSWS小世界模型。其構(gòu)造算法如下：小世界模型。其構(gòu)造算法如下：從規(guī)則圖開始：考慮一個(gè)含有從規(guī)則圖開始：考慮一個(gè)含有N N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)

5、點(diǎn)都與它左右相鄰的各環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2K/2個(gè)節(jié)點(diǎn)相連，個(gè)節(jié)點(diǎn)相連，K K是偶數(shù)。是偶數(shù)。隨機(jī)化重連：以概率隨機(jī)化重連：以概率p p隨機(jī)地重連網(wǎng)絡(luò)中的每個(gè)邊，即將邊的一個(gè)端點(diǎn)隨機(jī)地重連網(wǎng)絡(luò)中的每個(gè)邊，即將邊的一個(gè)端點(diǎn)保持不變，而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)。其中規(guī)定，保持不變，而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)。其中規(guī)定，任意兩個(gè)不同節(jié)點(diǎn)之任意兩個(gè)不同節(jié)點(diǎn)之- -間至多只能有一條邊，并且每一個(gè)節(jié)點(diǎn)都不能間至多只能有一條邊，并且每一個(gè)節(jié)點(diǎn)都不能有邊與自身相連。有邊與自身相連。P=0對應(yīng)于完全規(guī)則網(wǎng)絡(luò)，p=1對應(yīng)于完全隨機(jī)網(wǎng)絡(luò)。 具有較短的平均路徑長度又具有較

6、高的聚類系數(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ī)選取的一對節(jié)點(diǎn)之間加上一條邊。 NW小世界模型中，p=0對應(yīng)于原來的最近鄰耦合網(wǎng)絡(luò)，p=1對應(yīng)于全局耦合網(wǎng)絡(luò)。小世界網(wǎng)絡(luò)的性質(zhì) 1.聚類系數(shù)WS小世界網(wǎng)絡(luò)的聚類系數(shù)為NW小世界網(wǎng)絡(luò)的聚類系數(shù)為 2.平均路徑長度3)1 () 1(4)2(3)(pKKpC)2(4) 1(4)2( 3)(pKpKKpC)2/(2)(NKpfKNpL其中f（u）為一普適標(biāo)度函數(shù)，滿足Newma

7、n等人基于平均場方法給出了如下近似表達(dá)式： 3.度分布在基于“隨機(jī)化加邊”機(jī)制的NW小世界模型中，每個(gè)節(jié)點(diǎn)的度至少為K，因此當(dāng) 時(shí)，一個(gè)隨機(jī)選取的節(jié)點(diǎn)的度為k的概率為：而當(dāng)k1.1Nrandi 。等級網(wǎng)絡(luò) 等級網(wǎng)絡(luò)具有與網(wǎng)絡(luò)規(guī)模無關(guān)的較高的聚類系數(shù) ， 等級模塊性的一個(gè)最重要的量化標(biāo)志是節(jié)點(diǎn)聚類系數(shù)服從冪律 。這表明度很小的節(jié)點(diǎn)具有較高的聚類系數(shù)，相反度很高的節(jié)點(diǎn)具有低的聚類系數(shù)，其作用只是把不同的模塊連接起來。 ER隨機(jī)圖和BA無標(biāo)度網(wǎng)絡(luò)都不具有等級拓?fù)?，在這兩類網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類系數(shù)C（k）與該節(jié)點(diǎn)的度k無關(guān)。6 . 0C1)( kkC復(fù)雜網(wǎng)絡(luò)的自相似性 等級網(wǎng)絡(luò)看上去有一個(gè)明顯的特征，就是

8、該網(wǎng)絡(luò)部分與整體具有很明顯的相似性，即自相似性，正是分形的一個(gè)基本特征。 Sierpinski三角形： 復(fù)雜網(wǎng)絡(luò)的小世界特征意味著網(wǎng)絡(luò)的平均路徑長度l可以用網(wǎng)絡(luò)規(guī)模N的對數(shù)函數(shù)來表示，即 ，等價(jià)于 其中L0表示特征長度，上式意味著網(wǎng)絡(luò)規(guī)模是網(wǎng)絡(luò)平均路徑長度的指數(shù)函數(shù)。而自相似性要求滿足某種冪律關(guān)系，然而，Song等人的研究指出，許多實(shí)際網(wǎng)絡(luò)，包括WWW，蛋白質(zhì)交互作用網(wǎng)絡(luò)和細(xì)胞網(wǎng)絡(luò)等，在某種長度-標(biāo)度下確實(shí)是自相似的。NLln0/lnLLeN 與自相似性密切相關(guān)的一個(gè)概念是分?jǐn)?shù)維，計(jì)算自相似分形的維數(shù)的一種常用的方法是盒記數(shù)法?；舅枷胧怯眠呴L為lB的盒子來覆蓋該圖形，并統(tǒng)計(jì)完全覆蓋該圖形需要

9、的最少的盒子數(shù)NB(lB) 圖形維數(shù)的近似計(jì)算公式為 等價(jià)地有冪律標(biāo)度公式)ln()(lnBBBBllNdBdBBBllN)( 例：對于Sierpinski三角形，假設(shè)這個(gè)大三角形的邊長為1，如果用邊長為1/2的正方形覆蓋Sierpinski三角形，那么需要3個(gè)正方形，如果用邊長為1/4的正方形覆蓋Sierpinski三角形，需要9個(gè)正方形，如果用邊長為1/8的正方形覆蓋它，則需要27個(gè)正方形，依次類推，有以下公式：) 8/ 1ln(27ln) 4/ 1ln(9ln) 2/ 1ln(3lnBd Song等人通過采用重整化過程，揭示出自相似性和無標(biāo)度分布在網(wǎng)絡(luò)的所有粗?；A段都成立，在把所有節(jié)點(diǎn)

10、都分配到盒子中之后，再把每個(gè)盒子用單個(gè)節(jié)點(diǎn)來表示，這些節(jié)點(diǎn)稱為重整化節(jié)點(diǎn)，如果在兩個(gè)未重整化盒子之間至少存在一條邊，那么兩個(gè)重整化節(jié)點(diǎn)之間就有一條邊相連，這樣就得到一個(gè)新的重整化網(wǎng)絡(luò)。這種重整化過程可以一直進(jìn)行下去，直到這個(gè)網(wǎng)絡(luò)被規(guī)約為單個(gè)節(jié)點(diǎn)。 重整化網(wǎng)絡(luò)的度分布P（k）在重整化下具有不變性。 下圖顯示了www的度分布在不同盒子尺寸lB重整化下的不變性。rkkPkP) () ()(參考文獻(xiàn) 1Barabasi A L,Bonabeau E.Scale-free networks.Scientific American,May 2003,5059 2 Barabasi A L,Oltvai Z N.Network biology:Understanding