度分佈
度分佈是圖論和網絡理論中的概念。一個圖(或網絡)由一些頂點(節點)和連接它們的邊(連結)構成。每個頂點(節點)連出的所有邊(連結)的數量就是這個頂點(節點)的度。度分佈指的是對一個圖(網絡)中頂點(節點)度數的總體描述。對於隨機圖,度分佈指的是圖中頂點度數的概率分佈。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/c4/Enwiki-degree-distribution.png/300px-Enwiki-degree-distribution.png)
定義
度分佈是圖論和(複雜)網絡理論中都存在的概念。首先介紹圖的概念。一個圖 是一個由兩個集合 和 構成的二元組。集合 一般由有限個元素構成: ,其中的元素 被稱為圖的頂點。集合 是由 個元素構成的集合: 。 中的每個元素都是一個非負整數。無向圖中, 的一個元素 ,表示 中的兩個頂點 和 連有 條邊,並且規定 。有向圖中, 的一個元素 ,表示 中的頂點 有 條連向頂點 的邊。如果一個圖 中所有的 都不超過1,並且 ,那麼稱圖 是簡單圖。
網絡理論的數學框架建立在圖論上。網絡理論中的網絡其實就是圖論中的圖,但在網絡理論中稱之為網絡,圖的頂點在網絡理論中稱為節點,邊被稱為連結。以下仍舊以圖論中的術語定義度分佈。
一個無向圖 中某個頂點 的度,是指所有與它相連的邊的數目。
有向圖中,根據連出邊的數目和連入邊的數目,分為出度 和入度 。
因此,一個無向圖 中, 可以看成將每個頂點映射到一個非負整數的函數:
而度分佈則是對每個非負整數 ,考察度數是 的頂點在所有頂點中占的比例:
因此滿足:
從頂點中等概率地隨機抽取一個頂點,那麼這個頂點度數為 的概率就是 。
隨機圖頂點的度分佈
隨機圖是指由隨機過程產生的圖,即是將給定的頂點之間隨機地連上邊。一個隨機圖 中,每兩個頂點之間的邊的數量 是隨機變量。因此任一頂點 的度 也是隨機變量。這個變量的概率分佈也稱為隨機圖中的頂點的度分佈:
這個定義與一般的圖的度分佈是不一樣的[2]。
在經典的隨機圖模型中,所有頂點的位置都是一致的,沒有特殊的頂點。因此每個頂點的度分佈 都是相同的: 。所以,隨機抽取一個頂點,它的度數是 的概率就是 ; 越高,表示可能有更多的頂點度數是 。當頂點數目很大每個頂點的度分佈都是相對獨立的時候,頂點的度分佈 近似等於圖中度數是 的頂點的比例[1]。
例子
以下給出一些度分佈的例子。右圖是由十個頂點構成的無向圖。其中度數是4的頂點有3個,度數是3的頂點有6個,度數是6的頂點有1個,所以度分佈是:
對於 階完全圖,所有的頂點的度數都是 ,所以度分佈是:
如果圖 是任意兩頂點之間以概率 連邊的隨機圖,那麼每個頂點都有相同的度分佈。
這個分佈是泊松分佈。我們可以構造每個頂點的度數都是這樣的概率分佈的隨機圖模型。這樣當頂點數很大的時候,度數是 的頂點的個數占的比例大致是 。這個分佈的特點是當k很小或很大的時候, 都近似於0, 的值在一個特定的值處達到高峰,然後回落。也就是說,大多數的頂點的度數在這個特定值左右。然而在真實的複雜網絡中,人們觀察到,度分佈並不像這種隨機圖模型顯示的,聚集在某個特定值周圍,而是隨着k增大而以多項式速度遞減,也就是遵從所謂的冪律分佈:
參考文獻
- 引用
- ^ 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.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.
- ^ 《科學美國人》中文版2003年7月. 无尺度网络. 集智集團. [2011-07-04]. (原始內容存檔於2012-01-11).
- ^ 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).
- 期刊文章
- Albert, R.; Barabasi, A.-L. Statistical mechanics of complex networks. Reviews of Modern Physics. 2002, 74: 47–97. Bibcode:2002RvMP...74...47A. arXiv:cond-mat/0106096 . doi:10.1103/RevModPhys.74.47.
- Dorogovtsev, S.; Mendes, J. F. F. Evolution of networks. Advances in Physics. 2002, 51 (4): 1079–1187. Bibcode:2002AdPhy..51.1079D. arXiv:cond-mat/0106144 . doi:10.1080/00018730110112519.
- 書籍
- Shlomo Havlin, Reuven Cohen. Complex Networks: Structure, Robustness and Function. Cambridge University Press. 2010 [2013-04-20]. (原始內容存檔於2011-10-04).