度分布

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

## 定義

度分布是圖論和（複雜）網絡理論中都存在的概念。首先介紹圖的概念。一個圖 $G=G(V,E)$ 是一個由兩個集合 $V$ 和 $E$ 構成的二元組。集合 $V$ 一般由有限個元素構成： $V=\{v_{1},v_{2},\cdots ,v_{n}\}$ ，其中的元素 $v_{i},\,i=1,2,\cdots ,n$ 被稱為圖的頂點。集合 $E$ 是由 $n^{2}$ 個元素構成的集合： $E=\{e_{i,j}\,\,|\,\,i=1,2,\cdots ,n,\,j=1,2,\cdots ,n\}$ 。 $E$ 中的每個元素都是一個非負整數。無向圖中， $E$ 的一個元素 $e_{i,j}=k$ ，表示 $V$ 中的兩個頂點 $i$ 和 $j$ 連有 $k$ 條邊，並且規定 $e_{i,j}=e_{j,i}$ 。有向圖中， $E$ 的一個元素 $e_{i,j}=k$ ，表示 $V$ 中的頂點 $i$ 有 $k$ 條連向頂點 $j$ 的邊。如果一個圖 $G$ 中所有的 $e_{i,j}$ 都不超過 1，並且 $\forall i=1,2,\cdots ,n,\,\,e_{i,i}=0$ ，那麼稱圖 $G$ 是簡單圖。

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

一個無向圖 $G=G(V,E)$ 中某個頂點 $v_{i_{0}}$ 的度，是指所有與它相連的邊的數目。

　
: $d(v_{i_{0}})=\sum _{i=i_{0}}e_{i,j}$

有向圖中，根據連出邊的數目和連入邊的數目，分為出度 $d_{out}$ 和入度 $d_{in}$ 。

　
: $d_{out}(v_{i_{0}})=\sum _{i=i_{0}}e_{i,j}$

　
: $d_{in}(v_{i_{0}})=\sum _{j=i_{0}}e_{i,j}$

因此，一個無向圖 $G=G(V,E)$ 中， $d$ 可以看成將每個頂點映射到一個非負整數的函數：

　
: $d:\,v_{i}\mapsto d(v_{i})\quad i=1,2,\cdots ,n.$

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

　
: $\forall m\in \mathbb {N} ,\,\,P:m\mapsto P(m)={\frac {\operatorname {Card} \{v_{i}\,|\,d(v_{i})=m\}}{n}},$

因此滿足：

　
: $\sum _{m\in \mathbb {N} }P(m)=1.$

從頂點中等概率地隨機抽取一個頂點，那麼這個頂點度數為 $k$ 的概率就是 $P(k)$ 。

### 隨機圖頂點的度分布

隨機圖是指由隨機過程產生的圖，即是將給定的頂點之間隨機地連上邊。一個隨機圖 $G=G(V,E)$ 中，每兩個頂點之間的邊的數量 $e_{i,j}$ 是隨機變量。因此任一頂點 $v_{i_{0}}$ 的度 $d(v_{i_{0}})=\sum _{i=i_{0}}e_{i,j}$ 也是隨機變量。這個變量的概率分布也稱為隨機圖中的頂點的度分布：

　
: $P_{i}(k)=\mathbb {P} (d(v_{i})=k).$

這個定義與一般的圖的度分布是不一樣的。

在經典的隨機圖模型中，所有頂點的位置都是一致的，沒有特殊的頂點。因此每個頂點的度分布 $P_{i}(k)$ 都是相同的： $\forall i,\,P_{i}(k)=P(k)$ 。所以，隨機抽取一個頂點，它的度數是 $k$ 的概率就是 $P(k)$ ； $P(k)$ 越高，表示可能有更多的頂點度數是 $k$ 。當頂點數目很大每個頂點的度分布都是相對獨立的時候，頂點的度分布 $P_{i}(k)$ 近似等於圖中度數是 $k$ 的頂點的比例。

## 例子

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

　
: $P(m)={\begin{cases}0.3,&m=4\\0.6,&m=3\\0.1,&m=6\\0,&m\neq 3,4,6\end{cases}}$

對於 $n$ 階完全圖，所有的頂點的度數都是 $n-1$ ，所以度分布是：

　
: $P(m)={\begin{cases}1,&m=n-1\\0,&m\neq n-1\end{cases}}$

如果圖 $G$ 是任意兩頂點之間以概率 $0<p<1$ 連邊的隨機圖，那麼每個頂點都有相同的度分布。

　
: $P(m)={\binom {n-1}{m}}p^{m}(1-p)^{n-1-m}.$

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

 $P(k)\propto {\frac {1}{k^{\gamma }}}$
也就是說 $P(k)$ 的概率反比於 $k$ 的某個冪次，其中 $\gamma $ 是某個正實數。這種網絡特性被稱為無尺度特性。

## 參考文獻

**引用**

**期刊文章**

* 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）.

## 參見

* 圖的連通性
* 集聚係數
* 複雜網路
* 無尺度網路
* 隨機圖
* 圖論