集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

度分布

在图和网络的研究领域，网络节点的度是它与其他节点的连接数，而度分布 Degree distribution就是整个网络中这些度的概率分布。

定义

网络中一个节点的度（有时会被误认为连通性）是该节点与其他节点的连接或边的数量。如果网络是有向的，里面的边也会具有方向，从一个节点指向另一个节点，那么这些节点就会有两个度，一个度表示入射边的数量，另一个度表示出射边的数量，分别记为入度和出度。


度分布P(k)定义是：网络中度值为k的所有节点与总节点数量的分数，如果一个网络中有n个节点，且其中nk个节点的度值为k，那么 P(k) = nk/n。度分布就是P(k)的整体分布。类似的，对于有向网络也可以定义出度分布和入度分布。


度分布的定义也可以用累积度分布Cumulative Degree Distribution（位置[math]\displaystyle{ k }[/math]的累积度分布的值表示网络中度值小于或等于[math]\displaystyle{ k }[/math]的概率）的形式来表示，也可以用互补累积度分布Complementary Cumulative Degree Distribution或者逆累积度分布（[math]\displaystyle{ k }[/math]处的互补累积度分布的值表示网络中度值大于[math]\displaystyle{ k }[/math]的概率）的形式表示，此分布与积累度分布互补。


观察度分布

无论是在研究真实网络（如互联网和社会网络）还是在理论网络， 度分布都极为重要。以最简单的网络模型——随机图（ER模型）为例，该网络中的[math]\displaystyle{ n }[/math]个节点中任意两个节点之间以概率[math]\displaystyle{ p }[/math]连接，以概率[math]\displaystyle{ p }[/math]不连接，它们之间为独立事件。整个网络的度服从二项分布，其中度值为[math]\displaystyle{ k }[/math]的概率为:

[math]\displaystyle{ P(k) = {n-1\choose k} p^k (1 - p)^{n-1-k}, }[/math]


（当[math]\displaystyle{ n }[/math]无限大，平均度为[math]\displaystyle{ ⟨k⟩=p(n−1) }[/math]保持有限时，该二项分布可近似为泊松分布）。

但现实世界中的大多数网络的度分布却与上述分布非常不同，它们大多数是高度右偏的，这就意味着网络中的大量节点的度值较低，但少数节点，即所谓的“枢纽”，度值很高。一些网络，尤其是互联网、万维网和一些社交网络，其度分布被认为近似遵循幂律分布 power law:


[math]\displaystyle{ P(k)\sim k^{-\gamma} }[/math]

其中[math]\displaystyle{ γ }[/math]是一个常数，被称为幂律指数。这种网络被称为无标度网络 Scale-free network，它因其特殊的结构和动力学性质而引起人们的关注。[1][2][3][4]然而，最近有一个基于广泛真实数据的综合性研究认为，如果用严格的统计方法，无标度网络实际上是稀有的。[5]

一些研究人员对这些发现提出了异议，认为研究中使用的定义过于严格[6] ，其他人则认为，没有必要确定度分布的精确函数形式，只需要知道度分布是否为厚尾分布就好[7] 。对度分布的特定形式的过度解释也受到批评，因为它没有考虑网络如何随时间演化[8]。

假设一个网络具有度分布[math]\displaystyle{ P(k) }[/math],通过随机选择一个节点跟随一条边到达它的一个邻近点（假设至少有一个邻近点），那么后者具有[math]\displaystyle{ k }[/math] 个邻近点的概率不是由[math]\displaystyle{ P(k) }[/math]给出的，而是[math]\displaystyle{ \frac{kP(k)}{\langle k \rangle} }[/math]给出，这里的[math]\displaystyle{ {\langle k \rangle} }[/math]是网络的平均度。

朋友的平均朋友数量是:[math]\displaystyle{ \sum_k k \frac{kP(k)}{\langle k \rangle}=\frac{\langle k^2\rangle}{\langle k^\rangle} }[/math]，其中[math]\displaystyle{ {\langle k^2\rangle} }[/math]是网络中度的平均值，当网络中各节点的度不完全相同时，[math]\displaystyle{ {\langle k^2\rangle} \gt {\langle k\rangle}^2 }[/math] 。


由此可知，任意节点的邻居的平均度会大于该节点的平均度。推广到在社交网络中，这意味着你的朋友平均比你拥有更多的朋友。这就是著名的朋友悖论 Friendship Paradox。


造成这一结果的原因在于，无论何时在异质网络中选择某一个节点，它都更有可能通过跟随该节点的某一个现有邻点到达枢纽节点。

余度分布

余度分布 Excess Degree Distribution的定义是：沿着任意一条边到达某个节点，这个节点其他边的数量的概率分布。[9]换句话说，它是随链接进入一个节点后出去的边数的分布。


在配置模型 Configuration Model中，忽略节点之间的相关性，并假定每个节点以相同的概率连接到网络中的其他任何节点，余度分布表示为:



[math]\displaystyle{ q(k) = \frac{k+1}{\langle k \rangle}P(k+1), }[/math]


这里[math]\displaystyle{ {\langle k \rangle} }[/math]是模型的平均度。可以证明，如果一个网络的平均余度大于1，那么它可以有一个巨大的联通分支:

[math]\displaystyle{ \sum_k kq(k) \gt 1 \Rightarrow {\langle k^2 \rangle}-2{\langle k \rangle}\gt 0 }[/math]


要注意的是，以上两个方程只适用于配置模型，想要准确得到现实世界的网络中的余度分布，还应考虑网络中的度-度相关性。


生成函数方法

生成函数可以用来计算随机网络的不同性质。分别给定某些网络的度分布[math]\displaystyle{ P(k) }[/math]和余度分布[math]\displaystyle{ q(k) }[/math]，可以以下列形式写出两个幂级数:

[math]\displaystyle{ G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k }[/math] 和 [math]\displaystyle{ G_1(x) = \textstyle \sum_{k} \displaystyle q(k)x^k = \textstyle \sum_{k} \displaystyle \frac{k}{\langle k \rangle}P(k)x^{k-1} }[/math]


[math]\displaystyle{ G_1(x) }[/math] 的值也可得出通过 [math]\displaystyle{ G_0(x) }[/math]的导数：


[math]\displaystyle{ G_1(x) = \frac{G'_0(x)}{G'_0(1)} }[/math]


如果已知概率分布[math]\displaystyle{ P(k) }[/math]的生成函数，我们可以通过对其微分重新得到[math]\displaystyle{ P(k) }[/math]

[math]\displaystyle{ P(k) = \frac{1}{k!} {\operatorname{d}^k\!G\over\operatorname{d}\!x^k}\biggl \vert _{x=0} }[/math]

一些性质，如一些矩，然后，可以很容易地进行计算依据[math]\displaystyle{ G_0(x) }[/math] 和它的导数:


[math]\displaystyle{ {\langle k \rangle} = G'_0(1) }[/math]
[math]\displaystyle{ {\langle k^2 \rangle} = G''_0(1) + G'_0(1) }[/math]


更一般的，有：

[math]\displaystyle{ {\langle k^m \rangle} = \Biggl[{\bigg(\operatorname{x}{\operatorname{d}\!\over\operatorname{dx}\!}\biggl)^m}G_0(x)\Biggl]_{x=1} }[/math]


对于度分布服从泊松分布的随机网络，如ER随机图，[math]\displaystyle{ G_1(x) = G_0(x) }[/math]就是这种类型的随机网络理论特别简单的原因。一阶和二阶近邻的概率分布由函数[math]\displaystyle{ G_0(x) }[/math] 和[math]\displaystyle{ G_0(G_1(x)) }[/math]生成。进一步扩展，[math]\displaystyle{ m }[/math]阶近邻的概率分布由如下式子得到：


[math]\displaystyle{ G_0\bigl(G_1(...G_1(x)...)\bigr) }[/math]

其中的 [math]\displaystyle{ G_1 }[/math] 函数作用到自身（递归调用）m-1次。

一阶近邻的平均数量就是[math]\displaystyle{ c_1 }[/math]是[math]\displaystyle{ {\langle k \rangle} = {dG_0(x)\over dx}|_{x=1} }[/math] 二阶近邻的平均数量是：[math]\displaystyle{ c_2 = \biggl[ {d\over dx}G_0\big(G_1(x)\big)\biggl]_{x=1} = G_1'(1)G'_0\big(G_1(1)\big) = G_1'(1)G'_0(1) = G''_0(1) }[/math]


有向网络的度分布

 
图1：维基百科超链接图（对数尺度）的入/出度分布


在有向网络中，每个节点都有相应的入度[math]\displaystyle{ k_{in} }[/math] 和出度[math]\displaystyle{ k_{out} }[/math]，分别表示指向该节点的边的数量和从该节点指出的边的数量。若用 [math]\displaystyle{ P(k_{in}, k_{out}) }[/math]表示随机挑选一个节点，其入度为[math]\displaystyle{ k_{in} }[/math]出度为[math]\displaystyle{ k_{out} }[/math]的概率，则对应于这个联合概率分布的生成函数可以写成含有两个变量[math]\displaystyle{ x }[/math]和 [math]\displaystyle{ y }[/math] 的形式：


[math]\displaystyle{ \mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} . }[/math]


由于有向网络中的每条边必须离开某个节点并进入另一个节点，因此净进入一个节点平均边数是零，即

[math]\displaystyle{ \langle{k_{in}-k_{out}}\rangle =\sum_{k_{in},k_{out}} \displaystyle (k_{in}-k_{out})P({k_{in},k_{out}}) = 0 }[/math],


这意味着，生成函数必须满足:


[math]\displaystyle{ {\partial \mathcal{G}\over\partial x}\vert _{x,y=1} = {\partial \mathcal{G}\over\partial y}\vert _{x,y=1} = c, }[/math]

[math]\displaystyle{ c }[/math]是网络中节点的平均度（出度和入度）；[math]\displaystyle{ \langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c. }[/math]

基于函数[math]\displaystyle{ \mathcal{G}(x,y) }[/math]，类似于与前面所述，我们可以得到入/出度分布和入/出的余度分布的生成函数。[math]\displaystyle{ G^{in}_0(x) }[/math]可以定义为一个随机选择节点上所到达边数的生成函数， [math]\displaystyle{ G^{in}_1(x) }[/math]可定义为随机选择的边指向的节点的到达边数的生成函数。我们也可以定义 [math]\displaystyle{ G^{out}_0(y) }[/math] 和 [math]\displaystyle{ G^{out}_1(y) }[/math]表示离开节点的边的数量的生成函数：

  • [math]\displaystyle{ G^{in}_0(x) = \mathcal{G}(x,1) }[/math]
  • [math]\displaystyle{ G^{in}_1(x) = \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1} }[/math]
  • [math]\displaystyle{ G^{out}_0(y) = \mathcal{G}(1,y) }[/math]
  • [math]\displaystyle{ G^{out}_1(y) = \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1} }[/math]


这里，一阶近邻的平均数量[math]\displaystyle{ c_1 }[/math]是[math]\displaystyle{ {\partial \mathcal{G}\over\partial x}\biggl \vert _{x,y=1} = {\partial \mathcal{G}\over\partial y}\biggl \vert _{x,y=1}=c }[/math],随机选择一个节点的二阶近邻的平均数量为[math]\displaystyle{ c_2 = G_1'(1)G'_0(1) ={\partial^2 \mathcal{G}\over\partial x\partial y}\biggl \vert _{x,y=1} }[/math]。 这些也可以分别表示通过指向的边来到某一个节点的一阶近邻和二阶近邻的平均数量，因为这些方程显然是在[math]\displaystyle{ x }[/math]和[math]\displaystyle{ y }[/math]上对称的。


符号网络的度分布

在符号网络中，每个节点都有一个正度([math]\displaystyle{ k_{ +} }[/math])和一个负度([math]\displaystyle{ k_{-} }[/math] )，分别表示连接到该节点的正边和负边的数量。所以符号网络会有正度分布([math]\displaystyle{ P(k_{+}) }[/math])和负度分布([math]\displaystyle{ P(k_{-}) }[/math])[10][11]。

参见

参考

  1. ↑ Barabási, Albert-László; Albert, Réka (1999-10-15). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342.
  2. ↑ Albert, Réka; Barabási, Albert-László (2000-12-11). "Topology of Evolving Networks: Local Events and Universality" (PDF). Physical Review Letters. 85 (24): 5234–5237. arXiv:cond-mat/0005085. Bibcode:2000PhRvL..85.5234A. doi:10.1103/physrevlett.85.5234. hdl:2047/d20000695. ISSN 0031-9007. PMID 11102229.
  3. ↑ Dorogovtsev, S. N.; Mendes, J. F. F.; Samukhin, A. N. (2001-05-21). "Size-dependent degree distribution of a scale-free growing network". Physical Review E. 63 (6): 062101. arXiv:cond-mat/0011115. Bibcode:2001PhRvE..63f2101D. doi:10.1103/physreve.63.062101. ISSN 1063-651X. PMID 11415146.
  4. ↑ Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Scale-free behavior of networks with the copresence of preferential and uniform attachment rules". Physica D: Nonlinear Phenomena. 371: 1–12. arXiv:1704.08597. Bibcode:2018PhyD..371....1P. doi:10.1016/j.physd.2018.01.005.
  5. ↑ Holme, Petter (2019-03-04). "Rare and everywhere: Perspectives on scale-free networks". Nature Communications (in English). 10 (1): 1016. Bibcode:2019NatCo..10.1016H. doi:10.1038/s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568.
  6. ↑ Voitalov, Ivan; van der Hoorn, Pim; van der Hofstad, Remco; Krioukov, Dmitri (18 October 2019). "Scale-free networks well done". Physical Review Research. 1 (3): 033034. doi:10.1103/PhysRevResearch.1.033034.
  7. ↑ Holme, Petter (2019-03-04). "Rare and everywhere: Perspectives on scale-free networks". Nature Communications (in English). 10 (1): 1016. Bibcode:2019NatCo..10.1016H. doi:10.1038/s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568.
  8. ↑ Falkenberg, Max; Lee, Jong-Hyeok; Amano, Shun-ichi; Ogawa, Ken-ichiro; Yano, Kazuo; Miyake, Yoshihiro; Evans, Tim S.; Christensen, Kim (18 June 2020). "Identifying time dependence in network growth". Physical Review Research. 2 (2): 023352. doi:10.1103/PhysRevResearch.2.023352.
  9. ↑ Newman, Mark (2018-10-18) (in en). Networks. 1. Oxford University Press. doi:10.1093/oso/9780198805090.001.0001. ISBN 978-0-19-880509-0. http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090. 
  10. ↑ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (January 2021). "Topological impact of negative links on the stability of resting-state brain network". Scientific Reports. doi:10.1038/s41598-021-81767-7. PMC 7838299. PMID 33500525.
  11. ↑ Ciotti V (2015). "Degree correlations in signed social networks". Physica A: Statistical Mechanics and its Applications. arXiv:1412.1024. doi:10.1016/j.physa.2014.11.062.


编者推荐

 
集智俱乐部

集智文章推荐

从神经网络功能预测结构的几何框架 | 网络科学论文速递17篇

集智斑图最新论文栏目，关注复杂系统、网络科学、计算社会科学、统计物理等领域的前沿进展，每天即时更新相关顶刊论文，和最新arXiv预印本论文。


 
巴拉巴西网络科学（课程）


巴拉巴西网络科学（课程）

本课程中，有幸邀请了汪小帆、赵海兴、许小可、史定华、陈清华、张江、狄增如、陈关荣、樊瑛、刘宗华这十个来自六大不同高校、在网络科学领域耕耘许久的教授作为导师，依据教材框架，各有侧重地为我们共同勾勒出整个学科的美丽图景，展示这个学科的迷人魅力，指引这个学科的灿烂未来。


复杂系统中的幂律分布（首节免费）

本课程是由北京师范大学陈清华老师主讲，该课程结合实际数据和丰富的学术文献，从各方面向大家展示幂律分布——复杂系统入门必修课，其特征和意义，以及如何应用，为大家打造了体系完整的幂律分布学习框架！

本中文词条由Ryan 参与编译， CecileLi、趣木木 审校，不是海绵宝宝编辑，已由陈清华老师进行专业审校，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=度分布&oldid=22036”