度分布

度分布是图论和网络理论中的概念。一个图（或网络）由一些顶点（节点）和连接它们的边（连结）构成。每个顶点（节点）连出的所有边（连结）的数量就是这个顶点（节点）的度。度分布指的是对一个图（网络）中顶点（节点）度数的总体描述。对于随机图，度分布指的是图中顶点度数的概率分布。

定义
度分布是图论和（复杂）网络理论中都存在的概念。首先介绍图的概念。一个图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的顶点的比例。

参考文献
;引用

;期刊文章
*
*

;书籍
*

参见

• 图的连通性
• 集聚系数
• 複雜網路
• 無尺度網路
• 隨機圖
• 圖論