跳至內容

度分佈

維基百科,自由的百科全書
英文維基條目網絡的度分佈。將每個條目看成頂點,超連結看成邊,則對應的出度/入度的分佈如圖所示。

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

定義

[編輯]

度分佈是圖論和(複雜)網絡理論中都存在的概念。首先介紹圖的概念。一個圖是一個由兩個集合構成的二元組。集合一般由有限個元素構成:,其中的元素被稱為圖的頂點。集合是由個元素構成的集合:中的每個元素都是一個非負整數。無向圖中,的一個元素,表示中的兩個頂點連有條邊,並且規定。有向圖中,的一個元素,表示中的頂點條連向頂點的邊。如果一個圖中所有的都不超過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). 
期刊文章
書籍

參見

[編輯]