查看“︁度分布”︁的源代码

[[File:Enwiki-degree-distribution.png|thumb|300px|英文维基条目网络的度分布。将每个条目看成顶点，超链接看成边，则对应的出度/入度的分布如图所示。]]

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

==定义==
度分布是图论和（[[复杂网络|复杂]]）网络理论中都存在的概念。首先介绍图的概念。一个图<math>G=G(V, E)</math>是一个由两个集合<math>V</math>和<math>E</math>构成的二元组。集合<math>V</math>一般由有限个元素构成：<math>V = \{ v_1, v_2, \cdots , v_n\}</math>，其中的元素<math>v_i , \, i= 1, 2, \cdots , n</math>被称为图的顶点。集合<math>E</math>是由<math>n^2</math>个元素构成的集合：<math>E = \{ e_{i,j} \, \, | \, \, i= 1, 2, \cdots , n, \, j= 1, 2, \cdots , n \}</math>。<math>E</math>中的每个元素都是一个非负整数。无向图中，<math>E</math>的一个元素<math>e_{i, j} = k</math>，表示<math>V</math>中的两个顶点<math>i</math>和<math>j</math>连有<math>k</math>条边，并且规定<math>e_{i, j} = e_{j, i}</math>。有向图中，<math>E</math>的一个元素<math>e_{i, j} = k</math>，表示<math>V</math>中的顶点<math>i</math>有<math>k</math>条连向顶点<math>j</math>的边。如果一个图<math>G</math>中所有的<math>e_{i, j} </math>都不超过1，并且<math>\forall i=1, 2, \cdots , n, \, \, e_{i, i} = 0</math>，那么称图<math>G</math>是简单图。

网络理论的数学框架建立在图论上。网络理论中的网络其实就是图论中的图，但在网络理论中称之为网络，图的顶点在网络理论中称为节点，边被称为连结。以下仍旧以图论中的术语定义度分布。

一个无向图<math>G=G(V, E)</math>中某个顶点<math>v_{i_0}</math>的度，是指所有与它相连的边的数目。
:<math>d(v_{i_0}) = \sum_{i = i_0 } e_{i, j}</math>
有向图中，根据连出边的数目和连入边的数目，分为出度<math>d_{out}</math>和入度<math>d_{in}</math>。
:<math>d_{out}(v_{i_0}) =  \sum_{i = i_0 } e_{i, j}</math>
:<math>d_{in}(v_{i_0}) =  \sum_{j = i_0 } e_{i, j}</math>

因此，一个无向图<math>G=G(V, E)</math>中，<math>d</math>可以看成将每个顶点映射到一个非负整数的[[函数]]：
:<math>d : \, v_{i} \mapsto d(v_i) \quad i=1, 2, \cdots , n.</math>
而度分布则是对每个非负整数<math>m</math>，考察度数是<math>m</math>的顶点在所有顶点中占的比例：
:<math>\forall m \in \mathbb{N}, \, \, P : m \mapsto P(m) = \frac{\operatorname{Card}\{ v_i \, | \, d(v_i) = m \} }{n},</math><ref name="new">{{cite journal
 |last    = Newman
 |first   = M. E. J.
 |title   = The structure and function of complex networks
 |journal = SIAM Review
 |volume  = 45
 |pages   = 167–256
 |year    = 2003
 |url     = http://siamdl.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SIREAD000045000002000167000001
 |doi     = 10.1137/S003614450342480
 |issue   = 2
 |arxiv   = cond-mat/0303516
 |bibcode = 2003SIAMR..45..167N
}}{{dead link|date=2017年12月 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
因此满足：
:<math> \sum_{m \in \mathbb{N} } P(m) = 1.</math>
从顶点中等概率地随机抽取一个顶点，那么这个顶点度数为<math>k</math>的概率就是<math>P(k)</math>。
===随机图顶点的度分布===
随机图是指由随机过程产生的图，即是将给定的顶点之间随机地连上边。一个随机图<math>G=G(V, E)</math>中，每两个顶点之间的边的数量<math>e_{i, j}</math>是[[随机变量]]。因此任一顶点<math>v_{i_0}</math>的度<math>d(v_{i_0}) = \sum_{i = i_0 } e_{i, j}</math>也是随机变量。这个变量的[[概率分布]]也称为随机图中的顶点的度分布：
:<math>P_i(k) = \mathbb{P}( d(v_i) = k ).</math>
这个定义与一般的图的度分布是不一样的<ref name="nsw">{{cite journal|author=M. E. J. Newman, S. H. Strogatz, D. J. Watts|title=Random Graphs with Arbitrary Degree Distribution and Their Applications|journal=Phys. Rev. E|year=2001|volume=64|doi=10.1103/PhysRevE.64.026118}}</ref>。

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

==例子==
[[File:GolombGraph.svg|thumb|200px|由十个顶点构成的图]]
以下给出一些度分布的例子。右图是由十个顶点构成的无向图。其中度数是4的顶点有3个，度数是3的顶点有6个，度数是6的顶点有1个，所以度分布是：
:<math>P(m)=
\begin{cases}
 0.3, & m=4 \\
 0.6, & m=3 \\
 0.1, & m=6 \\
 0, & m \neq 3, 4, 6 
\end{cases}</math>

对于<math>n</math>阶完全图，所有的顶点的度数都是<math>n-1</math>，所以度分布是：
:<math>P(m)=
\begin{cases}
 1, & m=n-1 \\
 0, & m \neq n-1 
\end{cases}</math>

[[File:DegreeDistributions.PNG|thumb|right|300px|图3.随机网络的度（a）集中在某个特定值<math>d_c</math>附近，而无尺度网络的度分布（b）则遵守幂律分布]]
如果图<math>G</math>是任意两顶点之间以概率<math>0<p<1</math>连边的随机图，那么每个顶点都有相同的度分布。
:<math>P(m)=\binom{n-1}{m}p^m(1-p)^{n-1-m}.</math><ref name="nsw"/>
这个分布是[[泊松分布]]。我们可以构造每个顶点的度数都是这样的概率分布的随机图模型。这样当顶点数很大的时候，度数是<math>k</math>的顶点的个数占的比例大致是<math>P(k)</math>。这个分布的特点是当k很小或很大的时候，<math>P(k)</math>都近似于0，<math>P(k)</math>的值在一个特定的值处达到高峰，然后回落。也就是说，大多数的顶点的度数在这个特定值左右。然而在真实的复杂网络中，人们观察到，度分布并不像这种随机图模型显示的，聚集在某个特定值周围，而是随着k增大而以多项式速度递减，也就是遵从所谓的幂律分布：
<center><math>P(k) \propto \frac{1}{k^{\gamma}}</math></center>

也就是说<math>P(k)</math> 的概率反比于<math>k</math> 的某个幂次，其中<math>\gamma</math>是某个正实数。这种网络特性被称为[[无尺度网络|无尺度特性]]<ref name="sa">{{cite web| title =无尺度网络| url =http://www.swarmagents.com/complex/models/network.htm| publisher =集智集团| author =《科学美国人》中文版2003年7月| accessdate =2011-07-04| deadurl =yes| archiveurl =https://web.archive.org/web/20120111132542/http://www.swarmagents.com/complex/models/network.htm| archivedate =2012-01-11}} </ref><ref name="BA">{{cite journal |title = ''Emergence of Scaling in Random Networks'' |url = http://arxiv.org/PS_cache/cond-mat/pdf/9910/9910332v1.pdf |author = Albert-László Barabási, Réka Albert |journal = ''Science'' |volume = 286 no. 5439 |pages = 509-512 |doi = 10.1126/science.286.5439.509 |access-date = 2013-04-19 |archive-date = 2021-09-23 |archive-url = https://web.archive.org/web/20210923104103/https://arxiv.org/PS_cache/cond-mat/pdf/9910/9910332v1.pdf }}</ref>。

==参考文献==
;引用
{{Reflist}}

;期刊文章
* {{cite journal
  |last = Albert
  |first = R.
  |coauthors = Barabasi, A.-L.
  |title = Statistical mechanics of complex networks
  |journal = Reviews of Modern Physics
  |volume = 74
  |pages = 47–97
  |year = 2002
  |arxiv = cond-mat/0106096
  |doi = 10.1103/RevModPhys.74.47
|bibcode=2002RvMP...74...47A
}}
* {{cite journal
  |last = Dorogovtsev
  |first = S.
  |coauthors = Mendes, J. F. F.
  |title = Evolution of networks
  |url = https://archive.org/details/sim_advances-in-physics_2002-06_51_4/page/1079
  |journal = Advances in Physics
  |volume = 51
  |pages = 1079–1187
  |year = 2002
  |arxiv = cond-mat/0106144
  |doi = 10.1080/00018730110112519
  |issue = 4
|bibcode = 2002AdPhy..51.1079D }}

;书籍
* {{cite book 
  |title = Complex Networks: Structure, Robustness and Function 
  |authors = Shlomo Havlin, Reuven Cohen 
  |year = 2010 
  |url = http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php 
  |publisher = Cambridge University Press 
  |access-date = 2013-04-20 
  |archive-date = 2011-10-04 
  |archive-url = https://web.archive.org/web/20111004235522/http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php 
  }}

== 参见 ==
* [[连通图|图的连通性]]
* [[集聚系数]]
* [[複雜網路]]
* [[無尺度網路]]
* [[隨機圖]]
* [[圖論]]

[[Category:图论]]
[[Category:网络]]