度分布圖論網絡理論中的概念。一個圖(或網絡)由一些頂點(節點)和連接它們的邊(連結)構成。每個頂點(節點)連出的所有邊(連結)的數量就是這個頂點(節點)的。度分布指的是對一個圖(網絡)中頂點(節點)度數的總體描述。對於隨機圖,度分布指的是圖中頂點度數的概率分布

英文維基條目網絡的度分布。將每個條目看成頂點,超鏈接看成邊,則對應的出度/入度的分布如圖所示。

定義

編輯

度分布是圖論和(複雜)網絡理論中都存在的概念。首先介紹圖的概念。一個圖 是一個由兩個集合  構成的二元組。集合 一般由有限個元素構成: ,其中的元素 被稱為圖的頂點。集合 是由 個元素構成的集合:  中的每個元素都是一個非負整數。無向圖中, 的一個元素 ,表示 中的兩個頂點  連有 條邊,並且規定 。有向圖中, 的一個元素 ,表示 中的頂點  條連向頂點 的邊。如果一個圖 中所有的 都不超過1,並且 ,那麼稱圖 是簡單圖。

網絡理論的數學框架建立在圖論上。網絡理論中的網絡其實就是圖論中的圖,但在網絡理論中稱之為網絡,圖的頂點在網絡理論中稱為節點,邊被稱為連結。以下仍舊以圖論中的術語定義度分布。

一個無向圖 中某個頂點 的度,是指所有與它相連的邊的數目。

 

有向圖中,根據連出邊的數目和連入邊的數目,分為出度 和入度 

 
 

因此,一個無向圖 中, 可以看成將每個頂點映射到一個非負整數的函數

 

而度分布則是對每個非負整數 ,考察度數是 的頂點在所有頂點中占的比例:

 [1]

因此滿足:

 

從頂點中等概率地隨機抽取一個頂點,那麼這個頂點度數為 的概率就是 

隨機圖頂點的度分布

編輯

隨機圖是指由隨機過程產生的圖,即是將給定的頂點之間隨機地連上邊。一個隨機圖 中,每兩個頂點之間的邊的數量 隨機變量。因此任一頂點 的度 也是隨機變量。這個變量的概率分布也稱為隨機圖中的頂點的度分布:

 

這個定義與一般的圖的度分布是不一樣的[2]

在經典的隨機圖模型中,所有頂點的位置都是一致的,沒有特殊的頂點。因此每個頂點的度分布 都是相同的: 。所以,隨機抽取一個頂點,它的度數是 的概率就是  越高,表示可能有更多的頂點度數是 。當頂點數目很大每個頂點的度分布都是相對獨立的時候,頂點的度分布 近似等於圖中度數是 的頂點的比例[1]

例子

編輯
 
由十個頂點構成的圖

以下給出一些度分布的例子。右圖是由十個頂點構成的無向圖。其中度數是4的頂點有3個,度數是3的頂點有6個,度數是6的頂點有1個,所以度分布是:

 

對於 階完全圖,所有的頂點的度數都是 ,所以度分布是:

 
 
圖3.隨機網絡的度(a)集中在某個特定值 附近,而無尺度網絡的度分布(b)則遵守冪律分布

如果圖 是任意兩頂點之間以概率 連邊的隨機圖,那麼每個頂點都有相同的度分布。

 [2]

這個分布是泊松分布。我們可以構造每個頂點的度數都是這樣的概率分布的隨機圖模型。這樣當頂點數很大的時候,度數是 的頂點的個數占的比例大致是 。這個分布的特點是當k很小或很大的時候, 都近似於0, 的值在一個特定的值處達到高峰,然後回落。也就是說,大多數的頂點的度數在這個特定值左右。然而在真實的複雜網絡中,人們觀察到,度分布並不像這種隨機圖模型顯示的,聚集在某個特定值周圍,而是隨着k增大而以多項式速度遞減,也就是遵從所謂的冪律分布:

 

也就是說  的概率反比於  的某個冪次,其中 是某個正實數。這種網絡特性被稱為無尺度特性[3][4]

參考文獻

編輯
引用
  1. ^ 1.0 1.1 Newman, M. E. J. The structure and function of complex networks. SIAM Review. 2003, 45 (2): 167–256. Bibcode:2003SIAMR..45..167N. arXiv:cond-mat/0303516 . doi:10.1137/S003614450342480. [永久失效連結]
  2. ^ 2.0 2.1 M. E. J. Newman, S. H. Strogatz, D. J. Watts. Random Graphs with Arbitrary Degree Distribution and Their Applications. Phys. Rev. E. 2001, 64. doi:10.1103/PhysRevE.64.026118. 
  3. ^ 《科學美國人》中文版2003年7月. 无尺度网络. 集智集團. [2011-07-04]. (原始內容存檔於2012-01-11). 
  4. ^ Albert-László Barabási, Réka Albert. Emergence of Scaling in Random Networks (PDF). Science: 509–512. [2013-04-19]. doi:10.1126/science.286.5439.509. (原始內容 (PDF)存檔於2021-09-23). 
期刊文章
書籍

參見

編輯