度分布

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索


图 Graphs网络 Networks的研究领域,网络节点的度是它与其他节点的连接数,而度分布就是整个网络中这些度的概率分布。

定义

网络中一个节点的度(有时会被误认为连通性)是该节点与其他节点的连接或边的数量。如果网络是有向的,它的边就可能沿着不同方向从一个节点指向另一个节点,那么这些节点们就会有两个不同的度,一个度表示入射边的数量,另一个度表示出射边的数量。

度分布P(k)定义是:网络中度值为k的所有节点与总节点数量的分数比值,如果一个网络中有n个节点,且其中nk个节点的度值为k,那么 P(k) = nk/n

度分布的定义也可以用累积度分布函数 Cumulative Degree Distribution(随机选择一个节点,其度值小于k的概率)的形式来表示,或是用互补累积度分布函数 Complementary Cumulative Degree Distribution(如果把C看作累积度分布,那么该函数为度大于或等于k (1 - C)的节点比例)的形式表示,这一定义与积累度分布互补。

观察度分布

度分布无论是在研究真实网络(如互联网和社会网络)中还是在理论网络中都非常重要。以最简单的网络模型(Erdős–Rényi 模型)w 随机图 Random Graph为例,它的每n个节点都以概率p (或1 − p)独立连接(或不独立连接) ,其中二项分布 Binomial Distribution的度值为k:

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

(即使平均度\langle k\rangle=p(n-1)</math>保持不变,也会出现有限节点的泊松分布)。现实世界中的大多数网络的度分布却往往与上述分布非常不同,它们的大多数节点是高度右倾的,这就意味着这些节点的度值较低,但少数节点,即所谓的“枢纽” ,度值较高。一些网络,尤其是互联网、万维网和一些社交网络,被认为具有近似遵循幂定律的幂律分布:[math]\displaystyle{ P(k)\sim k^{-\gamma} }[/math]

其中γ是一个常数。这种网络被称为无标度网络 Scale-Free Networks,它因其结构和动力学性质而引起人们的重视。[1][2][3][4]然而,最近有一些基于真实数据的研究表明,尽管大多数观测到的网络具有肥尾(头轻脚重?末端过于繁琐?不是很清楚)度分布 Fat-Tailed Degree Distributions,但它们无标度分布的特点并不明显。[5]

超额度分布

超额度分布 Excess Degree Distribution的定义是:沿着一条边到达该节点的其他边的数量的概率分布。[6]换句话说,它是通过跟随链接从一个节点到达的其传出链接的分布。

假设一个网络具有度分布[math]\displaystyle{ P(k) }[/math],通过选择一个节点(随机或非随机)跟随它的一个邻近点(假设至少有一个邻近点),那么该节点具有[math]\displaystyle{ k }[/math] 个邻近点的概率不是由[math]\displaystyle{ P(k) }[/math].给出的。造成这一结果的原因在于,无论何时在异质网络中选择某个节点,它都更有可能通过跟随该节点的某个现有邻点到达枢纽节点。这些节点具有度[math]\displaystyle{ k }[/math]的真实概率是[math]\displaystyle{ q(k) }[/math],它被称为该节点的超额度。在配置模型 Configuration Model中,忽略节点之间的相关性,并假定每个节点以相同的概率连接到网络中的其他任何节点,超额度分布表示为:

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

这里[math]\displaystyle{ {\langle k \rangle} }[/math] 是模型的平均度。由此可知,任何节点的邻近点的平均度大于该节点的平均度。推广到在社交网络络中,这意味着你的朋友平均比你拥有更多的朋友。这就是著名的友谊悖论 Friendship Paradox。可以证明,如果一个网络的平均超额度大于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] and [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) = \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{ G0(G1(x)) }[/math]生成的。进一步扩展,[math]\displaystyle{ m }[/math]-th的邻近点的分布是由以下几个因素产生的:


[math]\displaystyle{ G_0\bigl(G_1(...G_1(x)...)\bigr) }[/math], 以[math]\displaystyle{ m-1 }[/math] 迭代到 [math]\displaystyle{ G_1 }[/math] 函数本身。第一邻边内点的平均数量[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]

Degree distribution for directed networks

有向网络的度分布 Degree Distribution For Directed Networks

图1:In/out degree distribution for Wikipedia's hyperlink graph (logarithmic scales) 维基百科超链接图(对数尺度)的入/出度分布

在有向网络中,每个节点都有一些入度[math]\displaystyle{ k_{ in} }[/math] 和一些出度[math]\displaystyle{ k_{out} }[/math],分别指代指向该节点的边的数量和从该节点指出的边的数量。如果 [math]\displaystyle{ P(k_{in}, k_{out}) }[/math] 是一个随机选择的具有入出度的节点的可能性。那么分配给这个生成函数的联合概率分布 Joint Probability Distribution可以被写成两个变量 [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> c </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} }[/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]上对称的。

参见

  • 图论 Graph Theory
  • 复杂网络 Complex Network
  • 无标度网络 Scale-free Network
  • 随机网络 Random Graph
  • 结构截止值 Structural Cut-off


参考

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


  • Albert, R.; Barabasi, A.-L.

2 = Barabasi,A.-L. (2002

2002年). "复杂网络的统计力学". Reviews of Modern Physics. 74

74 (1

1): 47–97. arXiv:cond-mat/0106096. Bibcode:[https://ui.adsabs.harvard.edu/abs/2002RvMP...74...47A

2002RvMP... 74... 47A 2002RvMP...74...47A 2002RvMP... 74... 47A]. doi:[//doi.org/10.1103%2FRevModPhys.74.47%0A%0A10.1103%2FRevModPhys.%2074.47 10.1103/RevModPhys.74.47 10.1103/RevModPhys. 74.47]. {{cite journal}}: Check |bibcode= length (help); Check |doi= value (help); Check date values in: |year= (help); Unknown parameter |杂志= ignored (help); Unknown parameter |第一= ignored (help); Unknown parameter |页数= ignored (help); line feed character in |author2= at position 16 (help); line feed character in |bibcode= at position 20 (help); line feed character in |doi= at position 25 (help); line feed character in |issue= at position 2 (help); line feed character in |volume= at position 3 (help); line feed character in |year= at position 5 (help)

}}

}}

  • Dorogovtsev, S.; Mendes, J. F. F.

2 = Mendes,J.f. (2002

2002年). "网络的进化". Advances in Physics. 51

51 (4

第四期): 1079–1187. arXiv:cond-mat/0106144. Bibcode:2002AdPhy..51.1079D. doi:[//doi.org/10.1080%2F00018730110112519%0A%0A10.1080%2F00018730110112519 10.1080/00018730110112519 10.1080/00018730110112519]. {{cite journal}}: Check |doi= value (help); Check date values in: |year= (help); Unknown parameter |杂志= ignored (help); Unknown parameter |第一= ignored (help); line feed character in |author2= at position 17 (help); line feed character in |doi= at position 26 (help); line feed character in |issue= at position 2 (help); line feed character in |volume= at position 3 (help); line feed character in |year= at position 5 (help)

|bibcode = 2002AdPhy..51.1079D }}

2002/adphy. . 51.1079 d }

  • Newman

纽曼, m.E.j. (2003

2003年). "复杂网络的结构和功能". SIAM Review. 45

45 (2

2): 167–256. arXiv:cond-mat/0303516. Bibcode:. 45. . 167 n 2003siaml. . 45. . 167 n. doi:10.1137/S003614450342480. {{cite journal}}: Check |bibcode= length (help); Check date values in: |year= (help); Unknown parameter |页= ignored (help); line feed character in |issue= at position 3 (help); line feed character in |last= at position 8 (help); line feed character in |volume= at position 4 (help); line feed character in |year= at position 6 (help)

}}

}}

2010年). [http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php

Http://havlin.biu.ac.il/shlomo%20havlin%20books_com_net.php Complex Networks: Structure, Robustness and Function

复杂网络: 结构、健壮性和功能]. Cambridge University Press

剑桥大学出版社. http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php

Http://havlin.biu.ac.il/shlomo%20havlin%20books_com_net.php. 

}}

}}


编者推荐

集智俱乐部

集智文章推荐

用神经学习模型计算海量实际网络中的节点中心性度量 | 论文速递1篇|集智俱乐部



博客推荐

社交网络分析:网络中心性

该篇博客为社会网络分析的笔记内容,有作者自己的思考,可从不同角度给予灵感。




本中文词条由Ryan 参与编译, CecileLi趣木木 审校,不是海绵宝宝薄荷编辑,欢迎在讨论页面留言。

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