無尺度網絡

圖1.有1000個節點的BA模型網絡。

在網絡理論中，無尺度網絡（Scale-free network，或稱無標度網絡）是帶有一類特性的複雜網絡，其典型特徵是在網絡中的大部分節點只和很少節點連接，而有極少的節點與非常多的節點連接。這種關鍵的節點（稱為「樞紐」或「集散節點」）的存在使得無尺度網絡對意外故障有強大的承受能力，但面對協同性攻擊時則顯得脆弱。現實中的許多網絡都帶有無尺度的特性，例如因特網、金融系統網絡、社會人際網絡等等。

源起

圖2.無尺度網絡與隨機網絡的對比：(a)中的隨機網絡，大部分節點都連出2到3條邊，0條與1條邊的和4條邊的都很少，而(b)中的無尺度網絡，大部分節點連1條邊，少數節點（紅色）連有大量邊。

無尺度網絡的概念是隨着對複雜網絡的研究而出現的。「網絡」其實就是數學中圖論研究的圖，由一群頂點以及它們之間所連的邊構成。在網絡理論中則換一套說法，用「節點」代替「頂點」，用「連結」代替「邊」。複雜網絡的概念，是用來描述由大量節點以及這些節點之間錯綜複雜的聯繫所構成的網絡。這樣的網絡會出現簡單網絡中沒有的特殊拓撲特性。

自二十世紀60年代開始，對複雜網絡的研究主要集中在隨機網絡上。隨機網絡，又稱隨機圖，是指通過隨機過程製造出的複雜網絡。最典型的隨機網絡是保羅·埃爾德什和阿爾弗雷德·雷尼提出的ER模型。ER模型是基於一種「自然」的構造方法：假設有$n$個節點，並假設每對節點之間相連的可能性都是常數$0<p<1$。這樣構造出的網絡就是ER模型網絡。科學家們最初使用這種模型來解釋現實生活中的網絡。

ER模型隨機網絡有一個重要特性，就是雖然節點之間的連接是隨機形成的，但最後產生的網絡的度分布是高度平等的。度分布是指節點的度的分布情況。在網絡中，每個節點都與另外某些節點相連，這種連接的數目叫做這個節點的度。在網絡中隨機抽取一個節點，它的度是多少呢？這個概率分布就稱為節點的度分布。

在一般的隨機網絡（如ER模型）中，大部分的節點的度都集中在某個特殊值附近，成鐘形的泊松分布規律（見圖3）。偏離這個特定值的概率呈指數性下降，遠大於或遠小於這個值的可能都是微乎其微的，就如一座城市中成年居民的身高大致的分布一樣。然而在1998年，Albert-László Barabási、Réka Albert等人合作進行一項描繪萬維網的研究時，發現通過超鏈接與網頁、文件所構成的萬維網網絡並不是如一般的隨機網絡一樣，有着均勻的度分布。他們發現，萬維網是由少數高連接性的頁面串聯起來的。絕大多數（超過80%）的網頁只有不超過4個超鏈接，但極少數頁面（不到總頁面數的萬分之一）卻擁有極多的鏈接，超過1000個，有一份文件甚至與超過200萬個其他頁面相連。與居民身高的例子作類比的話，就是說大多數的節點都是「矮個子」，而卻又有極少數的身高百丈的「巨人」。Barabási等人將其稱為「無尺度」網絡。

描述與定義

圖3.隨機網絡的度（a）集中在某個平均值$d_{c}$附近，而無尺度網絡的度分布（b）則遵守冪律分布

無尺度網絡的特性，在於其度分布沒有一個特定的平均值指標，即大多數節點的度在此附近。在研究這個網絡的度分布時，Barabási等人發現其遵守冪律分布（也稱為帕累托分布），也就是說，隨機抽取一個節點，它的度$d$是自然數$k$的概率：

$\mathbb {P} (d=k)\propto {\frac {1}{k^{\gamma }}}$

也就是說$d=k$ 的概率正比於$k$ 的某個冪次（一般是負的，記為$-\gamma$）。因此$k$越大，$d=k$ 的概率就越低。然而這個概率隨$k$增大而下降的「速度」是比較緩慢的：在一般的隨機網絡中，下降的速度是指數性的，而在無尺度網絡中只是以多項式類的速度下降。

在現實中許多大規模的無尺度網絡中，度分布的$\gamma$值介於2與3之間。在對數坐標系中，度分布將會是一條斜率介於-2至-3之間的直線。如左下圖中，橫坐標為節點的度，從$10^{0}$一直到$10^{3}$；縱坐標為找到這樣的節點的概率從$10^{-8}$一直到$10^{0}$。最高度數的節點有882條連接。所有的藍點大致成一條直線分布（綠色的直線）。

度-度相關性

圖4.200,000個節點的無尺度網絡的度分佈（對數坐標）

僅僅是將度分布的冪律分布作為無尺度網絡的定義有其不夠完善之處。由於冪律分布是方差可能無窮的高可變分布，對於度分布是同一個冪律分布的不同網絡，其拓撲結構和特性可能存在巨大的差異。2005年，Lun Li和大衛·阿爾德森（David Alderson）等人在論文《邁向無標度圖的理論》（Towards a Theory of Scale Free Graphs）中提出了一種補充性的標度性測度。設$G(D)$為所有具有（依照冪律分布的）度分布$D=(d_{1},d_{2},\cdots )$的網絡$g$的集合，對於其中每一個網絡$g\in G(D)$，定義度-度相關數：

$s(g)=\sum _{(i,j)\in \epsilon (g)}d_{i}d_{j}.$

其中$\epsilon (g)$表示$g$中所有連接的集合。根據排序原理，如果度數大的點之間相互連接的話，那麼$s(g)$會比較大。設$s_{max}$為最大的，那麼定義度-度相關係數：

$S(g)={\frac {s(g)}{s_{max}}}$

度-度相關係數$S(g)$介於0與1之間。$S(g)$越靠近1，則稱此網絡$g$「無尺度」的，$S(g)$靠近0，則稱$g$是「富尺度」的。在此定義下，無尺度網絡中的節點度數分布特徵體現了自相似的性質，而凸顯了「無尺度」的特徵，與富尺度網絡之間有相當的差異。

例子

不少現實中的網絡結構都屬於無尺度網絡，或者有無尺度的特性。以下是一些無尺度網絡的例子：

網絡	節點	連接
電影演員網絡	演員	出演同一部電影
萬維網	網頁	超鏈接
因特網	路由器	物理連接
蛋白質相互作用網絡	蛋白質	蛋白質之間的相互作用關係
金融網絡	金融機構	借貸關係
美國飛機航班網絡	機場	飛機航線

BA模型

圖5.製造BA模型的過程：每次增加一個節點，兩個連接

Albert-László Barabási與Réka Albert在1999年的論文中提出了一個模型來解釋複雜網絡的無尺度特性，稱為BA模型。這個模型基於兩個假設：

• 增長模式：不少現實網絡是不斷擴大不斷增長而來的，例如互聯網中新網頁的誕生，人際網絡中新朋友的加入，新的論文的發表，航空網絡中新機場的建造等等。
• 優先連接模式：新的節點在加入時會傾向於與有更多連接的節點相連，例如新網頁一般會有到知名的網絡站點的連接，新加入社群的人會想與社群中的知名人士結識，新的論文傾向於引用已被廣泛引用的著名文獻，新機場會優先考慮建立與大機場之間的航線等等。

在這種假設下，BA模型的具體構造為：

1. 增長：從一個較小的網絡$G_{0}$開始（這個網絡有$n_{0}$個節點，$E_{0}$條邊），逐步加入新的節點，每次加入一個。
2. 連接：假設原來的網絡已經有$n$個節點（$s_{1},s_{2},\cdots ,s_{n}$）。在某次新加入一個節點$s_{n+1}$時，從這個新節點向原有的$n$個節點連出$m<n_{0}$個連結。
3. 優先連接：連接方式為優先考慮高度數的節點。對於某個原有節點$s_{i}$（$1\leqslant i\leqslant n$），將其在原網絡中的度數記作$d_{i}$，那麼新節點與之相連的概率$\mathbb {P} _{i}$為：

   $\mathbb {P} _{i}={\frac {d_{i}}{\sum _{j=1}^{n}d_{j}}}$

這樣，在經過$t$次之後，得到的新網絡有$n_{0}+t$個節點，一共有$E_{0}+mt$條邊。

分析BA模型網絡的漸近度分布（當節點數量很大時的度分布）主要有連續場理論、主方程法和速率方程法。這三種方法得到的漸近結果都是相同的。2001年，Béla Bollobás證明了在節點數量很大時，BA模型網絡的度分布遵從$\gamma =3$的冪律分布。之後，其它的無尺度網絡模型也開始被提出。

其它無尺度模型

BA模型成功的為無尺度網絡找到了一個簡單而合理的形成機制。然而，BA模型也有其自身的局限。例如，它只能描述$\gamma =3$的無尺度網絡，對於真實網絡的一些非冪律特徵如指數截斷（exponential cutoff）、小變量飽和（saturation of small variables）等無法描述。因此，各種BA模型的推廣、變化版本開始出現。Bollobás在2001年提出了線性弦圖模型（LCD模型），允許節點自己與自己相連。而後又出現了只允許重複連線而不允許自連線的模型與不允許重複連線、自連線而是在選中的舊節點的鄰域隨機聯線的模型。

適應度模型

在BA模型的製造過程中，人們發現，存在越久的節點具有越高的度數。然而，現實生活的網絡中並非存在越久的元素就能有更多的聯繫。BA模型並沒有包括「後起之秀」的現象。於是，出現了基於BA模型的適應度模型。適應度模型主要是修正了優先連接的機制，對每個節點加上一個吸引因子$\mu _{i}$，這樣新節點的相連概率改正為：

$\mathbb {P} _{i}={\frac {\mu _{i}d_{i}}{\sum _{j=1}^{n}\mu _{j}d_{j}}}$

局域世界演化模型

另一種基於BA模型的推廣版本是局域世界演化模型。這個模型假設每個新節點在引入時並不能在全域進行優先連接。比如說一家新上市的公司可能只會與同地區或同國家的公司展開貿易聯繫，居民搬入新社區時只會與同一幢樓的人開始認識等等。局域世界演化模型將BA模型優先連接的機制改為：新加入的節點時，先選擇全部節點的一部分（隨機選取的$M$個節點）作為局域世界，然後再在局域世界中進行優先連接。模擬結果指出，當$M$從$m$變化到$n_{0}+t$時，產生的網絡從服從指數分布逐漸過渡到服從冪律分布。

複製模型

在BA模型中，度分布實際上是和增長的時間$t$（或說增長次數）相關的，只是在$t$十分大時近似於度分布。複製模型是一個與增長時間無關的模型。複製模型的做法是每次隨機地「複製」一個原有的節點：即隨機選定一個節點$i$，再加入一個新節點，然後新節點按照$i$與其它舊節點連接的方式與舊節點相連，最後與$i$也相連。

分層模型

主條目：分層網絡

圖6.分層網絡構造過程，n為模體級數，綠色為根節點

2001年，Barabási提出了第一個確定性的分層網絡模型。這個模型是為了解釋生物學中$\gamma \approx 2.2$的代謝網絡。分層模型的想法是從模體（motif）出發，通過自相似的層次疊加而得到複雜網絡。這種思想類似於分數維圖形。Barabási的模型是：

1. 建立一個根節點，以及兩個一級節點，並分別於根節點相連，這形成一個一級模體（右圖6中n=1的階段）；
2. 以一個一級模體作為根模體，再建立兩個一級模體，將它們的一級節點（一共4個）與根模體的根節點相連，這樣得到一個二級模體（右圖6中n=2的階段）；
3. 對二級模體重複前一步的操作（見右圖n=3的階段）。

圖7.偽分形圖構造過程，第一步為紅邊，第二步為粉邊，第三部為綠邊

這樣形成的網絡是無尺度網絡，Barabási算出它的$\scriptstyle \gamma ={\frac {\log {3}}{\log {2}}}$。後來有使用5節點4連結作為模體，得到$\gamma =1$，而4節點3連結作為模體得到$\scriptstyle \gamma =1+{\frac {\log {4}}{\log {3}}}\approx 2.26$，近似於代謝網絡。需要注意的是此模型中不少度數是0概率的，所以需要使用補分布繞過。類似的確定性模型還有偽分形圖（pseudofractal scale-free network）以及阿波羅模型（Apollonian network）。

無尺度網絡的阿喀琉斯之踵

2000年7月27日，《自然》雜誌的封面文章標題是《因特網的阿喀琉斯之踵》（Achilles' Heel of the Internet）。阿喀琉斯是古希臘神話中的英雄，他出生後，他的母親捏着他的腳踝將他浸泡在冥河中，從此他的身體刀槍不入，只有踵部沒被浸到，是為其致命弱點。因此如今「阿喀琉斯之踵」常被用來稱呼一個系統的致命缺陷。這篇文章中從因特網的無尺度特性出發，探討它對意外故障的承受能力。

假設在一個網絡中移除一個節點，以及與其相關的連接，那麼原網絡中的其他點也可能受到影響：原本相連的兩個節點可能不再相連；即使相連，從其中一處到另一處可能需要經過更多的路途。總的來說，網絡的連通性降低了。文章比較了ER隨機網絡模型與BA模型在移除少量節點時對網絡連通性的影響。這個影響主要使用最大連通子圖的大小$S$與平均路徑長度$l$來衡量。在執行「隨機攻擊策略」，也就是在網絡中隨機地去除一些節點時，無尺度網絡的$S$比隨機網絡下降慢得多，$l$的增長也緩慢得多。但是在執行「蓄意攻擊策略」，也就是選擇移除連接度最高的節點時，則會得到相反的結果。受到隨機攻擊的隨機圖會分裂成幾個較小的子圖，而無尺度網絡則有很大概率保持連通；然而面對蓄意攻擊（或稱協同攻擊）時，只需要移除5-10%的高於5度的節點，就能徹底癱瘓無尺度網絡。

流行病臨界值

流行病或網絡病毒在複雜網絡中的傳播也是複雜網絡研究的方向之一。在均勻網絡如ER模型隨機網絡或小世界網絡中，如果考慮易感（S）→感染（I）→易感（S）的SIS模型，那麼存在一個與網絡特性相關的臨界值，當有效傳播率高於這個臨界值的時候，傳染病會在網絡中傳播並穩定在某個恆定密度上（激活相態）。而當有效傳播率低於這個臨界值時，傳染病會很快逐漸消亡（吸收相態）。對於無尺度網絡，由於度分布不均勻，臨界值比較小。對於BA模型，臨界值為0。也就是說，只要有效傳播率大於0，病毒就能有效傳播並達到穩定。而對於有限規模的無標度網絡，臨界值大於0，但會在均勻網絡的十分之一左右。因此，無標度網絡對於病毒傳播的抵抗性較均勻網絡脆弱得多。

由於無尺度網絡應對流行病感染的脆弱性，人們提出不同的免疫策略來彌補。主要研究的免疫策略有三種：隨機免疫、選擇免疫與熟人免疫。

隨機免疫

隨機免疫是在網絡中隨機抽取一部分節點進行免疫。研究表明，採取這種策略的話，需要對網絡中幾乎所有的節點都進行免疫才能保證最終消滅傳染病。

選擇免疫

選擇免疫是在網絡中抽取度最大的節點進行免疫。就BA模型而言，採取這種策略的話，即使有效傳播率變化，也可以只免疫很小一部分節點就保證消滅傳染病。

熟人免疫

由於選擇免疫需要知道全局節點的度數情況，才能找到度數最大節點進行免疫，這在面對互聯網等龐大的複雜網絡時會導致難以操作。熟人免疫採取的是隨機抽取一部分節點，然後對每個節點隨機選一個與之相連的「鄰居」節點來進行免疫。由於在無尺度網絡中，度大的節點可以與非常多的節點相連，因此選擇「鄰居」免疫的話，碰到度大節點的概率會比碰到度小節點的概率大得多。所以熟人免疫要比隨機免疫有效得多，只略差於選擇免疫。

同步性

主條目：複雜網絡動力系統的同步

音樂會或歌劇完場時，台下的觀眾不間斷地鼓掌。在很短幾次後，鼓掌的頻率就會變得同步。這種現象顯示出網絡的同步性。研究表明，網絡動力系統的同步性取決於節點動力系統的特性，節點的耦合方式與網絡的結構。對於BA模型網絡，節點數的增加不會降低網絡同步的穩定性。而面對隨機攻擊和蓄意攻擊，BA模型網絡的同步性與連通性表現出相同的特徵：對於隨機攻擊承受性強，而對蓄意攻擊則顯得脆弱。

參考來源

• Eric D. Kolaczyk. Statistical analysis of network data: methods and models. Springer; 1 edition. 2009. ISBN 978-0387881454 （英語）. 
• Richard Durrett. Random graph dynamics. Cambridge University Press. 2007. ISBN 978-0-521-86656-9 （英語）. 

外部連結

• snGraph （頁面存檔備份，存於網際網路檔案館） （英文）
• The Erdős Webgraph Server （頁面存檔備份，存於網際網路檔案館） （英文）

相關條目

• 小世界網絡
• 系統風險