度分布

维基百科,自由的百科全书
跳转至: 导航搜索
英文维基条目网络的度分布。将每个条目看成顶点,超链接看成边,则对应的出度/入度的分布如图所示。

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

定义[编辑]

度分布是图论和(复杂)网络理论中都存在的概念。首先介绍图的概念。一个图G=G(V, E)是一个由两个集合VE构成的二元组。集合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中的两个顶点ij连有k条边,并且规定e_{i, j} = e_{j, i}。有向图中,E的一个元素e_{i, j} = k,表示V中的顶点ik条连向顶点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},[1]

因此满足:

 \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 ).

这个定义与一般的图的度分布是不一样的[2]

在经典的随机图模型中,所有顶点的位置都是一致的,没有特殊的顶点。因此每个顶点的度分布P_i(k) 都是相同的:\forall i , \, P_i(k) = P(k) 。所以,随机抽取一个顶点,它的度数是k的概率就是P(k) P(k) 越高,表示可能有更多的顶点度数是k。当顶点数目很大每个顶点的度分布都是相对独立的时候,顶点的度分布P_i(k) 近似等于图中度数是k的顶点的比例[1]

例子[编辑]

由十个顶点构成的图

以下给出一些度分布的例子。右图是由十个顶点构成的无向图。其中度数是3的顶点有6个,度数是4的顶点有3个,度数是6的顶点有1个,所以度分布是:

P(m)=
\begin{cases}
 0.6, & m=3 \\
 0.3, & m=4 \\
 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}
图3.随机网络的度(a)集中在某个特定值d_c附近,而无尺度网络的度分布(b)则遵守幂律分布

如果图G是任意两顶点之间以概率0<p<1连边的随机图,那么每个顶点都有相同的度分布。

P(m)=\binom{n-1}{m}p^m(1-p)^{n-1-p}.[2]

这个分布是泊松分布。我们可以构造每个顶点的度数都是这样的概率分布的随机图模型。这样当顶点数很大的时候,度数是k的顶点的个数占的比例大致是P(k)。这个分布的特点是当k很小或很大的时候,P(k)都近似于0,P(k)的值在一个特定的值处达到高峰,然后回落。也就是说,大多数的顶点的度数在这个特定值左右。然而在真实的复杂网络中,人们观察到,度分布并不像这种随机图模型显示的,聚集在某个特定值周围,而是随着k增大而以多项式速度递减,也就是遵从所谓的幂律分布:

P(k) \propto \frac{1}{k^{\gamma}}

也就是说P(k) 的概率反比于k 的某个幂次,其中\gamma是某个正实数。这种网络特性被称为无尺度特性[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. arXiv:cond-mat/0303516. Bibcode:2003SIAMR..45..167N. 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]. 
  4. ^ Albert-László Barabási, Réka Albert. Emergence of Scaling in Random Networks. Science: 509–512. doi:10.1126/science.286.5439.509. 
期刊文章
书籍

参见[编辑]