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

復(fù)雜網(wǎng)絡(luò)第二講第一頁，共四十三頁，2022年，8月28日規(guī)則網(wǎng)絡(luò)隨機(jī)圖小世界網(wǎng)絡(luò)模型無標(biāo)度網(wǎng)絡(luò)模型局域世界演化網(wǎng)絡(luò)模型模塊性與等級(jí)網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的自相似性第二頁，共四十三頁，2022年，8月28日規(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)絡(luò)具有最小的平均路徑長度Lgc=1和最大的聚類系數(shù)Cgc=1；第三頁，共四十三頁，2022年，8月28日最近鄰耦合網(wǎng)絡(luò):包含N個(gè)圍成一個(gè)環(huán)的點(diǎn)，其中每個(gè)節(jié)點(diǎn)都與它左右各K/2個(gè)鄰居點(diǎn)相連（K為偶數(shù)），對(duì)于較大的K值，最近鄰耦合網(wǎng)絡(luò)的聚類系數(shù)為因此，這樣的網(wǎng)絡(luò)是高度聚類的。對(duì)于固定的K值，網(wǎng)絡(luò)平均路徑長度為

星形耦合網(wǎng)絡(luò)：有一個(gè)中心點(diǎn)，其余N-1個(gè)點(diǎn)都只與這個(gè)中心點(diǎn)連接，其平均路徑長度為

聚類系數(shù)為第四頁，共四十三頁，2022年，8月28日隨機(jī)圖隨機(jī)圖是與規(guī)則網(wǎng)絡(luò)相反的網(wǎng)絡(luò)，一個(gè)典型模型是Erdos和Renyi于40多年前開始研究的隨機(jī)圖模型。假設(shè)有大量的紐扣（N》1）散落在地上，并以相同的概率p給每對(duì)紐扣系上一根線。這樣就會(huì)得到一個(gè)有N個(gè)節(jié)點(diǎn)，約pN(N-1)/2條邊的ER隨機(jī)圖的實(shí)例。第五頁，共四十三頁，2022年，8月28日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ī)圖的概率為1，那么就稱幾乎每一個(gè)ER隨機(jī)圖都具有性質(zhì)Q。Erdos和Renyi的最重要的發(fā)現(xiàn)時(shí)ER隨機(jī)圖具有如下的涌現(xiàn)或相變性質(zhì)：ER隨機(jī)圖的許多重要的性質(zhì)都是突然涌現(xiàn)的。也就是說，對(duì)于任意給定的概率p，要么幾乎每一個(gè)圖都具有性質(zhì)Q，要么幾乎每一個(gè)圖都不具有該性質(zhì)。上述紐扣網(wǎng)絡(luò)，如果p大于某個(gè)臨界值，那么幾乎每一個(gè)隨機(jī)圖都是連通的。第六頁，共四十三頁，2022年，8月28日ER隨機(jī)圖的平均度是,平均路徑長度。LER為網(wǎng)絡(luò)規(guī)模的對(duì)數(shù)增長函數(shù)是典型的小世界特征。ER隨機(jī)圖的聚類系數(shù)是C=p=<k>/N《1，這意味著大規(guī)模的稀疏ER隨機(jī)圖沒有聚類特性。實(shí)際網(wǎng)絡(luò)的聚類系數(shù)要比相同規(guī)模的ER隨機(jī)圖的聚類系數(shù)要高得多。ER隨機(jī)圖的度分布可用Poission分布來表示：因此，ER隨機(jī)圖也稱為“Poission隨機(jī)圖”。第七頁，共四十三頁，2022年，8月28日小世界網(wǎng)絡(luò)模型作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過渡，Watts和Strogtz于1998年引入了一個(gè)小世界網(wǎng)絡(luò)模型，稱為WS小世界模型。其構(gòu)造算法如下：①從規(guī)則圖開始：考慮一個(gè)含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2個(gè)節(jié)點(diǎn)相連，K是偶數(shù)。②隨機(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)都不能有邊與自身相連。P=0對(duì)應(yīng)于完全規(guī)則網(wǎng)絡(luò)，p=1對(duì)應(yīng)于完全隨機(jī)網(wǎng)絡(luò)。第八頁，共四十三頁，2022年，8月28日具有較短的平均路徑長度又具有較高的聚類系數(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ī)選取的一對(duì)節(jié)點(diǎn)之間加上一條邊。

NW小世界模型中，p=0對(duì)應(yīng)于原來的最近鄰耦合網(wǎng)絡(luò)，p=1對(duì)應(yīng)于全局耦合網(wǎng)絡(luò)。第九頁，共四十三頁，2022年，8月28日小世界網(wǎng)絡(luò)的性質(zhì)1.聚類系數(shù)WS小世界網(wǎng)絡(luò)的聚類系數(shù)為NW小世界網(wǎng)絡(luò)的聚類系數(shù)為2.平均路徑長度第十頁，共四十三頁，2022年，8月28日其中f（u）為一普適標(biāo)度函數(shù)，滿足Newman等人基于平均場(chǎng)方法給出了如下近似表達(dá)式：3.度分布在基于“隨機(jī)化加邊”機(jī)制的NW小世界模型中，每個(gè)節(jié)點(diǎn)的度至少為K，因此當(dāng)時(shí)，一個(gè)隨機(jī)選取的節(jié)點(diǎn)的度為k的概率為：而當(dāng)k<K時(shí)，P（k）=0。第十一頁，共四十三頁，2022年，8月28日無標(biāo)度網(wǎng)絡(luò)模型研究發(fā)現(xiàn)許多復(fù)雜網(wǎng)絡(luò)的連接度分布函數(shù)具有冪律形式，由于這類網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度沒有明顯的特征長度，故稱為無標(biāo)度網(wǎng)絡(luò)。

Barabasi和Albert提出了一個(gè)無標(biāo)度網(wǎng)絡(luò)模型，稱為BA模型。該模型考慮到了實(shí)際網(wǎng)絡(luò)的兩個(gè)重要特性：①增長特性；②優(yōu)先連接特性?；谶@兩個(gè)特性，BA無標(biāo)度網(wǎng)絡(luò)模型構(gòu)造算法如下：①增長：從一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)，并且連到m個(gè)已存在的節(jié)點(diǎn)上，這里。②優(yōu)先連接：一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率與節(jié)點(diǎn)i的度ki，節(jié)點(diǎn)j的度kj之間滿足如下關(guān)系：第十二頁，共四十三頁，2022年，8月28日第十三頁，共四十三頁，2022年，8月28日無標(biāo)度網(wǎng)絡(luò)的性質(zhì)1.平均路徑長度，表明該網(wǎng)絡(luò)具有小世界特性。2.聚類系數(shù)3.度分布

BA無標(biāo)度網(wǎng)絡(luò)的度分布函數(shù)為這表明BA無標(biāo)度網(wǎng)絡(luò)的度分布函數(shù)可由冪指數(shù)為3的冪律函數(shù)近似描述。第十四頁，共四十三頁，2022年，8月28日冪律分布函數(shù)的無標(biāo)度性質(zhì)：考慮一個(gè)概率分布函數(shù)f(x)，如果對(duì)任意給定常數(shù)a，存在常數(shù)b使得函數(shù)f(x)滿足如下“無標(biāo)度條件”:f(ax)=bf(x)

那么必有(假定)

也就是說，冪律分布函數(shù)是唯一滿足“無標(biāo)度條件”的概率分布函數(shù)。第十五頁，共四十三頁，2022年，8月28日第十六頁，共四十三頁，2022年，8月28日魯棒性與脆弱性假定一個(gè)網(wǎng)絡(luò)，每次從該網(wǎng)絡(luò)中移走一個(gè)節(jié)點(diǎn)，同時(shí)移走與該節(jié)點(diǎn)相連的所有邊，從而可能使得網(wǎng)絡(luò)中其他節(jié)點(diǎn)之間的一些路徑被中斷，如果在節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有多條路徑，中斷其中一些路徑可能會(huì)使這兩個(gè)節(jié)點(diǎn)之間的距離增大，從而整個(gè)網(wǎng)絡(luò)的平均路徑長度也會(huì)增大，而如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的所有路徑都被中斷，那么這兩個(gè)節(jié)點(diǎn)之間就不再連通了。如果在移走少量節(jié)點(diǎn)后網(wǎng)絡(luò)中的絕大部分節(jié)點(diǎn)仍是連通的，那么就稱該網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)故障具有魯棒性。第十七頁，共四十三頁，2022年，8月28日第十八頁，共四十三頁，2022年，8月28日比較ER隨機(jī)圖和BA無標(biāo)度網(wǎng)絡(luò)的連通性對(duì)節(jié)點(diǎn)去除的魯棒性，考慮兩類節(jié)點(diǎn)去除策略：一是隨機(jī)故障策略，即完全隨機(jī)地去除網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)；二是蓄意攻擊策略，即從去除網(wǎng)絡(luò)中度最高的節(jié)點(diǎn)開始，有意識(shí)地去除網(wǎng)絡(luò)中一部分度最高的節(jié)點(diǎn)。第十九頁，共四十三頁，2022年，8月28日第二十頁，共四十三頁，2022年，8月28日第二十一頁，共四十三頁，2022年，8月28日第二十二頁，共四十三頁，2022年，8月28日無標(biāo)度網(wǎng)絡(luò)對(duì)隨機(jī)圖故障具有極高的魯棒性：這種高度魯棒性來自于網(wǎng)絡(luò)度分布的極端非均勻性，然而，正是這種網(wǎng)絡(luò)度分布的非均勻性使得無標(biāo)度網(wǎng)絡(luò)對(duì)蓄意攻擊具有高度的脆弱性。對(duì)隨機(jī)故障的魯棒性和對(duì)蓄意攻擊的脆弱性是無標(biāo)度網(wǎng)絡(luò)的一個(gè)基本特征。事實(shí)上，科學(xué)家研究表明，“魯棒但又脆弱”是復(fù)雜系統(tǒng)的最重要和最基本的特征之一。假設(shè)去除的節(jié)點(diǎn)數(shù)占原始網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例為f，可以用最大聯(lián)通子圖的相對(duì)大小S和平均路徑和長度l與f的關(guān)系來度量網(wǎng)絡(luò)的魯棒性，研究發(fā)現(xiàn)，ER隨機(jī)圖和BA無標(biāo)度網(wǎng)絡(luò)之間存在及其顯著的差異性。第二十三頁，共四十三頁，2022年，8月28日第二十四頁，共四十三頁，2022年，8月28日適應(yīng)度模型BA模型只能生產(chǎn)度分布冪律指數(shù)固定為3的無標(biāo)度網(wǎng)絡(luò)，實(shí)際網(wǎng)絡(luò)的冪律指數(shù)則不盡相同，且大都屬于2至3的范圍內(nèi)。

2000年，Jeng等人在《Nature》上發(fā)表的文章中對(duì)43種生物體組織的新陳代謝過程加以研究，他們以各種基質(zhì)（如ADP）為節(jié)點(diǎn)，以基質(zhì)參與的某種化學(xué)反應(yīng)為邊構(gòu)建了新陳代謝的復(fù)雜網(wǎng)絡(luò)，結(jié)果顯示，這些網(wǎng)絡(luò)的度分布都服從冪律分布，冪指數(shù)在2.0~2.4之間。第二十五頁，共四十三頁，2022年，8月28日在BA無標(biāo)度網(wǎng)絡(luò)的增長過程中，節(jié)點(diǎn)的度也在發(fā)生變化并且滿足如下冪律關(guān)系。其中是第i個(gè)節(jié)點(diǎn)在時(shí)刻t的度，是第i個(gè)節(jié)點(diǎn)加入到網(wǎng)絡(luò)中的時(shí)刻，上式表明，在BA無標(biāo)度網(wǎng)絡(luò)中，越老的節(jié)點(diǎn)具有越高的度，然而，在許多實(shí)際網(wǎng)絡(luò)中，節(jié)點(diǎn)的度及其增長速度并非只與該節(jié)點(diǎn)的年齡有關(guān)，有時(shí)是與節(jié)點(diǎn)的內(nèi)在性質(zhì)有關(guān)的，如個(gè)人的交友能力，WWW站點(diǎn)的內(nèi)容和科研論文的質(zhì)量等，Bianconi和Barabasi把這一性質(zhì)稱為節(jié)點(diǎn)的適應(yīng)度，并據(jù)此提出了適應(yīng)度模型，其構(gòu)造算法如下：第二十六頁，共四十三頁，2022年，8月28日①增長：從一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)并且連到m個(gè)已存在的節(jié)點(diǎn)上，這里。每個(gè)節(jié)點(diǎn)的適應(yīng)度按概率分布選取。②優(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)系可見，適應(yīng)度模型與BA無標(biāo)度模型的區(qū)別在于，在適應(yīng)度模型中的優(yōu)先連接概率與節(jié)點(diǎn)的度和適應(yīng)度之積成正比，而不是僅與節(jié)點(diǎn)的度成正比，這樣，在適應(yīng)度模型中，如果一個(gè)年輕的節(jié)點(diǎn)具有的較高的適應(yīng)度，那么該節(jié)點(diǎn)就有可能在隨后的網(wǎng)絡(luò)演化過程中獲取更多的邊。

第二十七頁，共四十三頁，2022年，8月28日局域世界演化網(wǎng)絡(luò)模型在許多實(shí)際網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都有各自的局域世界，研究者們建立了局域世界演化網(wǎng)絡(luò)模型，其構(gòu)造算法如下：①增長：網(wǎng)絡(luò)初始時(shí)有m0個(gè)節(jié)點(diǎn)和e0條邊，每次新加入一個(gè)節(jié)點(diǎn)和附帶的m條邊。②局域世界優(yōu)先連接：隨機(jī)地從網(wǎng)絡(luò)已有的節(jié)點(diǎn)中選取M個(gè)節(jié)點(diǎn)（），作為新加入節(jié)點(diǎn)的局域世界，新加入的節(jié)點(diǎn)根據(jù)優(yōu)先連接概率來選擇與局域世界中的m個(gè)節(jié)點(diǎn)相連，其中LW是由新選擇的M個(gè)節(jié)點(diǎn)組成。第二十八頁，共四十三頁，2022年，8月28日在t時(shí)刻，，因此上述局域世界演化網(wǎng)絡(luò)模型有兩個(gè)特殊情形：M=m和M=t+m0。（1）特殊情形A：M=m

這時(shí)，新加入的節(jié)點(diǎn)與其局域世界中所有的節(jié)點(diǎn)相連接，這等價(jià)于BA無標(biāo)度網(wǎng)絡(luò)模型中只保留增長機(jī)制而沒有優(yōu)先連接。此時(shí)，第i個(gè)節(jié)點(diǎn)的度的變化率為網(wǎng)絡(luò)度分布服從指數(shù)分布第二十九頁，共四十三頁，2022年，8月28日（2）特殊情形B：M=t+m0

在這種特殊情形，每個(gè)節(jié)點(diǎn)的局域世界其實(shí)就是整個(gè)網(wǎng)絡(luò)，因此，局域世界模型就完全等價(jià)于BA無標(biāo)度網(wǎng)絡(luò)模型。第三十頁，共四十三頁，2022年，8月28日模塊性與等級(jí)網(wǎng)絡(luò)模塊（module）與模體（motif）模塊是指一組物理上或功能上連接在一起的、共同完成一個(gè)相對(duì)獨(dú)立功能的節(jié)點(diǎn)。模體可能是復(fù)雜網(wǎng)絡(luò)的基本模塊。網(wǎng)絡(luò)的高聚類性表明網(wǎng)絡(luò)可能包含由高度連接的節(jié)點(diǎn)構(gòu)成的子圖。如三角形，正方形和五角形，其中一些子圖所占的比例明顯高于同一網(wǎng)絡(luò)的完全隨機(jī)化形式中這些子圖所占的比例。這些子圖就稱為模體。第三十一頁，共四十三頁，2022年，8月28日判斷實(shí)際網(wǎng)絡(luò)中的一個(gè)子圖i是否為模體的依據(jù)如下：①該子圖在與實(shí)際網(wǎng)絡(luò)對(duì)應(yīng)的隨機(jī)化網(wǎng)絡(luò)中出現(xiàn)的次數(shù)大于它在實(shí)際網(wǎng)絡(luò)中出現(xiàn)的次數(shù)的概率是很小的，通常要求這個(gè)概率要小于某個(gè)閾值P（如P=0.01）②該子圖在實(shí)際網(wǎng)絡(luò)中出現(xiàn)的次數(shù)Nreali不小于某個(gè)下限U（如U=4）.③該子圖在實(shí)際網(wǎng)絡(luò)中出現(xiàn)的次數(shù)Nreali明顯高于它在隨機(jī)化網(wǎng)絡(luò)中出現(xiàn)的次數(shù)Nrandi,一般要求Nreali>1.1Nrandi。第三十二頁，共四十三頁，2022年，8月28日第三十三頁，共四十三頁，2022年，8月28日等級(jí)網(wǎng)絡(luò)第三十四頁，共四十三頁，2022年，8月28日

等級(jí)網(wǎng)絡(luò)具有與網(wǎng)絡(luò)規(guī)模無關(guān)的較高的聚類系數(shù)，等級(jí)模塊性的一個(gè)最重要的量化標(biāo)志是節(jié)點(diǎn)聚類系數(shù)服從冪律。這表明度很小的節(jié)點(diǎn)具有較高的聚類系數(shù)，相反度很高的節(jié)點(diǎn)具有低的聚類系數(shù)，其作用只是把不同的模塊連接起來。

ER隨機(jī)圖和BA無標(biāo)度網(wǎng)絡(luò)都不具有等級(jí)拓?fù)?，在這兩類網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類系數(shù)C（k）與該節(jié)點(diǎn)的度k無關(guān)。第三十五頁，共四十三頁，2022年，8月28日復(fù)雜網(wǎng)絡(luò)的自相似性等級(jí)網(wǎng)絡(luò)看上去有一個(gè)明顯的特征，就是該網(wǎng)絡(luò)部分與整體具有很明顯的相似性，即自相似性，正是分形的一個(gè)基本特征。

Sierpinski三角形：第三十六頁，共四十三頁，2022年，8月28日復(fù)雜網(wǎng)絡(luò)的小世界特征意味著網(wǎng)絡(luò)的平均路徑長度l可以用網(wǎng)絡(luò)規(guī)模N的對(duì)數(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í)是自相似的。第三十七頁，共四十三頁，2022年，8月28日與自相似性密切相關(guān)的一個(gè)概念是分?jǐn)?shù)維，計(jì)算自相似分形的維數(shù)的一種常用的方法是盒記數(shù)法?；舅枷胧怯眠呴L為lB的盒子來覆蓋該圖形，并統(tǒng)計(jì)完全覆蓋該圖形需要的最少的盒子數(shù)NB(lB)

圖形維數(shù)的近似計(jì)算公式為等價(jià)地有冪律標(biāo)度公式第三十八頁，共四十三頁，2022年，8月28日例：對(duì)于Sierpinski三角形，假設(shè)這個(gè)大三角形的邊長為1，如果用邊長為1/2的正方形覆蓋Sierpinski三角形，那么需要3個(gè)正方形，如果用邊長為1/4的正方形覆蓋Sierpinski三角形，需要