更改

(or [[Poisson distribution|Poisson]] in the limit of large ''n'', if the average degree <math>\langle k\rangle=p(n-1)</math> is held fixed). Most networks in the real world, however, have degree distributions very different from this. Most are highly [[Skewness|right-skewed]], meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree. Some networks, notably the Internet, the [[world wide web]], and some social networks were argued to have degree distributions that approximately follow a [[power law]]: <math>

(or [[Poisson distribution|Poisson]] in the limit of large ''n'', if the average degree <math>\langle k\rangle=p(n-1)</math> is held fixed). Most networks in the real world, however, have degree distributions very different from this. Most are highly [[Skewness|right-skewed]], meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree. Some networks, notably the Internet, the [[world wide web]], and some social networks were argued to have degree distributions that approximately follow a [[power law]]:  

(如果平均度<math>\langle k\rangle=p(n-1)</math>保持不变，也会出现有限节点的泊松分布)。然而，现实世界中的大多数网络的度分布与上述分布非常不同。大多数节点是高度右倾的，这意味着大多数节点的度值较低，但少数节点，即所谓的“枢纽” ，度值较高。一些网络，特别是互联网、万维网和一些社交网络，被认为具有近似遵循幂定律的幂律分布:<math>

 

(如果平均度\langle k\rangle=p(n-1)</math>保持不变，也会出现有限节点的泊松分布)。然而，现实世界中的大多数网络的度分布与上述分布非常不同。大多数节点是高度右倾的，这意味着大多数节点的度值较低，但少数节点，即所谓的“枢纽” ，度值较高。一些网络，特别是互联网、万维网和一些社交网络，被认为具有近似遵循幂定律的幂律分布:<math>

P(k)\sim k^{-\gamma}

P(k)\sim k^{-\gamma}

</math>

</math>

</math>, where ''γ'' is a constant. Such networks are called [[scale-free networks]] and have attracted particular attention for their structural and dynamical properties<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>. However, recently, there have been some researches based on real-world data sets claiming despite the fact that most of the observed networks have [[Fat-tailed distribution|fat-tailed degree distributions]], they deviate from being [[Scale-free network|scale-free]].<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>  

where ''γ'' is a constant. Such networks are called [[scale-free networks]] and have attracted particular attention for their structural and dynamical properties<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>. However, recently, there have been some researches based on real-world data sets claiming despite the fact that most of the observed networks have [[Fat-tailed distribution|fat-tailed degree distributions]], they deviate from being [[Scale-free network|scale-free]].<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>, where γ is a constant. Such networks are called scale-free networks and have attracted particular attention for their structural and dynamical properties. However, recently, there have been some researches based on real-world data sets claiming despite the fact that most of the observed networks have fat-tailed degree distributions, they deviate from being scale-free.  

where γ is a constant. Such networks are called scale-free networks and have attracted particular attention for their structural and dynamical properties. However, recently, there have been some researches based on real-world data sets claiming despite the fact that most of the observed networks have fat-tailed degree distributions, they deviate from being scale-free.  

γ是一个常数。这种网络被称为'''<font color="#ff8000">无标度网络 Scale-Free Networks</font>'''，因其结构和动力学性质而引起人们的特别关注。然而，最近有一些基于真实数据的研究表明，尽管大多数观测到的网络具有'''<font color="#ff8000">肥尾度分布 Fat-Tailed Degree Distributions</font>'''，但它们无标度分布的特点并不明显。

γ是一个常数。这种网络被称为'''<font color="#ff8000">无标度网络 Scale-Free Networks</font>'''，因其结构和动力学性质而引起人们的特别关注。然而，最近有一些基于真实数据的研究表明，尽管大多数观测到的网络具有'''<font color="#ff8000">肥尾度分布 Fat-Tailed Degree Distributions</font>'''，但它们无标度分布的特点并不明显。

假设一个网络具有度分布<math>

假设一个网络具有度分布<math>

P(k)

P(k)

</math>, by selecting one node (randomly or not) and going to one of its neighbors (assuming to have one neighbor at least), then the probability of that node to have <math>

</math>,通过选择一个节点(随机或非随机)跟踪它的一个邻居(假设至少有一个邻居) ，那么该节点具有<math>

 

 

通过选择一个节点(随机或非随机)跟踪它的一个邻居(假设至少有一个邻居) ，那么该节点具有<math>

k

k

</math> 个邻居的概率不是由<math>

</math> 个邻居的概率不是由<math>

P(k)

P(k)

</math>.给出的

</math>.给出的原因在于，无论何时在异质网络中选择某个节点，它都更有可能通过跟随该节点的某个现有邻居到达枢纽节点。这些节点具有度<math>

 

 

 

 

 

原因在于，无论何时在异质网络中选择某个节点，它都更有可能通过跟随该节点的某个现有邻居到达枢纽节点。这些节点具有度<math>

k

k

</math>的真实概率是<math>

</math>的真实概率是<math>

q(k)

q(k)

</math>  

</math>，它被称为该节点的超额度。在'''<font color="#ff8000">配置模型 Configuration Model</font>'''中，忽略节点之间的相关性，并假定每个节点以相同的概率连接到网络中的其他任何节点，超额度分布表示为:

 

 

 

它被称为该节点的超额度。在'''<font color="#ff8000">配置模型 Configuration Model</font>'''中，忽略节点之间的相关性，并假定每个节点以相同的概率连接到网络中的其他任何节点，超额度分布表示为:

 

 

<math>

<math>

</math> is the mean-degree (average degree) of the model. It follows to that fact that the average degree of the neighbor of any node is greater than the average degree of that node. In social networks, it mean that your friends, on average, have more friends than you. This is famous as the [[friendship paradox]]. It can be shown that a network can have a [[giant component]], if its average excess degree is larger than one:

</math> is the mean-degree (average degree) of the model. It follows to that fact that the average degree of the neighbor of any node is greater than the average degree of that node. In social networks, it mean that your friends, on average, have more friends than you. This is famous as the [[friendship paradox]]. It can be shown that a network can have a [[giant component]], if its average excess degree is larger than one:

</math> is the mean-degree (average degree) of the model. It follows to that fact that the average degree of the neighbor of any node is greater than the average degree of that node. In social networks, it mean that your friends, on average, have more friends than you. This is famous as the friendship paradox. It can be shown that a network can have a giant component, if its average excess degree is larger than one:

</math> is the mean-degree (average degree) of the model. It follows to that fact that the average degree of the neighbor of any node is greater than the average degree of that node. In social networks, it mean that your friends, on average, have more friends than you. This is famous as the friendship paradox. It can be shown that a network can have a giant component, if its average excess degree is larger than one:

生成函数方法

生成函数方法

Generating functions can be used to calculate different properties of random networks. Given the degree distribution and the excess degree distribution of some network,  

[[Probability-generating function|Generating functions]] can be used to calculate different properties of random networks. Given the degree distribution and the excess degree distribution of some network, <math>

 

生成函数可以用来计算随机网络的不同性质。给定某些网络的度分布和超度分布，<math>

P(k)

P(k)

</math> 和 <math>

</math> and <math>

q(k)

q(k)

</math>

</math> respectively, it is possible to write two power series in the following forms:

 

 

respectively, it is possible to write two power series in the following forms:

 

 

可以以下列形式写出两个幂级数:

<math>

<math>

<math>

<math>

G_1(x)

G_1(x)

</math> 也可得出通过 <math>

</math> can also be obtained from derivatives of <math>

G_0(x)

G_0(x)

</math>的导数:

</math>:

<math>

<math>

</math>

</math>

 

If we know the generating function for a probability distribution <math>

 

If we know the generating function for a probability distribution  

</math> then we can recover the values of <math>

 

P(k)

If we know the generating function for a probability distribution

</math> by differentiating:

 

如果我们知道生成函数的一个概率分布，然后我们就得到<math>P(k)</math>的值通过鉴别：

<math>

<math>

</math>

</math>

 

Some properties, e.g. the moments, can be easily calculated from <math>

Some properties, e.g. the moments, can be easily calculated from  

G_0(x)  

 

</math> and its derivatives:

 

一些性质，例如，时刻，可以很容易地计算依据 < math > G0(x)</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>

And in general<ref name=":0" />:

And in general<ref name=":0" />:

* <math>

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

For [[Poisson distribution|Poisson]]-distributed random networks, such as the [[Erdős–Rényi model|ER graph]], <math>

For [[Poisson distribution|Poisson]]-distributed random networks, such as the [[Erdős–Rényi model|ER graph]], <math>

For Poisson-distributed random networks, such as the ER graph, <math>

m-1

</math> iterations of the function <math>

</math> acting on itself.<ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|url=https://link.aps.org/doi/10.1103/PhysRevE.64.026118|journal=Physical Review E|language=en|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|issn=1063-651X|doi-access=free}}</ref>

<math>

<math>

G_1(x) = G_0(x)

G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k

</math>这就是为什么这种类型的随机网络理论特别简单的原因。第一和第二近邻的概率分布是由函数<math>

</math> and <math>

G_0(x)  

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>G0(G1(x))</math>生成的

</math>

</math>. By extension, the distribution of <math>

如果我们知道生成函数的一个概率分布，然后我们就得到<math>P(k)</math>的值通过鉴别：

</math>. By extension, the distribution of <math>

<math>

</math>

继续扩展，<math>

一些性质，例如，时刻性。然后，可以很容易地进行计算依据<math>

</math>-th的邻居的分布

</math> 和它的导数:

</math>-th neighbors is generated by:

</math>

</math>-th neighbors is generated by:

 

是由以下几个因素产生的:

</math> 和<math>G0(G1(x))</math>生成的。进一步扩展，<math>

</math>-th的邻居的分布是由以下几个因素产生的:

第一个邻居的平均数量<math>

第一个邻居的平均数量<math>

<math>

<math>

{\langle k \rangle} = {dG_0(x)\over dx}|_{x=1}

{\langle k \rangle} = {dG_0(x)\over dx}|_{x=1}

</math>  

</math> 第二个邻居的平均数量是:

 

 

 

第二个邻居的平均数量是:

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

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)

[[File:Enwiki-degree-distribution.png|thumb|right|320px|

[[File:Enwiki-degree-distribution.png|thumb|right|320px|

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

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

In a directed network, each node has some in-degree <math>

In a directed network, each node has some in-degree <math>

 

in}

 

在有向网络中，每个节点都有一些入度k{in}

 

 

 

 

</math> and some out-degree <math>

</math> and some out-degree <math>

 

k_{out}

和一些出度k{out}

 

 

 

 

</math> which are the number of links which have run into and out of that node respectfully. If <math>

</math> which are the number of links which have run into and out of that node respectfully. If <math>

P(k_{in}, k_{out})

P(k_{in}, k_{out})

P(k_{in}, k_{out})

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

</math> is the probability that a randomly chosen node has in-degree <math>

</math> 和一些出度<math>

</math>分别指代的是指向该节点的边的数量和从该节点指出的边的数量。

如果 <math>

如果 <math>

P(k_{in}, k_{out})

P(k_{in}, k_{out})

</math> 是一个随机选择的具有入出度的节点的可能性

</math> 是一个随机选择的具有入出度的节点的可能性。那么分配给这个生成函数的'''<font color="#ff8000">联合概率分布  Joint Probability Distribution</font>'''可以被写成两个变量 <math>

 

 

</math> 和 <math>

</math> then the generating function assigned to this [[joint probability distribution]] can be written with two valuables <math>

y

 

</math>  

</math> then the generating function assigned to this joint probability distribution can be written with two valuables <math>

 

那么分配给这个生成函数的联合概率分布可以被写成两个变量 <math>x</math>和<math>y</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>  

Since every link in a directed network must leave some node and enter another, the net average number of links entering

Since every link in a directed network must leave some node and enter another, the net average number of links entering

Since every link in a directed network must leave some node and enter another, the net average number of links entering

a node is zero. Therefore,  

a node is zero. Therefore,

</math> is the mean degree (both in and out) of the nodes in the network; <math>

\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.  

所以,

由于有向网络中的每个链路必须离开某个节点并进入另一个节点，因此进入一个节点的链路的净平均数是零。所以,

</math>,

</math>,

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

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

</math>

</math>

 

<math>

 

c  

where <math>c

</math>是网络中节点的平均度(内部和外部)

 

where <math>c  

 

 

 

 

</math> is the mean degree (both in and out) of the nodes in the network; <math>

 

C是网络中节点的平均度(内部和外部)

<math>

<math>

\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.  

\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.  

</math>

</math>

Using the function <math>

Using the function <math>

\mathcal{G}(x,y)

\mathcal{G}(x,y)

</math>, we can again find the generation function for the in/out-degree distribution and in/out-excess degree distribution, as before. <math>

</math>, we can again find the generation function for the in/out-degree distribution and in/out-excess degree distribution, as before. <math>

G^{in}_0(x)  

G^{in}_0(x)  

</math> can be defined as generating functions for the number of arriving links at a randomly chosen node, and <math>

</math> can be defined as generating functions for the number of arriving links at a randomly chosen node, and <math>

G^{in}_1(x)

G^{in}_1(x)

G^{in}_1(x)

G^{in}_1(x) =  \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1}

</math>can be defined as the number of arriving links at a node reached by following a randomly chosen link. We can also define generating functions <math>

使用函数<math>

 

</math>can be defined as the number of arriving links at a node reached by following a randomly chosen link. We can also define generating functions <math>

</math>如前所述，我们可以再次找到入/出度分布和入/出超量度分布的生成函数。可以将<math>

 

<math>

</math>定义为一个随机选择的节点上到达的链接数的生成函数，以及 <math>

G^{in}_1(x)

G^{in}_1(x)

</math>可以定义为按照随机选择的链接到达一个节点的到达链接数。我们也可以定义生成函数 <math>

</math>可以定义为按照随机选择的链接到达一个节点的到达链接数。我们也可以定义生成函数 <math>

</math> 和 <math>

</math> 和 <math>

G^{out}_1(y)

G^{out}_1(y)

</math>

</math>表示离开节点的边的数量:

 

 

 

 

离开这样一个节点的数字:

</math>

</math>

Here, the average number of 1st neighbors, <math>

</math>.<ref name=":1" />

这里，第一个邻居的平均数量math>

这里，第一个邻居的平均数量math>

c

c

</math>，< math >

</math>，或者像之前表示的<math>

 

 

 

 

 

 

或者像之前表示的<math>

c_1

c_1

</math>是

</math>是

</math>

</math>

从一个随机选择的节点上可达到的第二邻居的平均数是<math>

从一个随机选择的节点上可达到的第二邻居的平均数是<math>

</math>. :

</math>. :

这些是从随机选择的节点所达到第一和第二邻居的数量，因为这些方程显然是在<math>

 

 

 

</math>. These are also the numbers of 1st and 2nd neighbors from which a random node can be reached, since these equations are manifestly symmetric in <math>

 

 

 

 

x

x

 

</math>和 <math>

 

</math> and <math>

 

</math> and <math>

 

 

y

y

</math>上对称的。

 

 

 

 

</math>.<ref name=":1" />

 

 

 

 

== See also ==

== See also ==