無尺度網路

在網路理論中，無尺度網路的存在使得無尺度網路對意外故障有強大的承受能力，但面對協同性攻擊時則顯得脆弱。現實中的許多網路都帶有無尺度的特性，例如因特網、金融系統網路、社會人際網路等等。源起.}-無尺度網路的概念是隨著對複雜網路的研究而出現的。“網路”其實就是數學中圖論研究的圖，由一群頂點以及它們之間所連的邊構成。在網路理論中則換一套說法，用“節點”代替“頂點”，用“連結”代替“邊”:4:9。複雜網路的概念，是用來描述由大量節點以及這些節點之間錯綜複雜的聯絡所構成的網路。這樣的網路會出現簡單網路中沒有的特殊拓撲特性:2。自二十世紀60年代開始，對複雜網路的研究主要集中在隨機網路上。隨機網路，又稱隨機圖，是指透過隨機過程製造出的複雜網路。最典型的隨機網路是保羅·埃爾德什和阿爾弗雷德·雷尼提出的ER模型。ER模型是基於一種“自然”的構造方法：假設有formula_1個節點，並假設每對節點之間相連的可能性都是常數formula_2是自然數formula_3的機率：formula_4也就是說formula_5 的機率正比於formula_3 的某個冪次。因此formula_3越大，formula_5 的機率就越低。然而這個機率隨formula_3增大而下降的“速度”是比較緩慢的：在一般的隨機網路中，下降的速度是指數性的，而在無尺度網路中只是以多項式類的速度下降:12。在現實中許多大規模的無尺度網路中，度分佈的formula_11值介於2與3之間:14。在對數座標系中，度分佈將會是一條斜率介於-2至-3之間的直線:12。如左下圖中，橫座標為節點的度，從formula_12一直到formula_13；縱座標為找到這樣的節點的機率從formula_14一直到formula_12。最高度數的節點有882條連線。所有的藍點大致成一條直線分佈。度-度相關性.僅僅是將度分佈的冪律分佈作為無尺度網路的定義有其不夠完善之處。由於冪律分佈是方差可能無窮的高可變分佈，對於度分佈是同一個冪律分佈的不同網路，其拓撲結構和特性可能存在巨大的差異。2005年，Lun Li和大衛·阿爾德森度分佈formula_17的網路formula_18的集合，對於其中每一個網路formula_19，定義度-度相關數：formula_20其中formula_21表示formula_18中所有連線的集合。根據排序原理，如果度數大的點之間相互連線的話，那麼formula_23會比較大。設formula_24為最大的，那麼定義度-度相關係數：formula_25度-度相關係數formula_26介於0與1之間。formula_26越靠近1，則稱此網路formula_18“無尺度”的，formula_26靠近0，則稱formula_18是“富尺度”的。在此定義下，無尺度網路中的節點度數分佈特徵體現了自相似的性質，而凸顯了“無尺度”的特徵，與富尺度網路之間有相當的差異。例子.不少現實中的網路結構都屬於無尺度網路，或者有無尺度的特性。以下是一些無尺度網路的例子：BA模型.Albert-László Barabási與Réka Albert在1999年的論文中提出了一個模型來解釋複雜網路的無尺度特性，稱為BA模型。這個模型基於兩個假設：在這種假設下，BA模型的具體構造為：這樣，在經過formula_44次之後，得到的新網路有formula_45個節點，一共有formula_46條邊:27-28。分析BA模型網路的漸近度分佈主要有連續場理論、主方程法和速率方程法。這三種方法得到的漸近結果都是相同的。2001年，Béla Bollobás證明了在節點數量很大時，BA模型網路的度分佈遵從formula_47的冪律分佈:29。之後，其它的無尺度網路模型也開始被提出。其它無尺度模型.BA模型成功的為無尺度網路找到了一個簡單而合理的形成機制。然而，BA模型也有其自身的侷限。例如，它只能描述formula_47的無尺度網路，對於真實網路的一些非冪律特徵如指數截斷，允許節點自己與自己相連。而後又出現了只允許重複連線而不允許自連線的模型與不允許重複連線、自連線而是在選中的舊節點的鄰域隨機聯線的模型。適應度模型.在BA模型的製造過程中，人們發現，存在越久的節點具有越高的度數。然而，現實生活的網路中並非存在越久的元素就能有更多的聯絡。BA模型並沒有包括“後起之秀”的現象:33。於是，出現了基於BA模型的適應度模型。適應度模型主要是修正了優先連線的機制，對每個節點加上一個吸引因子formula_49，這樣新節點的相連機率改正為：formula_50局域世界演化模型.另一種基於BA模型的推廣版本是局域世界演化模型。這個模型假設每個新節點在引入時並不能在全域進行優先連線。比如說一家新上市的公司可能只會與同地區或同國家的公司展開貿易聯絡，居民搬入新社群時只會與同一幢樓的人開始認識等等。局域世界演化模型將BA模型優先連線的機制改為：新加入的節點時，先選擇全部節點的一部分作為局域世界，然後再在局域世界中進行優先連線。模擬結果指出，當formula_51從formula_53變化到formula_54時，產生的網路從服從指數分佈逐漸過渡到服從冪律分佈。複製模型.在BA模型中，度分佈實際上是和增長的時間formula_55相關的，只是在formula_55十分大時近似於度分佈。複製模型是一個與增長時間無關的模型。複製模型的做法是每次隨機地“複製”一個原有的節點：即隨機選定一個節點formula_57，再加入一個新節點，然後新節點按照formula_57與其它舊節點連線的方式與舊節點相連，最後與formula_57也相連。分層模型.2001年，Barabási提出了第一個確定性的分層網路模型。這個模型是為了解釋生物學中formula_60的代謝網路。分層模型的想法是從模體出發，透過自相似的層次疊加而得到複雜網路。這種思想類似於分數維圖形。Barabási的模型是：這樣形成的網路是無尺度網路，Barabási算出它的formula_61。後來有使用5節點4連結作為模體，得到formula_62，而4節點3連結作為模體得到formula_63，近似於代謝網路。需要注意的是此模型中不少度數是0機率的，所以需要使用補分佈繞過。類似的確定性模型還有偽分形圖。無尺度網路的阿喀琉斯之踵.2000年7月27日，《自然》雜誌的封面文章標題是《因特網的阿喀琉斯之踵》。阿喀琉斯是古希臘神話中的英雄，他出生後，他的母親捏著他的腳踝將他浸泡在冥河中，從此他的身體刀槍不入，只有踵部沒被浸到，是為其致命弱點。因此如今“阿喀琉斯之踵”常被用來稱呼一個系統的致命缺陷。這篇文章中從因特網的無尺度特性出發，探討它對意外故障的承受能力。假設在一個網路中移除一個節點，以及與其相關的連線，那麼原網路中的其他點也可能受到影響：原本相連的兩個節點可能不再相連；即使相連，從其中一處到另一處可能需要經過更多的路途。總的來說，網路的連通性降低了。文章比較了ER隨機網路模型與BA模型在移除少量節點時對網路連通性的影響。這個影響主要使用最大連通子圖的大小formula_64與平均路徑長度formula_65來衡量。在執行“隨機攻擊策略”，也就是在網路中隨機地去除一些節點時，無尺度網路的formula_64比隨機網路下降慢得多，formula_65的增長也緩慢得多。但是在執行“蓄意攻擊策略”，也就是選擇移除連線度最高的節點時，則會得到相反的結果。受到隨機攻擊的隨機圖會分裂成幾個較小的子圖，而無尺度網路則有很大機率保持連通；然而面對蓄意攻擊時，只需要移除5-10%的高於5度的節點，就能徹底癱瘓無尺度網路:31-33。流行病臨界值.流行病或網路病毒在複雜網路中的傳播也是複雜網路研究的方向之一。在均勻網路如ER模型隨機網路或小世界網路中，如果考慮易感:73-74。對於無尺度網路，由於度分佈不均勻，臨界值比較小。對於BA模型，臨界值為0。也就是說，只要有效傳播率大於0，病毒就能有效傳播並達到穩定。而對於有限規模的無標度網路，臨界值大於0，但會在均勻網路的十分之一左右。因此，無標度網路對於病毒傳播的抵抗性較均勻網路脆弱得多。由於無尺度網路應對流行病感染的脆弱性，人們提出不同的免疫策略來彌補。主要研究的免疫策略有三種：隨機免疫、選擇免疫與熟人免疫:79。隨機免疫.隨機免疫是在網路中隨機抽取一部分節點進行免疫。研究表明，採取這種策略的話，需要對網路中幾乎所有的節點都進行免疫才能保證最終消滅傳染病:79。選擇免疫.選擇免疫是在網路中抽取度最大的節點進行免疫。就BA模型而言，採取這種策略的話，即使有效傳播率變化，也可以只免疫很小一部分節點就保證消滅傳染病:79。熟人免疫.由於選擇免疫需要知道全域性節點的度數情況，才能找到度數最大節點進行免疫，這在面對網際網路等龐大的複雜網路時會導致難以操作。熟人免疫採取的是隨機抽取一部分節點，然後對每個節點隨機選一個與之相連的“鄰居”節點來進行免疫。由於在無尺度網路中，度大的節點可以與非常多的節點相連，因此選擇“鄰居”免疫的話，碰到度大節點的機率會比碰到度小節點的機率大得多。所以熟人免疫要比隨機免疫有效得多，只略差於選擇免疫:79。同步性.音樂會或歌劇完場時，臺下的觀眾不間斷地鼓掌。在很短几次後，鼓掌的頻率就會變得同步。這種現象顯示出網路的同步性。研究表明，網路動力系統的同步性取決於節點動力系統的特性，節點的耦合方式與網路的結構。對於BA模型網路，節點數的增加不會降低網路同步的穩定性。而面對隨機攻擊和蓄意攻擊，BA模型網路的同步性與連通性表現出相同的特徵：對於隨機攻擊承受性強，而對蓄意攻擊則顯得脆弱:79。