復雜網(wǎng)絡第二講

復雜網(wǎng)絡第二講

網(wǎng)絡拓撲基本模型及其性質(zhì)李凱凱規(guī)則網(wǎng)絡隨機圖小世界網(wǎng)絡模型無標度網(wǎng)絡模型局域世界演化網(wǎng)絡模型模塊性與等級網(wǎng)絡復雜網(wǎng)絡的自相似性規(guī)則網(wǎng)絡系統(tǒng)中節(jié)點及其與邊的關(guān)系是固定的。

（a）全局耦合網(wǎng)絡；（b）最近鄰耦合網(wǎng)絡；（c）星形網(wǎng)絡

全局耦合網(wǎng)絡具有最小的平均路徑長度Lgc=1和最大的聚類系數(shù)Cgc=1；最近鄰耦合網(wǎng)絡:包含N個圍成一個環(huán)的點，其中每個節(jié)點都與它左右各K/2個鄰居點相連（K為偶數(shù)），對于較大的K值，最近鄰耦合網(wǎng)絡的聚類系數(shù)為因此，這樣的網(wǎng)絡是高度聚類的。對于固定的K值，網(wǎng)絡平均路徑長度為

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

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

時產(chǎn)生一個具有性質(zhì)Q的ER隨機圖的概率為1，那么就稱幾乎每一個ER隨機圖都具有性質(zhì)Q。Erdos和Renyi的最重要的發(fā)現(xiàn)時ER隨機圖具有如下的涌現(xiàn)或相變性質(zhì)：ER隨機圖的許多重要的性質(zhì)都是突然涌現(xiàn)的。也就是說，對于任意給定的概率p，要么幾乎每一個圖都具有性質(zhì)Q，要么幾乎每一個圖都不具有該性質(zhì)。上述紐扣網(wǎng)絡，如果p大于某個臨界值，那么幾乎每一個隨機圖都是連通的。ER隨機圖的平均度是,平均路徑長度。LER為網(wǎng)絡規(guī)模的對數(shù)增長函數(shù)是典型的小世界特征。ER隨機圖的聚類系數(shù)是C=p=<k>/N《1，這意味著大規(guī)模的稀疏ER隨機圖沒有聚類特性。實際網(wǎng)絡的聚類系數(shù)要比相同規(guī)模的ER隨機圖的聚類系數(shù)要高得多。ER隨機圖的度分布可用Poission分布來表示：因此，ER隨機圖也稱為“Poission隨機圖”。小世界網(wǎng)絡模型作為從完全規(guī)則網(wǎng)絡向完全隨機圖的過渡，Watts和Strogtz于1998年引入了一個小世界網(wǎng)絡模型，稱為WS小世界模型。其構(gòu)造算法如下：①從規(guī)則圖開始：考慮一個含有N個點的最近鄰耦合網(wǎng)絡，它們圍成一個環(huán)，其中每個節(jié)點都與它左右相鄰的各K/2個節(jié)點相連，K是偶數(shù)。②隨機化重連：以概率p隨機地重連網(wǎng)絡中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網(wǎng)絡中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同節(jié)點之-間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。P=0對應于完全規(guī)則網(wǎng)絡，p=1對應于完全隨機網(wǎng)絡。具有較短的平均路徑長度又具有較高的聚類系數(shù)的網(wǎng)絡就稱為小世界網(wǎng)絡。Newman和Watts提出了NW小世界模型，用“隨機化加邊”取代WS小世界模型構(gòu)造中的“隨機化重連”。算法如下：①從規(guī)則圖開始：含有N個節(jié)點的最近鄰耦合網(wǎng)絡。②隨機化加邊：以概率P在隨機選取的一對節(jié)點之間加上一條邊。NW小世界模型中，p=0對應于原來的最近鄰耦合網(wǎng)絡，p=1對應于全局耦合網(wǎng)絡。小世界網(wǎng)絡的性質(zhì)1.聚類系數(shù)WS小世界網(wǎng)絡的聚類系數(shù)為NW小世界網(wǎng)絡的聚類系數(shù)為2.平均路徑長度其中f（u）為一普適標度函數(shù)，滿足Newman等人基于平均場方法給出了如下近似表達式：3.度分布在基于“隨機化加邊”機制的NW小世界模型中，每個節(jié)點的度至少為K，因此當時，一個隨機選取的節(jié)點的度為k的概率為：而當k<K時，P（k）=0。無標度網(wǎng)絡模型研究發(fā)現(xiàn)許多復雜網(wǎng)絡的連接度分布函數(shù)具有冪律形式，由于這類網(wǎng)絡的節(jié)點的連接度沒有明顯的特征長度，故稱為無標度網(wǎng)絡。Barabasi和Albert提出了一個無標度網(wǎng)絡模型，稱為BA模型。該模型考慮到了實際網(wǎng)絡的兩個重要特性：①增長特性；②優(yōu)先連接特性?；谶@兩個特性，BA無標度網(wǎng)絡模型構(gòu)造算法如下：①增長：從一個具有m0個節(jié)點的網(wǎng)絡開始，每次引入一個新的節(jié)點，并且連到m個已存在的節(jié)點上，這里。②優(yōu)先連接：一個新節(jié)點與一個已經(jīng)存在的節(jié)點i相連接的概率與節(jié)點i的度ki，節(jié)點j的度kj之間滿足如下關(guān)系：無標度網(wǎng)絡的性質(zhì)1.平均路徑長度，表明該網(wǎng)絡具有小世界特性。2.聚類系數(shù)3.度分布BA無標度網(wǎng)絡的度分布函數(shù)為這表明BA無標度網(wǎng)絡的度分布函數(shù)可由冪指數(shù)為3的冪律函數(shù)近似描述。冪律分布函數(shù)的無標度性質(zhì)：考慮一個概率分布函數(shù)f(x)，如果對任意給定常數(shù)a，存在常數(shù)b使得函數(shù)f(x)滿足如下“無標度條件”:f(ax)=bf(x)那么必有(假定)也就是說，冪律分布函數(shù)是唯一滿足“無標度條件”的概率分布函數(shù)。魯棒性與脆弱性假定一個網(wǎng)絡，每次從該網(wǎng)絡中移走一個節(jié)點，同時移走與該節(jié)點相連的所有邊，從而可能使得網(wǎng)絡中其他節(jié)點之間的一些路徑被中斷，如果在節(jié)點i和節(jié)點j之間有多條路徑，中斷其中一些路徑可能會使這兩個節(jié)點之間的距離增大，從而整個網(wǎng)絡的平均路徑長度也會增大，而如果節(jié)點i和節(jié)點j之間的所有路徑都被中斷，那么這兩個節(jié)點之間就不再連通了。如果在移走少量節(jié)點后網(wǎng)絡中的絕大部分節(jié)點仍是連通的，那么就稱該網(wǎng)絡對節(jié)點故障具有魯棒性。比較ER隨機圖和BA無標度網(wǎng)絡的連通性對節(jié)點去除的魯棒性，考慮兩類節(jié)點去除策略：一是隨機故障策略，即完全隨機地去除網(wǎng)絡中的一部分節(jié)點；二是蓄意攻擊策略，即從去除網(wǎng)絡中度最高的節(jié)點開始，有意識地去除網(wǎng)絡中一部分度最高的節(jié)點。無標度網(wǎng)絡對隨機圖故障具有極高的魯棒性：這種高度魯棒性來自于網(wǎng)絡度分布的極端非均勻性，然而，正是這種網(wǎng)絡度分布的非均勻性使得無標度網(wǎng)絡對蓄意攻擊具有高度的脆弱性。對隨機故障的魯棒性和對蓄意攻擊的脆弱性是無標度網(wǎng)絡的一個基本特征。事實上，科學家研究表明，“魯棒但又脆弱”是復雜系統(tǒng)的最重要和最基本的特征之一。假設(shè)去除的節(jié)點數(shù)占原始網(wǎng)絡總節(jié)點數(shù)的比例為f，可以用最大聯(lián)通子圖的相對大小S和平均路徑和長度l與f的關(guān)系來度量網(wǎng)絡的魯棒性，研究發(fā)現(xiàn)，ER隨機圖和BA無標度網(wǎng)絡之間存在及其顯著的差異性。適應度模型BA模型只能生產(chǎn)度分布冪律指數(shù)固定為3的無標度網(wǎng)絡，實際網(wǎng)絡的冪律指數(shù)則不盡相同，且大都屬于2至3的范圍內(nèi)。2000年，Jeng等人在《Nature》上發(fā)表的文章中對43種生物體組織的新陳代謝過程加以研究，他們以各種基質(zhì)（如ADP）為節(jié)點，以基質(zhì)參與的某種化學反應為邊構(gòu)建了新陳代謝的復雜網(wǎng)絡，結(jié)果顯示，這些網(wǎng)絡的度分布都服從冪律分布，冪指數(shù)在2.0~2.4之間。在BA無標度網(wǎng)絡的增長過程中，節(jié)點的度也在發(fā)生變化并且滿足如下冪律關(guān)系。其中是第i個節(jié)點在時刻t的度，是第i個節(jié)點加入到網(wǎng)絡中的時刻，上式表明，在BA無標度網(wǎng)絡中，越老的節(jié)點具有越高的度，然而，在許多實際網(wǎng)絡中，節(jié)點的度及其增長速度并非只與該節(jié)點的年齡有關(guān)，有時是與節(jié)點的內(nèi)在性質(zhì)有關(guān)的，如個人的交友能力，WWW站點的內(nèi)容和科研論文的質(zhì)量等，Bianconi和Barabasi把這一性質(zhì)稱為節(jié)點的適應度，并據(jù)此提出了適應度模型，其構(gòu)造算法如下：①增長：從一個具有m0個節(jié)點的網(wǎng)絡開始，每次引入一個新的節(jié)點并且連到m個已存在的節(jié)點上，這里。每個節(jié)點的適應度按概率分布選取。②優(yōu)先連接：一個新節(jié)點與一個已經(jīng)存在的節(jié)點i相連接的概率，與節(jié)點i的度ki，節(jié)點j的度kj和適應度之間滿足如下關(guān)系可見，適應度模型與BA無標度模型的區(qū)別在于，在適應度模型中的優(yōu)先連接概率與節(jié)點的度和適應度之積成正比，而不是僅與節(jié)點的度成正比，這樣，在適應度模型中，如果一個年輕的節(jié)點具有的較高的適應度，那么該節(jié)點就有可能在隨后的網(wǎng)絡演化過程中獲取更多的邊。

局域世界演化網(wǎng)絡模型在許多實際網(wǎng)絡中，每個節(jié)點都有各自的局域世界，研究者們建立了局域世界演化網(wǎng)絡模型，其構(gòu)造算法如下：①增長：網(wǎng)絡初始時有m0個節(jié)點和e0條邊，每次新加入一個節(jié)點和附帶的m條邊。②局域世界優(yōu)先連接：隨機地從網(wǎng)絡已有的節(jié)點中選取M個節(jié)點（），作為新加入節(jié)點的局域世界，新加入的節(jié)點根據(jù)優(yōu)先連接概率來選擇與局域世界中的m個節(jié)點相連，其中LW是由新選擇的M個節(jié)點組成。在t時刻，，因此上述局域世界演化網(wǎng)絡模型有兩個特殊情形：M=m和M=t+m0。（1）特殊情形A：M=m這時，新加入的節(jié)點與其局域世界中所有的節(jié)點相連接，這等價于BA無標度網(wǎng)絡模型中只保留增長機制而沒有優(yōu)先連接。此時，第i個節(jié)點的度的變化率為網(wǎng)絡度分布服從指數(shù)分布（2）特殊情形B：M=t+m0在這種特殊情形，每個節(jié)點的局域世界其實就是整個網(wǎng)絡，因此，局域世界模型就完全等價于BA無標度網(wǎng)絡模型。模塊性與等級網(wǎng)絡模塊（module）與模體（motif）模塊是指一組物理上或功能上連接在一起的、共同完成一個相對獨立功能的節(jié)點。模體可能是復雜網(wǎng)絡的基本模塊。網(wǎng)絡的高聚類性表明網(wǎng)絡可能包含由高度連接的節(jié)點構(gòu)成的子圖。如三角形，正方形和五角形，其中一些子圖所占的比例明顯高于同一網(wǎng)絡的完全隨機化形式中這些子圖所占的比例。這些子圖就稱為模體。判斷實際網(wǎng)絡中的一個子圖i是否為模體的依據(jù)如下：①該子圖在與實際網(wǎng)絡對應的隨機化網(wǎng)絡中出現(xiàn)的次數(shù)大于它在實際網(wǎng)絡中出現(xiàn)的次數(shù)的概率是很小的，通常要求這個概率要小于某個閾值P（如P=0.01）②該子圖在實際網(wǎng)絡中出現(xiàn)的次數(shù)Nreali不小于某個下限U（如U=4）.③該子圖在實際網(wǎng)絡中出現(xiàn)的次數(shù)Nreali明顯高于它在隨機化網(wǎng)絡中出現(xiàn)的次數(shù)Nrandi,一般要求Nreali>1.1Nrandi

。等級網(wǎng)絡

等級網(wǎng)絡具有與網(wǎng)絡規(guī)模無關(guān)的較高的聚類系數(shù)，等級模塊性的一個最重要的量化標志是節(jié)點聚類系數(shù)服從冪律。這表明度很小的節(jié)點具有較高的聚類系數(shù)，相反度很高的節(jié)點具有低的聚類系數(shù)，其作用只是把不同的模塊連接起來。ER隨機圖和BA無標度網(wǎng)絡都不具有等級拓撲，在這兩類網(wǎng)絡中節(jié)點的聚類系數(shù)C（k）與該節(jié)點的度k無關(guān)。復雜網(wǎng)絡的自相似性等級網(wǎng)絡看上去有一個明顯的特征，就是該網(wǎng)絡部分與整體具有很明顯的相似性，即自相似性，正是分形的一個基本特征。

Sierpinski三角形：復雜網(wǎng)絡的小世界特征意味著網(wǎng)絡的平均路徑長度l可以用網(wǎng)絡規(guī)模N的對數(shù)函數(shù)來表示，即，等價于其中L0表示特征長度，上式意味著網(wǎng)絡規(guī)模是網(wǎng)絡平均路徑長度的指數(shù)函數(shù)。而自相似性要求滿足某種冪律關(guān)系，然而，Song等人的研究指出，許多實際網(wǎng)絡，包括WWW，蛋白質(zhì)交互作用網(wǎng)絡和細胞網(wǎng)絡等，在某種長度-標度下確實是自相似的。與自相似性密切相關(guān)的一個概念是分數(shù)維，計算自相似分形的維數(shù)的一種常用的方法是盒記數(shù)法?；舅枷胧怯眠呴L為lB的盒子來覆蓋該圖形，并統(tǒng)計完全覆蓋該圖形需要的最少的盒子數(shù)NB(lB)圖形維數(shù)的近似計算公式為等價地有冪律標度公式例：對于Sierpinski三角形，假設(shè)這個大三角形的邊長為1，如果用邊長為1/2的正方形覆蓋Sierpinski三角形，那么需要3個正方形，如果用邊長為1/4的正