更改

==定义==

==定义==

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

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

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

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

<br>

<br>

== 观察度分布 ==

== 观察度分布 ==

:<math>

:<math>

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

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

 

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

其中γ是一个常数。这种网络被称为'''[[无标度网络 Scale-free network]]'''，它因其结构和动力学性质而引起人们的重视。<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>  

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

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

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

这里<math>{\langle k \rangle}</math>是模型的平均度。由此可知，任何节点的邻近点的平均度大于该节点的平均度。推广到在社交网络络中，这意味着你的朋友平均比你拥有更多的朋友。这就是著名的'''<font color="#ff8000">友谊悖论 Friendship Paradox</font>'''。可以证明，如果一个网络的平均超额度大于1，那么它可以有一个巨大的联通子网络:

这里<math>{\langle k \rangle}</math>是模型的平均度。由此可知，任意节点的邻居的平均度会大于该节点的平均度。推广到在社交网络络中，这意味着你的朋友平均比你拥有更多的朋友。这就是著名的'''<font color="#ff8000">朋友悖论 Friendship Paradox</font>'''。可以证明，如果一个网络的平均超额度大于1，那么它可以有一个巨大的联通分支:

 

:<math>

:<math>

<br>

<br>

== 函数生成方法 ==

== 函数生成方法 ==

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

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

 

:<math>

:<math>

如果已知生成函数的一个概率分布，我们就能通过运算检验得到<math>P(k)</math>的值：

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

 

:<math>

:<math>

</math>

</math>

 

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

一些性质，例如，即时性。然后，可以很容易地进行计算依据<math>G_0(x)</math> 和它的导数:

 

:<math>

:<math>

:<math>G_0\bigl(G_1(...G_1(x)...)\bigr) </math>, 以<math>m-1 </math> 迭代到 <math>G_1 </math> 函数本身。

其中的 <math>G_1 </math> 函数作用到自身（递归调用）31次。

第一邻边内点的平均数量<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>

 

一阶近邻的平均数量c1就是<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>

<br>

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

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

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

 

:<math>

:<math>

</math>

</math>

<math>c</math>是网络中节点的平均度（内部和外部）；<math>\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.</math>

<math>c</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>\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>

这里，第一邻边内点的平均数量<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>上对称的。

 

这里，一阶近邻的平均数量<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>（公式里面增加=c）,随机选择一个节点的二阶近邻的平均数量为<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>

<br>

== 参见 ==

== 参见 ==