“度分布”的版本间的差异
跳到导航
跳到搜索
（→编者推荐） |
|||
| 第3行： | 第3行： | ||
|description=图论,图形不变量,网络理论 | |description=图论,图形不变量,网络理论 | ||
}} | }} | ||
| − | + | 在[[图 Graphs]]和[[网络 Networks]]的研究领域，网络节点的度是它与其他节点的连接数，而'''度分布'''就是整个网络中这些度的概率分布。 | |
| − | 在 | ||
==定义== | ==定义== | ||
网络中一个节点的度(有时会被误认为连通性)是该节点与其他节点的连接或边的数量。如果网络是有向的，它的边就可能沿着不同方向从一个节点指向另一个节点，那么这些节点们就会有两个不同的度，一个度表示入射边的数量，另一个度表示出射边的数量。 | 网络中一个节点的度(有时会被误认为连通性)是该节点与其他节点的连接或边的数量。如果网络是有向的，它的边就可能沿着不同方向从一个节点指向另一个节点，那么这些节点们就会有两个不同的度，一个度表示入射边的数量，另一个度表示出射边的数量。 | ||
| + | |||
度分布''P''(''k'')定义是：网络中度值为''k''的所有节点与总节点数量的分数比值，如果一个网络中有''n''个节点，且其中''n<sub>k</sub>''个节点的度值为''k''，那么 ''P''(''k'') = ''n''<sub>''k''</sub>/''n''。 | 度分布''P''(''k'')定义是：网络中度值为''k''的所有节点与总节点数量的分数比值，如果一个网络中有''n''个节点，且其中''n<sub>k</sub>''个节点的度值为''k''，那么 ''P''(''k'') = ''n''<sub>''k''</sub>/''n''。 | ||
| + | |||
度分布的定义也可以用'''<font color="#ff8000">累积度分布函数 Cumulative Degree Distribution</font>'''（随机选择一个节点，其度值小于k的概率）的形式来表示，或是用'''<font color="#ff8000">互补累积度分布函数 Complementary Cumulative Degree Distribution</font>'''（如果把''C''看作累积度分布，那么该函数为度大于或等于''k'' (1 - ''C'')的节点比例）的形式表示，这一定义与积累度分布互补。 | 度分布的定义也可以用'''<font color="#ff8000">累积度分布函数 Cumulative Degree Distribution</font>'''（随机选择一个节点，其度值小于k的概率）的形式来表示，或是用'''<font color="#ff8000">互补累积度分布函数 Complementary Cumulative Degree Distribution</font>'''（如果把''C''看作累积度分布，那么该函数为度大于或等于''k'' (1 - ''C'')的节点比例）的形式表示，这一定义与积累度分布互补。 | ||
| + | <br> | ||
== 观察度分布 == | == 观察度分布 == | ||
| − | 度分布无论是在研究真实网络(如互联网和社会网络)中还是在理论网络中都非常重要。以最简单的网络模型( | + | 度分布无论是在研究真实网络(如互联网和社会网络)中还是在理论网络中都非常重要。以最简单的网络模型([[ER模型]]) |
| − | + | [[随机图 Random graph]]为例，它的每''n''个节点都以概率''p'' (或1 − ''p'')独立连接(或不独立连接) ，其中'''<font color="#ff8000">二项分布 Binomial Distribution</font>'''的度值为''k'': | |
:<math> | :<math> | ||
| 第23行： | 第25行： | ||
</math> | </math> | ||
| − | (即使平均度\langle k\rangle=p(n-1)</math>保持不变，也会出现有限节点的泊松分布) | + | (即使平均度<math>\langle k\rangle=p(n-1)</math>保持不变，也会出现有限节点的泊松分布)。现实世界中的大多数网络的度分布却往往与上述分布非常不同，它们的大多数节点是高度右倾的，这就意味着这些节点的度值较低，但少数节点，即所谓的“'''枢纽'''” ，度值较高。一些网络，尤其是互联网、万维网和一些社交网络，被认为具有近似遵循[[幂律分布 power law]： |
| + | |||
| + | :<math> | ||
P(k)\sim k^{-\gamma} | P(k)\sim k^{-\gamma} | ||
</math> | </math> | ||
| − | |||
| + | 其中γ是一个常数。这种网络被称为'''[[无标度网络 Scale-Free Networks]]'''，它因其结构和动力学性质而引起人们的重视。<ref name="BA">{{cite journal | last=Barabási | first=Albert-László | last2=Albert | first2=Réka | title=Emergence of Scaling in Random Networks | journal=Science | volume=286 | issue=5439 | date=1999-10-15 | issn=0036-8075 | doi=10.1126/science.286.5439.509 | pages=509–512| pmid=10521342 | arxiv=cond-mat/9910332 | bibcode=1999Sci...286..509B }}</ref><ref name="AB">{{cite journal | last=Albert | first=Réka | last2=Barabási | first2=Albert-László | title=Topology of Evolving Networks: Local Events and Universality | journal=Physical Review Letters | volume=85 | issue=24 | date=2000-12-11 | issn=0031-9007 | doi=10.1103/physrevlett.85.5234 | pages=5234–5237| pmid=11102229 | arxiv=cond-mat/0005085 | bibcode=2000PhRvL..85.5234A | hdl=2047/d20000695 | url=https://repository.library.northeastern.edu/files/neu:331099/fulltext.pdf }}</ref><ref name="Doro">{{cite journal | last=Dorogovtsev | first=S. N. | last2=Mendes | first2=J. F. F. | last3=Samukhin | first3=A. N. | title=Size-dependent degree distribution of a scale-free growing network | journal=Physical Review E | volume=63 | issue=6 | date=2001-05-21 | issn=1063-651X | doi=10.1103/physreve.63.062101 | page=062101| pmid=11415146 |arxiv=cond-mat/0011115| bibcode=2001PhRvE..63f2101D }}</ref><ref name="PSY">{{cite journal|title=Scale-free behavior of networks with the copresence of preferential and uniform attachment rules|journal=Physica D: Nonlinear Phenomena|year=2018|first=Angelica |last=Pachon |first2=Laura |last2=Sacerdote |first3=Shuyi |last3=Yang |volume=371|pages=1–12|doi=10.1016/j.physd.2018.01.005|arxiv=1704.08597|bibcode=2018PhyD..371....1P}}</ref>然而，最近有一些基于真实数据的研究表明，尽管大多数观测到的网络具有'''<font color="#ff8000">肥尾（头轻脚重？末端过于繁琐？不是很清楚）度分布 Fat-Tailed Degree Distributions</font>'''，但它们无标度分布的特点并不明显。<ref>{{Cite journal|last=Holme|first=Petter|date=2019-03-04|title=Rare and everywhere: Perspectives on scale-free networks|journal=Nature Communications|language=en|volume=10|issue=1|pages=1016|doi=10.1038/s41467-019-09038-8|issn=2041-1723|pmc=6399274|pmid=30833568|bibcode=2019NatCo..10.1016H}}</ref> | ||
| + | |||
| + | <br> | ||
== 超额度分布 == | == 超额度分布 == | ||
'''<font color="#ff8000">超额度分布 Excess Degree Distribution</font>'''的定义是：沿着一条边到达该节点的其他边的数量的概率分布。<ref name=":0">{{Cite book|last=Newman|first=Mark|url=http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090|title=Networks|date=2018-10-18|publisher=Oxford University Press|isbn=978-0-19-880509-0|volume=1|language=en|doi=10.1093/oso/9780198805090.001.0001}}</ref>换句话说，它是通过跟随链接从一个节点到达的其传出链接的分布。 | '''<font color="#ff8000">超额度分布 Excess Degree Distribution</font>'''的定义是：沿着一条边到达该节点的其他边的数量的概率分布。<ref name=":0">{{Cite book|last=Newman|first=Mark|url=http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090|title=Networks|date=2018-10-18|publisher=Oxford University Press|isbn=978-0-19-880509-0|volume=1|language=en|doi=10.1093/oso/9780198805090.001.0001}}</ref>换句话说，它是通过跟随链接从一个节点到达的其传出链接的分布。 | ||
| − | 假设一个网络具有度分布<math> | + | 假设一个网络具有度分布<math>P(k)</math>,通过选择一个节点（随机或非随机）跟随它的一个邻近点（假设至少有一个邻近点），那么该节点具有<math>k</math> 个邻近点的概率不是由<math>P(k)</math>.给出的。造成这一结果的原因在于，无论何时在异质网络中选择某个节点，它都更有可能通过跟随该节点的某个现有邻点到达枢纽节点。这些节点具有度<math>k</math>的真实概率是<math>q(k)</math>，它被称为该节点的'''超额度'''。在'''<font color="#ff8000">配置模型 Configuration Model</font>'''中，忽略节点之间的相关性，并假定每个节点以相同的概率连接到网络中的其他任何节点，超额度分布表示为: |
| − | P(k) | ||
| − | </math>, | ||
| − | k | ||
| − | </math> 个邻近点的概率不是由<math> | ||
| − | P(k) | ||
| − | </math>.给出的。造成这一结果的原因在于，无论何时在异质网络中选择某个节点，它都更有可能通过跟随该节点的某个现有邻点到达枢纽节点。这些节点具有度<math> | ||
| − | k | ||
| − | </math>的真实概率是<math> | ||
| − | q(k) | ||
| − | </math> | ||
| − | <math> | + | :<math> |
q(k) = \frac{k+1}{\langle k \rangle}P(k+1), | q(k) = \frac{k+1}{\langle k \rangle}P(k+1), | ||
</math> | </math> | ||
| − | |||
| − | <math> | + | 这里<math>{\langle k \rangle}</math>是模型的平均度。由此可知，任何节点的邻近点的平均度大于该节点的平均度。推广到在社交网络络中，这意味着你的朋友平均比你拥有更多的朋友。这就是著名的'''<font color="#ff8000">友谊悖论 Friendship Paradox</font>'''。可以证明，如果一个网络的平均超额度大于1，那么它可以有一个巨大的联通子网络: |
| + | |||
| + | :<math> | ||
\sum_k kq(k) > 1 \Rightarrow {\langle k^2 \rangle}-2{\langle k \rangle}>0 | \sum_k kq(k) > 1 \Rightarrow {\langle k^2 \rangle}-2{\langle k \rangle}>0 | ||
</math> | </math> | ||
| + | |||
要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。 | 要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。 | ||
| + | <br> | ||
== '''<font color="#ff8000">函数生成方法</font>''' == | == '''<font color="#ff8000">函数生成方法</font>''' == | ||
| − | 生成函数可以用来计算随机网络的不同性质。给定某些网络的度分布和超度分布，<math> | + | 生成函数可以用来计算随机网络的不同性质。给定某些网络的度分布和超度分布，<math>P(k)</math> 和 <math>q(k)</math>可以以下列形式写出两个幂级数: |
| − | P(k) | ||
| − | </math> 和 <math> | ||
| − | q(k) | ||
| − | </math>可以以下列形式写出两个幂级数: | ||
| − | <math> | + | :<math> |
G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k | G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k | ||
| − | </math> | + | </math> |
| + | |||
| + | :<math> | ||
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} | 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> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <math> | + | <math>G_1(x)</math> 的值也可得出通过 <math>G_0(x)</math>的导数: |
| + | |||
| + | :<math> | ||
G_1(x) = \frac{G'_0(x)}{G'_0(1)} | G_1(x) = \frac{G'_0(x)}{G'_0(1)} | ||
</math> | </math> | ||
| + | |||
如果已知生成函数的一个概率分布，我们就能通过运算检验得到<math>P(k)</math>的值： | 如果已知生成函数的一个概率分布，我们就能通过运算检验得到<math>P(k)</math>的值： | ||
| − | <math> | + | :<math> |
P(k) = \frac{1}{k!} {\operatorname{d}^k\!G\over\operatorname{d}\!x^k}\biggl \vert _{x=0} | P(k) = \frac{1}{k!} {\operatorname{d}^k\!G\over\operatorname{d}\!x^k}\biggl \vert _{x=0} | ||
</math> | </math> | ||
| − | |||
| − | |||
| − | |||
| + | 一些性质，例如，即时性。然后，可以很容易地进行计算依据<math>G_0(x)</math> 和它的导数: | ||
| − | + | :<math> | |
{\langle k \rangle} = G'_0(1) | {\langle k \rangle} = G'_0(1) | ||
</math> | </math> | ||
| − | + | :<math> | |
{\langle k^2 \rangle} = G''_0(1) + G'_0(1) | {\langle k^2 \rangle} = G''_0(1) + G'_0(1) | ||
</math> | </math> | ||
| 第101行： | 第94行： | ||
一般来说: | 一般来说: | ||
| − | + | :<math> | |
{\langle k^m \rangle} = \Biggl[{\bigg(\operatorname{x}{\operatorname{d}\!\over\operatorname{dx}\!}\biggl)^m}G_0(x)\Biggl]_{x=1} | {\langle k^m \rangle} = \Biggl[{\bigg(\operatorname{x}{\operatorname{d}\!\over\operatorname{dx}\!}\biggl)^m}G_0(x)\Biggl]_{x=1} | ||
</math> | </math> | ||
| − | 对于泊松分布的随机网络，如 ER 图，<math> | + | 对于泊松分布的随机网络，如 ER 图，<math>G_1(x) = G_0(x) </math>这就是这种类型的随机网络理论特别简单的原因。第一和第二邻近点的概率分布是由函数<math>G_0(x)</math> 和<math>G0(G1(x))</math>生成的。进一步扩展，<math>m</math>-th的邻近点的分布是由以下几个因素产生的: |
| − | G_1(x) = G_0(x) | ||
| − | </math>这就是这种类型的随机网络理论特别简单的原因。第一和第二邻近点的概率分布是由函数<math> | ||
| − | G_0(x) | ||
| − | </math> 和<math>G0(G1(x))</math>生成的。进一步扩展，<math> | ||
| − | m | ||
| − | </math>-th的邻近点的分布是由以下几个因素产生的: | ||
| − | |||
| − | <math> | + | :<math>G_0\bigl(G_1(...G_1(x)...)\bigr) </math>, 以<math>m-1 </math> 迭代到 <math>G_1 </math> 函数本身。第一邻边内点的平均数量<math>c_1</math>是<math>{\langle k \rangle} = {dG_0(x)\over dx}|_{x=1} |
| − | G_0\bigl(G_1(...G_1(x)...)\bigr) | + | </math> 第二邻边内点的平均数量是：<math>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> |
| − | </math>, 以<math> | ||
| − | m-1 | ||
| − | </math> 迭代到 <math> | ||
| − | G_1 | ||
| − | </math> 函数本身。第一邻边内点的平均数量<math> | ||
| − | c_1 | ||
| − | </math>是 | ||
| − | <math> | ||
| − | {\langle k \rangle} = {dG_0(x)\over dx}|_{x=1} | ||
| − | </math> | ||
| − | <math> | ||
| − | 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> | ||
| + | <br> | ||
== '''<font color="#ff8000">有向网络的度分布</font>''' == | == '''<font color="#ff8000">有向网络的度分布</font>''' == | ||
| 第135行： | 第109行： | ||
图1：维基百科超链接图(对数尺度)的入/出度分布]] | 图1：维基百科超链接图(对数尺度)的入/出度分布]] | ||
| − | 在有向网络中，每个节点都有一些入度<math> | + | 在有向网络中，每个节点都有一些入度<math>k_{in}</math> 和一些出度<math>k_{out}</math>，分别指代指向该节点的边的数量和从该节点指出的边的数量。如果 <math>P(k_{in}, k_{out})</math> 是一个随机选择的具有入出度的节点的可能性。那么分配给这个生成函数的'''<font color="#ff8000">联合概率分布 Joint Probability Distribution</font>'''可以被写成两个变量 <math>x</math> 和 <math>y</math> |
| − | k_{ | ||
| − | in} | ||
| − | </math> 和一些出度<math> | ||
| − | k_{out} | ||
| − | </math>，分别指代指向该节点的边的数量和从该节点指出的边的数量。如果 <math> | ||
| − | P(k_{in}, k_{out}) | ||
| − | </math> 是一个随机选择的具有入出度的节点的可能性。那么分配给这个生成函数的'''<font color="#ff8000">联合概率分布 Joint Probability Distribution</font>'''可以被写成两个变量 <math> | ||
| − | x | ||
| − | </math> 和 <math> | ||
| − | y | ||
| − | </math> | ||
| − | + | :<math> | |
| − | <math> | ||
\mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} . | \mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} . | ||
</math> | </math> | ||
| 第156行： | 第118行： | ||
由于有向网络中的每个链路必须离开某个节点并进入另一个节点，因此进入一个节点的链路的净平均数是零。所以, | 由于有向网络中的每个链路必须离开某个节点并进入另一个节点，因此进入一个节点的链路的净平均数是零。所以, | ||
| − | + | :<math> | |
| − | <math> | ||
\langle{k_{in}-k_{out}}\rangle =\sum_{k_{in},k_{out}} \displaystyle (k_{in}-k_{out})P({k_{in},k_{out}}) = 0 | \langle{k_{in}-k_{out}}\rangle =\sum_{k_{in},k_{out}} \displaystyle (k_{in}-k_{out})P({k_{in},k_{out}}) = 0 | ||
</math>, | </math>, | ||
| 第164行： | 第125行： | ||
这意味着，生成函数必须满足: | 这意味着，生成函数必须满足: | ||
| − | <math> | + | :<math> |
{\partial \mathcal{G}\over\partial x}\vert _{x,y=1} = {\partial \mathcal{G}\over\partial y}\vert _{x,y=1} = c, | {\partial \mathcal{G}\over\partial x}\vert _{x,y=1} = {\partial \mathcal{G}\over\partial y}\vert _{x,y=1} = c, | ||
| − | |||
</math> | </math> | ||
| − | <math> | + | <math>c</math>是网络中节点的平均度(内部和外部) |
| − | c | + | <math>\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.</math> |
| − | </math>是网络中节点的平均度(内部和外部)<math> | ||
| − | \langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c. | ||
| − | </math> | ||
| − | 使用函数 | + | 使用函数 |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | :<math>\mathcal{G}(x,y)</math> | ||
| + | 如上文所述，我们可以再次找到入/出度分布和入/出超量度分布的生成函数。可以将<math>G^{in}_0(x) </math>设为一个随机选择的节点上到达的链接数的生成函数，以及 <math>G^{in}_1(x)</math>可以设为按照随机选择的链接到达一个节点的到达链接数。我们也可以构造函数 <math>G^{out}_0(y)</math> 和 <math>G^{out}_1(y)</math>表示离开节点的边的数量: | ||
* <math> | * <math> | ||
| 第203行： | 第152行： | ||
</math> | </math> | ||
| − | + | 这里，第一邻边内点的平均数量<math>c</math>，或者像之前表示的<math>c_1</math>是<math> {\partial \mathcal{G}\over\partial x}\biggl \vert _{x,y=1} = {\partial \mathcal{G}\over\partial y}\biggl \vert _{x,y=1}</math>从一个随机选择的节点上可达到的第二邻边内的点的平均数是<math>c_2 = G_1'(1)G'_0(1) ={\partial^2 \mathcal{G}\over\partial x\partial y}\biggl \vert _{x,y=1}</math>. 这些是从随机选择的节点所达到第一和第二邻近点的数量，因为这些方程显然是在<math>x</math>和 <math>y</math>上对称的。 | |
| − | c | ||
| − | </math>，或者像之前表示的<math> | ||
| − | c_1 | ||
| − | </math>是 | ||
| − | <math> | ||
| − | |||
| − | |||
| − | </math>从一个随机选择的节点上可达到的第二邻边内的点的平均数是<math> | ||
| − | c_2 = G_1'(1)G'_0(1) ={\partial^2 \mathcal{G}\over\partial x\partial y}\biggl \vert _{x,y=1} | ||
| − | </math>. 这些是从随机选择的节点所达到第一和第二邻近点的数量，因为这些方程显然是在<math> | ||
| − | x | ||
| − | </math>和 <math> | ||
| − | y | ||
| − | |||
| − | </math>上对称的。 | ||
| + | <br> | ||
== 参见 == | == 参见 == | ||
| − | * | + | * [[图论 Graph theory]] |
| − | * | + | *[[复杂网络 Complex network]] |
| − | * | + | *[[无标度网络 Scale-free network]] |
| − | * | + | *[[随机网络 Random graph]] |
| − | * | + | * [[结构截止值 Structural cut-off]] |
2020年11月1日 (日) 00:58的版本
在图 Graphs和网络 Networks的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。
定义
网络中一个节点的度(有时会被误认为连通性)是该节点与其他节点的连接或边的数量。如果网络是有向的，它的边就可能沿着不同方向从一个节点指向另一个节点，那么这些节点们就会有两个不同的度，一个度表示入射边的数量，另一个度表示出射边的数量。
度分布P(k)定义是：网络中度值为k的所有节点与总节点数量的分数比值，如果一个网络中有n个节点，且其中nk个节点的度值为k，那么 P(k) = nk/n。
度分布的定义也可以用累积度分布函数 Cumulative Degree Distribution（随机选择一个节点，其度值小于k的概率）的形式来表示，或是用互补累积度分布函数 Complementary Cumulative Degree Distribution（如果把C看作累积度分布，那么该函数为度大于或等于k (1 - C)的节点比例）的形式表示，这一定义与积累度分布互补。
观察度分布
度分布无论是在研究真实网络(如互联网和社会网络)中还是在理论网络中都非常重要。以最简单的网络模型(ER模型) 随机图 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]
(即使平均度[math]\displaystyle{ \langle k\rangle=p(n-1) }[/math]保持不变，也会出现有限节点的泊松分布)。现实世界中的大多数网络的度分布却往往与上述分布非常不同，它们的大多数节点是高度右倾的，这就意味着这些节点的度值较低，但少数节点，即所谓的“枢纽” ，度值较高。一些网络，尤其是互联网、万维网和一些社交网络，被认为具有近似遵循[[幂律分布 power law]：
- [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]
- [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]
有向网络的度分布
在有向网络中，每个节点都有一些入度[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]\displaystyle{ 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]上对称的。
参见
参考
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
编者推荐
集智文章推荐
从神经网络功能预测结构的几何框架 | 网络科学论文速递17篇
集智斑图最新论文栏目，关注复杂系统、网络科学、计算社会科学、统计物理等领域的前沿进展，每天即时更新相关顶刊论文，和最新arXiv预印本论文。
本中文词条由Ryan 参与编译， CecileLi、趣木木 审校，不是海绵宝宝编辑，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。