分子生物網(wǎng)絡(luò)分析-第2章-網(wǎng)絡(luò)拓?fù)浠灸Ｐ图捌湫再|(zhì)

1、Page 1第二章 網(wǎng)絡(luò)拓?fù)浠灸Ｐ图捌湫再|(zhì)教 師：辦公室：外語學(xué)館412室分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 2n理解網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)行為之間的關(guān)系。n對實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)有深入的了解，考慮改善網(wǎng)絡(luò)的行為。n在此基礎(chǔ)上建立合適的網(wǎng)絡(luò)結(jié)構(gòu)模型。n本章介紹幾類基本的模型：規(guī)則網(wǎng)絡(luò)、隨機(jī)圖、小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)、等級網(wǎng)絡(luò)等模型。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 3nWatts和Strogatz關(guān)于小世界網(wǎng)絡(luò)的工作；nBarabasi和Albert關(guān)

2、于無標(biāo)度網(wǎng)絡(luò)的開創(chuàng)性工作。n人們對存在于不同領(lǐng)域的大量實(shí)際網(wǎng)絡(luò)的拓?fù)涮卣鬟M(jìn)行了廣泛的實(shí)證性研究。n從不同角度提出了各種各樣的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 4分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 5分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 6分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Pag

3、e 7分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 8有一個(gè)中心點(diǎn)，其余N-1個(gè)點(diǎn)都只與這個(gè)中心點(diǎn)連接。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 9有一個(gè)中心點(diǎn)，其余有一個(gè)中心點(diǎn)，其余N-1個(gè)點(diǎn)都只與這個(gè)個(gè)點(diǎn)都只與這個(gè)中心點(diǎn)連接中心點(diǎn)連接分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 101112ijijLdNN21iiiiECkk請同學(xué)分析全局耦合網(wǎng)絡(luò)的拓?fù)鋵傩?。如：平均路徑長度，聚類系數(shù)

4、，服從哪種分布。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 11分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 12請計(jì)算全局耦合網(wǎng)絡(luò)的緊密度、拓?fù)湎禂?shù)、介數(shù)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 13n最近鄰耦合網(wǎng)絡(luò)：每個(gè)節(jié)點(diǎn)都與它左右的K/2個(gè)節(jié)點(diǎn)相連，K是一個(gè)偶數(shù)。n對大的N, K, 有：聚類系數(shù)C3/4, 平均路徑長度L無窮大。請同學(xué)分析最近鄰耦合網(wǎng)絡(luò)的拓?fù)鋵傩?。如：平均路徑長

5、度，聚類系數(shù)，服從哪種分布。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 14n一般地，規(guī)則網(wǎng)絡(luò)具有大的聚類系數(shù)和大的平均距離。n這類網(wǎng)絡(luò)是高度聚類的但不是一個(gè)小世界網(wǎng)絡(luò)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1513258471069請計(jì)算最近鄰耦合網(wǎng)絡(luò)的緊密度、拓?fù)湎禂?shù)、介數(shù)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 161112ijijLdN N21iiiiECkk請同學(xué)分析

6、星形耦合網(wǎng)絡(luò)的拓?fù)鋵傩?。如：平均路徑長度，聚類系數(shù)，服從哪種分布。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 17n 星形耦合網(wǎng)絡(luò)是比較特殊的一類網(wǎng)絡(luò)。n 有些文獻(xiàn)中定義如果一個(gè)節(jié)點(diǎn)只有一個(gè)鄰居節(jié)點(diǎn)，那么該節(jié)點(diǎn)聚類系數(shù)定義為1.n 有些研究文獻(xiàn)則定義只有一個(gè)鄰居節(jié)點(diǎn)的節(jié)點(diǎn)聚類系數(shù)為0，依此定義，星形網(wǎng)絡(luò)的聚類系數(shù)為0. NNNCNNNNL1121122聚聚類類系系數(shù)數(shù)：平平均均路路徑徑長長度度： 0C 分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 18請計(jì)算

7、星形耦合網(wǎng)絡(luò)的緊密度、拓?fù)湎禂?shù)、介數(shù)。35846917102分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 19分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 20n與完全規(guī)則網(wǎng)絡(luò)相反的是完全隨機(jī)網(wǎng)絡(luò)。n典型的模型是Erds和Rnyi于40多年前開始研究的ER隨機(jī)圖模型。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 21n 假設(shè)有大量的紐扣（N1）散落在地上，并以相同的概率P給每對紐扣系上一根線。

8、n 這樣就會得到一個(gè)有N個(gè)點(diǎn)，約PN（N-1）/2條邊的ER隨機(jī)圖的實(shí)例。例如：節(jié)點(diǎn)數(shù)N=10，P值分別為：0，0.1，0.15，0.25則可以得到ER隨機(jī)圖的實(shí)例。請同學(xué)給出此實(shí)例演化過程。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 22n隨機(jī)演化示意圖：N=10，P=0；P=0.1；P=0.15，P=0.25分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 23nER隨機(jī)圖具有的性質(zhì)：涌現(xiàn)或相變性質(zhì)nER隨機(jī)圖的許多重要性質(zhì)都是突然涌現(xiàn)的：也就是說，對于任一

9、給定的概率P，要么幾乎每一個(gè)圖都具有某個(gè)性質(zhì)Q（比如，連通性），要么幾乎每一個(gè)圖都不具有該性質(zhì)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 24n例如，對于上述紐扣網(wǎng)絡(luò)，如果你撿起一個(gè)紐扣，那么將有多少個(gè)紐扣也會跟著被拎起來呢？n結(jié)果顯示，如果概率P有大于某個(gè)臨界值Pc（lnN）/N，那么幾乎每一個(gè)隨機(jī)圖都是連通的，也就是說，隨機(jī)地?fù)炱鹨粋€(gè)紐扣都會拎起地上幾乎所有的紐扣。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 25nER隨機(jī)圖的平均度=P(N-1)PN

10、。n設(shè)LER是ER隨機(jī)圖的平均路徑長度。直觀上，對于ER隨機(jī)圖中隨機(jī)選取的一個(gè)點(diǎn)，網(wǎng)絡(luò)中大約有 LER個(gè)其他的點(diǎn)與該點(diǎn)之間的距離等于或非常接近LER。因此，LERlnN/ln。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 26n這種平均路徑長度為網(wǎng)絡(luò)規(guī)模的對數(shù)增長函數(shù)的特征就是典型的小世界特征。n因?yàn)楫?dāng)lnN的值隨N增長得很慢，這就使得即使是規(guī)模很大的網(wǎng)絡(luò)也可以具有很小的平均路徑長度。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 27nER隨機(jī)圖中兩個(gè)節(jié)點(diǎn)之間

11、不論是否具有共同的鄰居節(jié)點(diǎn)，其連接概率均為P。n因此，ER隨機(jī)圖的聚類系數(shù)C=P=/N1，這意味著大規(guī)模的稀疏ER隨機(jī)圖沒有聚類特征。n現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)一般都具有明顯的聚類特性，也就是說，實(shí)際的復(fù)雜網(wǎng)絡(luò)的聚類系數(shù)要比相同規(guī)模的ER隨機(jī)圖的聚類系數(shù)高得多。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 28分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 29分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Pag

12、e 30分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 31布朗運(yùn)動(dòng)布朗運(yùn)動(dòng)分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 32分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 33nER隨機(jī)圖作為實(shí)際復(fù)雜網(wǎng)絡(luò)的模型存在明顯的缺陷。nER隨機(jī)圖理論一直是研究復(fù)雜網(wǎng)絡(luò)拓?fù)涞幕纠碚摚渲幸恍┗舅枷朐谀壳暗膹?fù)雜網(wǎng)絡(luò)理論研究中仍然很重要。n可以參考Bollobs的著作。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(M

13、olecular Biology Network Analysis)Page 34n從多角度對ER隨機(jī)圖進(jìn)行擴(kuò)展以使其更接近真實(shí)的網(wǎng)絡(luò)。n一個(gè)推廣就是具有任意給定度分布的廣義隨機(jī)圖（generalized random graph）。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 35n給定一個(gè)度分布P（k），它表示了網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)所占的比例。n基于這一分布按相同概率產(chǎn)生多個(gè)度序列為ki（i=1,2,.,N）的由N個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)。n這些網(wǎng)絡(luò)模型的集合稱為配置模型（configuration model），詳細(xì)介紹參見New

14、man的綜述。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 36n這兩類網(wǎng)絡(luò)模型都不能再現(xiàn)真實(shí)網(wǎng)絡(luò)的一些重要特征。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 37n畢竟大部分實(shí)際網(wǎng)絡(luò)既不是完全規(guī)則的，也不是完全隨機(jī)的。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 38nWatts和Strogtz于1998年引入了一個(gè)有趣的小世界網(wǎng)絡(luò)模型，稱為WS小世界模型，作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過

15、渡。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 39n WS小世界模型構(gòu)造算法如下：1.從規(guī)則圖開始：考慮一個(gè)含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右的各K/2節(jié)點(diǎn)相連，K是偶數(shù)。2.隨機(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)都不能有邊與自身相連。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 4

16、0分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 41n通過調(diào)節(jié)P的值就可以控制從完全規(guī)則網(wǎng)絡(luò)到完成隨機(jī)網(wǎng)絡(luò)的過渡。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 42分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 43分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 44nWS小世界模型的隨機(jī)化重連過程：分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分

17、析(Molecular Biology Network Analysis)Page 45分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 462( )(/ 2)NL pf NKpK分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 47分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 48分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 492

18、.NW小世界模型nWS小世界模型構(gòu)造算法中的隨機(jī)化過程有可能破壞網(wǎng)絡(luò)的連通性。n另一個(gè)研究較多的小世界模型由Newman和Watts稍后提出的，稱為NW小世界模型。n該模型是通過用“隨機(jī)化加邊”取代WS小世界模型 構(gòu)造中的“隨機(jī)化重連”而得到的。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 502.NW小世界模型nNW小世界模型構(gòu)造算法：n1.從規(guī)則圖開始：考慮一個(gè)含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各k/2個(gè)節(jié)點(diǎn)相連，k是偶數(shù)。n2.隨機(jī)化加邊：以概率P在隨機(jī)選取的一對節(jié)點(diǎn)之間加上一條邊。

19、其中，任意兩個(gè)不同的節(jié)點(diǎn)之間至多只能有一條邊，并且每一個(gè)節(jié)點(diǎn)都不能有邊與自身相連。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 512.NW小世界模型nNW小世界模型的隨機(jī)化加邊過程。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 522.NW小世界模型n在NW小世界模型中：P=0對應(yīng)于原來的最近鄰耦合網(wǎng)絡(luò)；P=1則對應(yīng)于全局耦合網(wǎng)絡(luò)。n理論分析，NW小世界模型要比WS小世界模型簡單一些。當(dāng)P足夠小和N足夠大時(shí)，NW小世界模型本質(zhì)上等同于WS小世界模型。分子生物

20、網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 532.NW小世界模型分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 543.小世界網(wǎng)絡(luò)模型的統(tǒng)計(jì)性質(zhì)n聚類系數(shù)：分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 553.小世界網(wǎng)絡(luò)模型的統(tǒng)計(jì)性質(zhì)分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 563.小世界網(wǎng)絡(luò)模型的統(tǒng)計(jì)性質(zhì)分子生物網(wǎng)絡(luò)分析分子生

21、物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 57分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 58分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 59分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 60分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 61分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析

22、(Molecular Biology Network Analysis)Page 62請同學(xué)們回憶什么是冪律分布？請同學(xué)們思考什么是特征長度？分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 63n特征長度（Characteristic length）是屬于分形幾何的概念。n對于某個(gè)物體, 特征長度通常是指該物體長度中有代表意義的長度, 如我們考察一個(gè)球體, 那么它的特征長度就是該球體的半徑或直徑。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 64n普通幾何學(xué)研究

23、的對象，一般都具有整數(shù)的維數(shù)。比如，零維的點(diǎn)、一維的線、二維的面、三維的立體、乃至四維的時(shí)空。n在20世紀(jì)70年代末80年代初，產(chǎn)生了新興的分形幾何學(xué)（fractal geometry），空間具有不一定是整數(shù)的維，而存在一個(gè)分?jǐn)?shù)維數(shù)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 65n自然界中的物體或圖形, 要么具有特征長度, 要么不具有特征長度。n對于具有特征長度的物體, 只要其特征長度不變, 其性質(zhì)就不會發(fā)生什么變化。n還有的事物沒有特征尺度，就必須同時(shí)考慮從小到大的許許多多尺度（或者叫標(biāo)度），這叫做“無標(biāo)度性”的問題。

24、分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 66n分開幾何：分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 67n分形幾何學(xué)的基本思想是：客觀事物具有自相似的層次結(jié)構(gòu)，局部與整體在形態(tài)、功能、信息、時(shí)間、空間等方面具有統(tǒng)計(jì)意義上的相似性，稱為自相似性。n例如，一塊磁鐵中的每一部分都像整體一樣具有南北兩極，不斷分割下去，每一部分都具有和整體磁鐵相同的磁場。n這種自相似的層次結(jié)構(gòu)，適當(dāng)?shù)姆糯蠡蚩s小幾何尺寸，整個(gè)結(jié)構(gòu)不變。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molec

25、ular Biology Network Analysis)Page 68n自相似性：分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 69n上世紀(jì)80年代初開始的“分形熱”經(jīng)久不息。分形作為一種新的概念和方法，正在許多領(lǐng)域開展應(yīng)用探索。n美國物理學(xué)大師約翰惠勒說過：今后誰不熟悉分形，誰就不能被稱為科學(xué)上的文化人。n由此可見分形的重要性。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 70n近年來，人們在互聯(lián)網(wǎng)和人際關(guān)系網(wǎng)絡(luò)等社會學(xué)網(wǎng)絡(luò)的研究中都發(fā)現(xiàn)了“無標(biāo)度”特性

26、。n無標(biāo)度網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)通過少數(shù)中心節(jié)點(diǎn)連接到一起，這就意味著節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位是不平等的，中心節(jié)點(diǎn)在連接網(wǎng)絡(luò)完整性方面起更加重要的作用。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 71n定義：無標(biāo)度網(wǎng)絡(luò)，是指網(wǎng)絡(luò)中連通度的分布符合冪率分布，即P(k)k-r的網(wǎng)絡(luò)，如圖2-4 B所示。n這種分布說明，在無標(biāo)度網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的連通度較低，但存在少數(shù)連通度非常高的節(jié)點(diǎn)使網(wǎng)絡(luò)連接在一起。在這種網(wǎng)絡(luò)中，平均連通度等標(biāo)度已經(jīng)不足以描述網(wǎng)絡(luò)的規(guī)模和結(jié)構(gòu)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Netw

27、ork Analysis)Page 72n 圖2-4B無標(biāo)度網(wǎng)絡(luò)及其連通度分布和聚類系數(shù)函數(shù)趨勢圖n B為無標(biāo)度網(wǎng)絡(luò)，其連通度分布符合冪率分布，平均聚類系數(shù)函數(shù)曲線水平。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 73分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 74例如：每個(gè)月都會有大量的生物信息學(xué)文章發(fā)表；WWW上則每天都有大量新的網(wǎng)頁產(chǎn)生；分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page

28、75例如：新發(fā)表的文章更傾向于引用一些被廣泛引用的重要文獻(xiàn)；新的個(gè)人主頁上的超文本鏈接更有可能指向新浪、雅虎等著名的站點(diǎn)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 76分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 77分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 78分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 79jji

29、ikk分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 80例例: m0 = 3, m = 2t = 1t = 2t = 3分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 81分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 82n按照這種機(jī)制構(gòu)建起的網(wǎng)絡(luò)即可得到無標(biāo)度網(wǎng)絡(luò)。n例如，在互連網(wǎng)形成的初期，網(wǎng)絡(luò)中的連接呈現(xiàn)隨機(jī)特性，而當(dāng)一個(gè)新的節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)，人們會傾向于訪問已經(jīng)具有一定知名度的網(wǎng)站，也就更

30、有可能與這樣的網(wǎng)頁建立連接。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 83n這樣隨著越來越多的節(jié)點(diǎn)引入網(wǎng)絡(luò)，網(wǎng)絡(luò)連接便呈現(xiàn)出無標(biāo)度特性。n這個(gè)模型很好地解釋了網(wǎng)頁連接網(wǎng)絡(luò)中少數(shù)權(quán)威網(wǎng)站存在的現(xiàn)象，也為生物分子網(wǎng)絡(luò)中無標(biāo)度特性的形成原因提供了很好的啟示。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 84分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 85分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Mol

31、ecular Biology Network Analysis)Page 86分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 87n練習(xí)：初始網(wǎng)絡(luò)含有兩個(gè)節(jié)點(diǎn)，一條邊，經(jīng)過9步,構(gòu)造BA模型，即m0=2,m=2,t=9.分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 88分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 89分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Netw

32、ork Analysis)Page 90分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 91分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 92分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 93nBA網(wǎng)絡(luò)的度分布函數(shù)為：322)2)(1() 1(2)(kmkkkmmkPn這表明BA網(wǎng)絡(luò)的度分布函數(shù)可由冪指數(shù)為3的冪律函數(shù)近似描述。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology

33、 Network Analysis)Page 94分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 95分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 96n目前對BA無標(biāo)度網(wǎng)絡(luò)的度分布理論的研究主要有三種方法：連續(xù)場理論（continuum theory）、主方程法、速率方程法。n這三種方法得到的漸近結(jié)果都是相同的，其中，主方程法和速率方程法是等價(jià)的。需要指出的是，對需要指出的是，對BA無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造及無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造及其理論分析的嚴(yán)格性等還存在一些不同

34、的看法。其理論分析的嚴(yán)格性等還存在一些不同的看法。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 97NNLlogloglog分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 98分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 99分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 100n網(wǎng)絡(luò)的平均聚類系數(shù)與網(wǎng)絡(luò)大小分子生物網(wǎng)絡(luò)分析分子生

35、物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1013.無標(biāo)度網(wǎng)絡(luò)VS隨機(jī)網(wǎng)絡(luò)n如果網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接完全是隨機(jī)的，那么連通度的分布應(yīng)該符合泊松分布或者在大尺度的情況下近似認(rèn)為符合正態(tài)分布。n即度的分布比較均勻，大部分節(jié)點(diǎn)的連通度都與平均連通度相差不多，只有極少數(shù)節(jié)點(diǎn)具有很低或很高的連通度，如圖1-3 A所示。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1023.無標(biāo)度網(wǎng)絡(luò)VS隨機(jī)網(wǎng)絡(luò)分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analy

36、sis)Page 1033.無標(biāo)度網(wǎng)絡(luò)VS隨機(jī)網(wǎng)絡(luò)n 隨機(jī)網(wǎng)絡(luò)中直徑或網(wǎng)絡(luò)平均距離與節(jié)點(diǎn)的數(shù)目的對數(shù)成正比，即Llog(N)。對于包含大量節(jié)點(diǎn)的網(wǎng)絡(luò)，其直徑相對要小得多，任意兩個(gè)節(jié)點(diǎn)間只需要較少的轉(zhuǎn)接即可以連接在一起。n 一方面網(wǎng)絡(luò)中包含有大量節(jié)點(diǎn)和邊，表現(xiàn)出“大世界”的景象，另一方面，連接任意節(jié)點(diǎn)間的距離卻相對較小，呈現(xiàn)“小世界”的特征。這種“小世界”網(wǎng)絡(luò)是復(fù)雜系統(tǒng)互作網(wǎng)絡(luò)的共同特性，因此成為目前網(wǎng)絡(luò)研究分析一個(gè)熱點(diǎn)問題。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1043.無標(biāo)度網(wǎng)絡(luò)VS隨機(jī)網(wǎng)絡(luò)n無標(biāo)度網(wǎng)絡(luò)對網(wǎng)絡(luò)的另一個(gè)

37、重要影響是使網(wǎng)絡(luò)的直徑相對較小，一般來說直徑的大小正比于網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的對數(shù)值的對數(shù)值即Llog(log(N)。n這就使無標(biāo)度網(wǎng)絡(luò)比一般小世界網(wǎng)絡(luò)直徑更小，聯(lián)系更緊密。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 105nA為隨機(jī)網(wǎng)絡(luò)，其連通度分布符合泊松分布，在大尺度情況下近似服從正態(tài)分布。B為無標(biāo)度網(wǎng)絡(luò)，其連通度分布符合冪率分布，平均聚類系數(shù)函數(shù)曲線水平。C為層次網(wǎng)絡(luò)，其連通度分布與符合冪率分布，平均聚類系數(shù)與連通度的倒數(shù)成正比分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analy

38、sis)Page 106分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 107分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 108分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 109無標(biāo)度網(wǎng)絡(luò)小結(jié)：n無標(biāo)度網(wǎng)絡(luò)定義及特點(diǎn)nBA模型及構(gòu)造算法nBA模型的特性1.度分布2.平均路徑長度3.聚類系數(shù)n無標(biāo)度網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)的比較分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Net

39、work Analysis)Page 110分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 111思考題？n無標(biāo)度網(wǎng)絡(luò)模型具有哪些特性？n真實(shí)網(wǎng)絡(luò)中，若某些節(jié)點(diǎn)被攻擊，會出現(xiàn)什么結(jié)果？分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 112n引言故事：Achilles Heel of the InternetAchilles是古希臘傳說中的一位杰出英雄，身經(jīng)百戰(zhàn)，屢建功勛據(jù)說，Achilles出生時(shí)也是一個(gè)極普通的孩子，母親倒提著他的身體放到環(huán)繞地獄的冥河之中去浸泡

40、，練就一一副鋼筋鐵骨，任何兇惡的敵人也不是對手。但是，他的一只腳后跟 卻因?yàn)槲赵谀赣H的手里沒有浸泡到冥河之中，和普通人一樣，成為英雄的致命弱點(diǎn)，最后也死于此。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 113分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 114n脆弱性：今天人們常常把系統(tǒng)的脆弱之處稱為該系統(tǒng)的“Achilles踵”(Achilles Heel).分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analys

41、is)Page 115分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 116分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 117分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 118分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 119分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analys

42、is)Page 120分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 121分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 122分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 123分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 124分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analys

43、is)Page 125分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 126n去除節(jié)點(diǎn)的兩種策略：n1.隨機(jī)故障策略：即完全隨機(jī)地去除網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)；n2.蓄意攻擊策略：即從去除網(wǎng)絡(luò)中度最高的節(jié)點(diǎn)開始，有意識地去除網(wǎng)絡(luò)中一部分度最高的節(jié)點(diǎn)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 127n假設(shè)去除的節(jié)點(diǎn)數(shù)占原始網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)的比例為f，可以用最大連通子圖的相對大小S和平均路徑長度L與f的關(guān)系來度量網(wǎng)絡(luò)的魯棒性。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molec

44、ular Biology Network Analysis)Page 128n當(dāng)f較小時(shí)，隨機(jī)選取的節(jié)點(diǎn)都是度很小的節(jié)點(diǎn)，除掉這些節(jié)點(diǎn)對整個(gè)網(wǎng)絡(luò)的連通性不會產(chǎn)生大的影響。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 129n研究發(fā)現(xiàn)，ER隨機(jī)圖和BA無標(biāo)網(wǎng)絡(luò)之間存在極其顯著的差異。n1.無標(biāo)度網(wǎng)絡(luò)對隨機(jī)節(jié)點(diǎn)故障具有極高的魯棒性：與隨機(jī)圖相比，最大連通子圖的相對大小在相對高得多的f時(shí)才下降到零，而其平均路徑長度的增長則要緩慢得多。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysi

45、s)Page 130分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 131n這種無標(biāo)度網(wǎng)絡(luò)對隨機(jī)故障的高度魯棒性，來自于網(wǎng)絡(luò)度分布的極端非均勻性，即絕大多數(shù)節(jié)點(diǎn)的度相對很小，而有少量節(jié)點(diǎn)的度相對很大。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 132n然而，正是這種非均勻性使無標(biāo)度網(wǎng)絡(luò)對蓄意攻擊具有高度的脆弱性.n只要有意識地去除網(wǎng)絡(luò)中極少量度最大的節(jié)點(diǎn)，就會對整個(gè)網(wǎng)絡(luò)的連通性產(chǎn)生大的影響。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology

46、Network Analysis)Page 133分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 134n無標(biāo)度網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)的魯棒性的形象比較：n1.即使隨機(jī)去除網(wǎng)絡(luò)中的大量節(jié)點(diǎn)，無標(biāo)度網(wǎng)絡(luò)仍可保持基本的連通性。而隨機(jī)去除同樣多的節(jié)點(diǎn)，則可使同樣規(guī)模的隨機(jī)網(wǎng)絡(luò)分成多個(gè)孤立的子網(wǎng)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 135分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 136n2.但蓄意

47、去除少量度最高的節(jié)點(diǎn)就可破壞無標(biāo)度網(wǎng)絡(luò)的連通性。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 137分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 138n例：以Internet為例，它的前身是20世紀(jì)60年代后期由美國國防部高級研究計(jì)劃署（ARPA）研制的ARPANET。n目的之一是為了使得在一些子網(wǎng)和網(wǎng)關(guān)發(fā)生故障的情況下，網(wǎng)絡(luò)還能維持基本的通信工作。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Pag

48、e 139n如今，Internet已經(jīng)發(fā)展成為一個(gè)規(guī)模巨大的網(wǎng)絡(luò)，并在人類社會生活中起著越來越重要的作用。n而Internet上每天都在發(fā)生各種各樣的故障并經(jīng)常受到黑客的攻擊。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 140n這種情況下，Internet能否保持它的功能無疑是一個(gè)重要的課題。nAlbert、Jeong和Barabasi在文獻(xiàn)中研究了兩個(gè)實(shí)際網(wǎng)絡(luò)對隨機(jī)故障和蓄意攻擊的魯棒性。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 141n一個(gè)是含有60

49、00個(gè)節(jié)點(diǎn)的自治層Internet結(jié)構(gòu)圖;n另一個(gè)是含有326000個(gè)網(wǎng)頁的WWW子網(wǎng)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 142n他們得到了與BA無標(biāo)度網(wǎng)絡(luò)相類似的結(jié)果，從而進(jìn)一步驗(yàn)證了對隨機(jī)故障的魯棒性和對蓄意攻擊的脆弱性是無標(biāo)度網(wǎng)絡(luò)的一個(gè)基本特征，并且指出其根源在于無標(biāo)度網(wǎng)絡(luò)的度分布是不均勻性。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 143n對隨機(jī)故障的魯棒性和對蓄意攻擊的脆弱性是無標(biāo)度網(wǎng)絡(luò)的一個(gè)基本特征分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(

50、Molecular Biology Network Analysis)Page 144n事實(shí)上，近些年不同領(lǐng)域科學(xué)家的研究表明，“魯棒但又脆弱（robust yet fragile）”是復(fù)雜系統(tǒng)的最重要和最基本的特征之一。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 145nBroder等人研究了更大規(guī)模的WWW子網(wǎng)的魯棒性。他們發(fā)現(xiàn)只有刪除所有度大于5的節(jié)點(diǎn)才能完全破壞其連通性。n由于有些節(jié)點(diǎn)的度高達(dá)幾千，這就意味著要對整個(gè)網(wǎng)絡(luò)實(shí)施猛烈的攻擊，因此，他們認(rèn)為該網(wǎng)絡(luò)對蓄意攻擊也具有很高的魯棒性。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析

51、(Molecular Biology Network Analysis)Page 146nAlbert認(rèn)為WWW對蓄意攻擊是呈現(xiàn)脆弱性的，而Broder卻認(rèn)為具有很高的魯棒性，這初看起來與Albert等人的結(jié)論似乎是矛盾的？n其實(shí)不然，因?yàn)閃WW具有高度傾斜的度分布，所以度數(shù)大于5的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中所占的比例還是很小的。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 147nCallaway和Cohen等人運(yùn)用逾滲理論對網(wǎng)絡(luò)的魯棒性作了理論性分析。nValente等人基于Callaway和Cohen等人的分析，推出對于隨機(jī)故障和

52、惡意攻擊具有最優(yōu)魯棒性的網(wǎng)絡(luò)中的節(jié)點(diǎn)的度最多只可能取自三個(gè)不同的值。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 148nBollobas和Riordan則運(yùn)用隨機(jī)圖理論對無標(biāo)網(wǎng)絡(luò)的魯棒性和脆弱性作了數(shù)學(xué)分析。nHolme等人研究了基于介數(shù)的刪除策略，其中一個(gè)節(jié)點(diǎn)的介數(shù)刻畫了網(wǎng)絡(luò)中經(jīng)過該節(jié)點(diǎn)的最短路徑的數(shù)目。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1495.適應(yīng)度模型nBA無標(biāo)度網(wǎng)絡(luò)模型的精彩之處在于它把實(shí)際復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，歸結(jié)為增長和優(yōu)先連接兩個(gè)

53、非常簡單明了的機(jī)制。n這很好地體現(xiàn)了科學(xué)研究中的從復(fù)雜現(xiàn)象提取簡單本質(zhì)的特點(diǎn)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1505.適應(yīng)度模型n當(dāng)然這也不可避免地使得BA無標(biāo)度網(wǎng)絡(luò)模型和真實(shí)網(wǎng)絡(luò)相比存在一些明顯的限制。nBA模型只能生產(chǎn)度分布冪律指數(shù)固定為3的無標(biāo)度網(wǎng)絡(luò)，實(shí)際網(wǎng)絡(luò)的冪律指數(shù)則不盡相同，且大都屬于2至3的范圍內(nèi)。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1515.適應(yīng)度模型n此外，實(shí)際網(wǎng)絡(luò)常常具有一些非冪律特征。n因此，在BA模型的基礎(chǔ)上，

54、人們做了各種各樣的擴(kuò)展，其中一些重要的擴(kuò)展模型都是通過修改BA模型中的優(yōu)先連接方式而獲得的。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1525.適應(yīng)度模型n2000年，Jeng等人在Nature上發(fā)表的文章中對43種生物體組織的新陳代謝過程加以研究，他們以各種基質(zhì)（如ADP）為節(jié)點(diǎn)，以基質(zhì)參與的某種化學(xué)反應(yīng)為邊構(gòu)建了新陳代謝的復(fù)雜網(wǎng)絡(luò)。n結(jié)果顯示，這些網(wǎng)絡(luò)的度分布都服從冪律分布，冪指數(shù)在2.02.4之間。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 153

55、5.適應(yīng)度模型n在BA無標(biāo)度網(wǎng)絡(luò)的增長過程中，節(jié)點(diǎn)的度也在發(fā)生變化并且滿足如下冪律關(guān)系。21)()(iitttkn其中 是第i個(gè)節(jié)點(diǎn)在時(shí)刻t的度， 是第i個(gè)節(jié)點(diǎn)加入到網(wǎng)絡(luò)中的時(shí)刻。)(tkiit分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1545.適應(yīng)度模型n上式表明，在BA無標(biāo)度網(wǎng)絡(luò)中，越老的節(jié)點(diǎn)具有越高的度，那么實(shí)際網(wǎng)中也真是這樣嗎？21)()(iitttkn在BA無標(biāo)度網(wǎng)絡(luò)的增長過程中，節(jié)點(diǎn)的度也在發(fā)生變化并且滿足如下冪律關(guān)系。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Ana

56、lysis)Page 1555.適應(yīng)度模型n然而，在許多實(shí)際網(wǎng)絡(luò)中，節(jié)點(diǎn)的度及其增長速度并非只與該節(jié)點(diǎn)的年齡有關(guān)。n有時(shí)是與節(jié)點(diǎn)的內(nèi)在性質(zhì)有關(guān)的，如個(gè)人的交友能力，WWW站點(diǎn)的內(nèi)容和科研論文的質(zhì)量等。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1565.適應(yīng)度模型nBianconi和Barabasi把這一性質(zhì)稱為節(jié)點(diǎn)的適應(yīng)度（fitness）。n據(jù)此提出了 適應(yīng)度模型(fitness model).n并給出了該模型的構(gòu)造算法。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysi

57、s)Page 1575.適應(yīng)度模型n 其構(gòu)造算法如下：n 增長：從一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)并且連到m個(gè)已存在的節(jié)點(diǎn)上，這里mm0。每個(gè)節(jié)點(diǎn)的適應(yīng)度按概率分布 選取 。)(分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1585.適應(yīng)度模型n 其構(gòu)造算法如下：n 優(yōu)先連接：一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率 ，與節(jié)點(diǎn)i的度ki，節(jié)點(diǎn)j的度kj和適應(yīng)度之間滿足如下關(guān)系:ijjjiiikk分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page

58、 1595.適應(yīng)度模型n可見，適應(yīng)度模型與BA無標(biāo)度模型的區(qū)別在于，在適應(yīng)度模型中的優(yōu)先連接概率與節(jié)點(diǎn)的度和適應(yīng)度之積成正比，而不是僅與節(jié)點(diǎn)的度成正比。jjjiiikk分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1605.適應(yīng)度模型n這樣，在適應(yīng)度模型中，如果一個(gè)年輕的節(jié)點(diǎn)具有的較高的適應(yīng)度，那么該節(jié)點(diǎn)就有可能在隨后的網(wǎng)絡(luò)演化過程中獲取更多的邊。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1615.適應(yīng)度模型n取決于適應(yīng)度分布的形式，適應(yīng)度模型表現(xiàn)出兩類不

59、同的行為，即：如果該分布具有有限支撐（finite support），那么與原始的BA模型一樣，網(wǎng)絡(luò)具有冪律分布。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1625.適應(yīng)度模型n如果該分布具有無限支撐（infnite support），那么應(yīng)用度最高的那個(gè)點(diǎn)就會獲得占整個(gè)網(wǎng)絡(luò)總邊數(shù)的一定比例的邊數(shù)，后者是一種所謂的“贏者通吃(winner takes all)”的現(xiàn)象，類似于市場中的寡頭壟斷。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 163課堂小結(jié)n2

60、.4無標(biāo)度網(wǎng)絡(luò)模型n魯棒性和脆弱性n適應(yīng)度模型n2.5局域世界網(wǎng)絡(luò)演化模型分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1642.5局域世界演化網(wǎng)絡(luò)模型n在諸多實(shí)際的復(fù)雜網(wǎng)絡(luò)中存在著局域世界。 nBA網(wǎng)絡(luò)模型根據(jù)其優(yōu)先連接概率公式來計(jì)算每一個(gè)節(jié)點(diǎn)的優(yōu)先連接概率值，由此得到冪律分布形式的網(wǎng)絡(luò)度分布。分子生物網(wǎng)絡(luò)分析分子生物網(wǎng)絡(luò)分析(Molecular Biology Network Analysis)Page 1652.5局域世界演化網(wǎng)絡(luò)模型n然而， 在許多實(shí)際網(wǎng)絡(luò)中，由于局域世界連接性的存在，每一個(gè)節(jié)點(diǎn)都有各自的局域世界，因而