無尺度網路

無尺度網路

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

基本介紹

  • 中文名:無尺度網路
  • 又稱:無標度網路
  • 概念:隨著對複雜網路的研究而出現
  • 網路數學圖論研究的圖
源起,定義,特性,

源起

無尺度網路的概念是隨著對複雜網路的研究而出現的。“網路”其實就是數學中圖論研究的,由一群頂點以及它們之間所連的邊構成。在網路理論中則換一套說法,用“節點”代替“頂點”,用“連結”代替“邊”。複雜網路的概念,是用來描述由大量節點以及這些節點之間錯綜複雜的聯繫所構成的網路。這樣的網路會出現簡單網路中沒有的特殊拓撲特性。
自二十世紀60年代開始,對複雜網路的研究主要集中在隨機網路上。隨機網路,又稱隨機圖,是指通過隨機過程製造出的複雜網路。最典型的隨機網路是保羅·埃爾德什和阿爾弗雷德·雷尼提出的ER模型。ER模型是基於一種“自然”的構造方法:假設有{\displaystyle n}個節點,並假設每對節點之間相連的可能性都是常數{\displaystyle 0<p<1}。這樣構造出的網路就是ER模型網路。科學家們最初使用這種模型來解釋現實生活中的網路。
ER模型隨機網路有一個重要特性,就是雖然節點之間的連線是隨機形成的,但最後產生的網路的度分布是高度平等的。度分布是指節點的度的分布情況。在網路中,每個節點都與另外某些節點相連,這種連線的數目叫做這個節點的度。在網路中隨機抽取一個節點,它的度是多少呢?這個機率分布就稱為節點的度分布
在一般的隨機網路(如ER模型)中,大部分的節點的度都集中在某個特殊值附近,成鐘形的泊松分布規律。偏離這個特定值的機率指數性下降,遠大於或遠小於這個值的可能都是微乎其微的,就如一座城市中成年居民的身高大致的分布一樣。然而在1998年,Albert-László Barabási、Réka Albert等人合作進行一項描繪全球資訊網的研究時,發現通過超連結與網頁、檔案所構成的全球資訊網網路並不是如一般的隨機網路一樣,有著均勻的度分布。他們發現,全球資訊網是由少數高連線性的頁面串聯起來的。絕大多數(超過80%)的網頁只有不超過4個超連結,但極少數頁面(不到總頁面數的萬分之一)卻擁有極多的連結,超過1000個,有一份檔案甚至與超過200萬個其他頁面相連。與居民身高的例子作類比的話,就是說大多數的節點都是“矮個子”,而卻又有極少數的身高百丈的“巨人”。Barabási等人將其稱為“無尺度”網路。

定義

按生長方式定義:如果網路的每個節點的連線數與此節點產生新連線的機率成增函式關係,這個網路就叫無尺度網路。
按分布定義:如果網路中有一定數量的連線的節點數與此連線數量成減函式,這個網路就叫無尺度網路。
人造的網路結構大多是規則的。在隨機的網路結構中,節點與其他節點的連結的數量呈常態分配;在規則的網路結構中,節點與其他節點的連結數量是固定的。以上兩類網路中,節點與其他節點的連結的數量分布都有規則可循,因此是有尺度的網路。然而,用數學方法描繪網際網路時,出乎意料地發現有些節點與大量的其他節點連結,形成一個個集散中心(稱為集散節點),因而把網際網路這樣的網路稱為無尺度網路(scale-free network)。
無尺度網路中包含無數節點,大部分節點與其他節點只有幾個連結,有些節點與大量的其他節點連結,稱為集散節點。無尺度網路不存在代表性的節點,但受少數集散節點的支配,並具有如下可預期的行為特性:對意外事件具有驚人的承受力,對協同式攻擊很脆弱,受制於某些基本的法則。

特性

無尺度網路的特性,在於其度分布沒有一個特定的平均值指標,即大多數節點的度在此附近。在研究這個網路的度分布時,Barabási等人發現其遵守冪律分布(也稱為帕累托分布),也就是說,隨機抽取一個節點,它的度d是自然數k的機率:
也就是說d=k的機率正比於k的某個冪次(一般是負的,記為 − γ)。因此k越大,d=k的機率就越低。然而這個機率隨k增大而下降的“速度”是比較緩慢的:在一般的隨機網路中,下降的速度是指數性的,而在無尺度網路中只是以多項式類的速度下降。
在現實中許多大規模的無尺度網路中,度分布的γ值介於2與3之間。在對數坐標系中,度分布將會是一條斜率介於-2至-3之間的直線。如左下圖中,橫坐標為節點的度,從10一直到10;縱坐標為找到這樣的節點的機率從10 一直到10。最高度數的節點有882條連線。所有的藍點大致成一條直線分布(綠色的直線)。

相關詞條

熱門詞條

聯絡我們