“度分布”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第1行： 第1行：
−
本词条由Ryan初步翻译
+
{{#seo:
−
由CecileLi初步审校
+
|keywords=度分布,图形不变量,网络理论
−
原文中neighbor翻译有点生硬，部分修改为邻近点后面的邻边想表示点集，集合的意思。
+
|description=图论,图形不变量,网络理论
 +
}}
  
 
在'''<font color="#ff8000">图 Graphs</font>'''和'''<font color="#ff8000">网络 Networks</font>'''的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。
 
在'''<font color="#ff8000">图 Graphs</font>'''和'''<font color="#ff8000">网络 Networks</font>'''的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。
第28行： 第29行：
 
其中γ是一个常数。这种网络被称为'''<font color="#ff8000">无标度网络 Scale-Free Networks</font>'''，它因其结构和动力学性质而引起人们的重视。<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>  
 
其中γ是一个常数。这种网络被称为'''<font color="#ff8000">无标度网络 Scale-Free Networks</font>'''，它因其结构和动力学性质而引起人们的重视。<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>  
  
−
== Excess degree distribution ==
+
== 超额度分布 ==
−
超额度分布
 
−
 
 
−
  --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）同样 标题为专业名词的  可以把正文中对应的专业名词进行标注标橙
 
−
Excess degree distribution is the probability distribution, for a node reached by following an edge, of the number of other edges attached to that node.<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> In other words, it is the distribution of outgoing links from a node reached by following a link.
 
−
 
 
−
Excess degree distribution is the probability distribution, for a node reached by following an edge, of the number of other edges attached to that node. In other words, it is the distribution of outgoing links from a node reached by following a link.
 
−
 
 
−
'''<font color="#ff8000">超额度分布 Excess Degree Distribution</font>'''的定义是：沿着一条边到达该节点的其他边的数量的概率分布。换句话说，它是通过跟随链接从一个节点到达的其传出链接的分布。
 
−
 
 
−
 
 
−
Suppose a network has a degree distribution <math>
 
−
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>
 
−
k
 
−
</math> neighbors is not given by <math>
 
−
P(k)
 
−
</math>. The reason is that, whenever some node is selected in a heterogeneous network, it is more probable to reach the hobs by following one of the existing neighbors of that node. The true probability of such nodes to have degree <math>
 
−
k
 
−
</math> is <math>
 
−
q(k)
 
−
</math> which is called the ''excess degree'' of that node. In the [[configuration model]], which correlations between the nodes have been ignored and every node is assumed to be connected to any other nodes in the network with the same probability, the excess degree distribution can be found as<ref name=":0" />:
 
−
 
 
−
<math>
 
−
q(k) = \frac{k+1}{\langle k \rangle}P(k+1),
 
−
</math>
 
−
 
 
  
 +
'''<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>
第72行： 第48行：
 
q(k) =  \frac{k+1}{\langle k \rangle}P(k+1),
 
q(k) =  \frac{k+1}{\langle k \rangle}P(k+1),
 
</math>
 
</math>
−
 
−
where <math>
 
−
{\langle k \rangle}
 
−
</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:
 
−
 
−
 
−
where <math>
 
−
{\langle k \rangle}
 
−
</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>{\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>
 
\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>
−
 
−
 
−
 
−
Bear in mind that the last two equations are just for the [[configuration model]] and to derive the excess degree distribution of a real-word network, we should also add degree correlations into account.<ref name=":0" />
 
−
 
−
Bear in mind that the last two equations are just for the configuration model and to derive the excess degree distribution of a real-word network, we should also add degree correlations into account.
 
  
 
要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。
 
要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。
  
−
== The Generating Functions Method ==
+
== '''<font color="#ff8000">函数生成方法 Generating Functions Method</font>''' ==
−
'''<font color="#ff8000">函数生成方法 Generating Functions Method</font>'''
 
−
 
 
−
 
 
−
[[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>
 
−
P(k)
 
−
</math> and <math>
 
−
q(k)
 
−
</math> respectively, it is possible to write two power series in the following forms:
 
−
 
 
−
<math>
 
−
G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k
 
−
</math> and <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}
 
−
</math>
 
−
 
 
−
<math>
 
−
G_1(x)
 
−
</math> can also be obtained from derivatives of <math>
 
−
G_0(x)
 
−
</math>:
 
−
 
 
−
<math>
 
−
G_1(x) = \frac{G'_0(x)}{G'_0(1)}
 
−
</math>
 
−
 
 
−
If we know the generating function for a probability distribution <math>
 
−
P(k)
 
−
</math> then we can recover the values of <math>
 
−
P(k)
 
−
</math> by differentiating:
 
−
 
 
−
<math>
 
−
P(k) = \frac{1}{k!} {\operatorname{d}^k\!G\over\operatorname{d}\!x^k}\biggl \vert _{x=0}
 
−
</math>
 
−
 
 
−
Some properties, e.g. the moments, can be easily calculated from <math>
 
−
G_0(x)
 
−
</math> and its derivatives:
 
−
 
 
−
*<math>
 
−
{\langle k \rangle} = G'_0(1)
 
−
</math>
 
−
*<math>
 
−
{\langle k^2 \rangle} = G''_0(1) + G'_0(1)
 
−
</math>
 
−
 
 
−
And in general<ref name=":0" />:
 
−
 
 
−
* <math>
 
−
{\langle k^m \rangle} = \Biggl[{\bigg(\operatorname{x}{\operatorname{d}\!\over\operatorname{dx}\!}\biggl)^m}G_0(x)\Biggl]_{x=1}
 
−
</math>
 
−
 
 
−
For [[Poisson distribution|Poisson]]-distributed random networks, such as the [[Erdős–Rényi model|ER graph]], <math>
 
−
G_1(x) = G_0(x)
 
−
</math>, that is the reason why the theory of random networks of this type is especially simple. The probability distributions for the 1st and 2nd-nearest neighbors are generated by the functions <math>
 
−
G_0(x)
 
−
</math> and <math>
 
−
G_0(G_1(x))
 
−
</math>. By extension, the distribution of <math>
 
−
m
 
−
</math>-th neighbors is generated by:
 
−
 
 
−
<math>
 
−
G_0\bigl(G_1(...G_1(x)...)\bigr)
 
−
</math>, with <math>
 
−
m-1
 
−
</math> iterations of the function <math>
 
−
G_1
 
−
</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>
 
−
 
 
−
The average number of 1st neighbors, <math>
 
−
c_1
 
−
</math>, is <math>
 
−
{\langle k \rangle} = {dG_0(x)\over dx}|_{x=1}
 
−
</math> and the average number of 2nd neighbors is: <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>
第254行： 第135行：
 
[[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>
 
−
k_{
 
−
in}
 
−
</math> and some out-degree <math>
 
−
k_{out}
 
−
</math> which are the number of links which have run into and out of that node respectfully. If <math>
 
−
P(k_{in}, k_{out})
 
−
</math> is the probability that a randomly chosen node has in-degree <math>
 
−
k_{
 
−
in}
 
−
</math> and out-degree <math>
 
−
k_{out}
 
−
</math> then the generating function assigned to this [[joint probability distribution]] can be written with two valuables <math>
 
−
x
 
−
</math> and <math>
 
−
y
 
−
</math> as:
 
−
 
−
<math>
 
−
\mathcal{G}(x,y) =  \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} .
 
−
</math>
 
−
 
  
 
在有向网络中，每个节点都有一些入度<math>
 
在有向网络中，每个节点都有一些入度<math>
第295行： 第153行：
 
\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
 
−
 
−
a node is zero. Therefore,
 
−
 
−
<math>
 
−
\langle{k_{in}-k_{out}}\rangle =\sum_{k_{in},k_{out}} \displaystyle (k_{in}-k_{out})P({k_{in},k_{out}}) = 0
 
−
</math>,
 
−
 
−
which implies that, the generation function must satisfy:
 
−
 
−
<math>
 
−
{\partial \mathcal{G}\over\partial x}\vert _{x,y=1} =  {\partial \mathcal{G}\over\partial y}\vert _{x,y=1} = c,
 
−
 
−
</math>
 
−
 
−
where <math>
 
−
c
 
−
</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>
 
−
 
  
  
第340行： 第174行：
 
</math>是网络中节点的平均度(内部和外部)<math>
 
</math>是网络中节点的平均度(内部和外部)<math>
 
\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.  
 
\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.  
−
</math>
 
−
 
−
 
−
 
−
Using the function <math>
 
−
\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>
 
−
G^{in}_0(x)
 
−
</math> can be defined as generating functions for the number of arriving links at a randomly chosen node, and <math>
 
−
G^{in}_1(x)
 
−
</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>
 
−
G^{out}_0(y)
 
−
</math> and <math>
 
−
G^{out}_1(y)
 
−
</math> for the number leaving such a node:<ref name=":1" />
 
−
 
−
* <math>
 
−
G^{in}_0(x) = \mathcal{G}(x,1)
 
−
</math>
 
−
* <math>
 
−
G^{in}_1(x) =  \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1}
 
−
</math>
 
−
* <math>
 
−
G^{out}_0(y) = \mathcal{G}(1,y)
 
−
</math>
 
−
* <math>
 
−
G^{out}_1(y) =  \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1}
 
 
</math>
 
</math>
  
第396行： 第203行：
 
G^{out}_1(y) =  \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1}  
 
G^{out}_1(y) =  \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1}  
 
</math>
 
</math>
−
 
−
 
−
Here, the average number of 1st neighbors, <math>
 
−
c
 
−
</math>, or as previously introduced as <math>
 
−
c_1
 
−
</math>, is <math>
 
−
{\partial \mathcal{G}\over\partial x}\biggl \vert _{x,y=1} =  {\partial \mathcal{G}\over\partial y}\biggl \vert _{x,y=1}
 
−
 
−
</math> and the average number of 2nd neighbors reachable from a randomly chosen node is given by: <math>
 
−
c_2 = G_1'(1)G'_0(1) ={\partial^2 \mathcal{G}\over\partial x\partial y}\biggl \vert _{x,y=1}
 
−
</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
 
−
</math> and <math>
 
−
y
 
−
 
−
</math>.<ref name=":1" />
 
−
 
  
 
这里，第一邻边内点的平均数量math>
 
这里，第一邻边内点的平均数量math>
第432行： 第221行：
 
</math>上对称的。
 
</math>上对称的。
  
−
== See also ==
+
== 参见 ==
 +
* '''<font color="#ff8000">图论 Graph Theory</font>'''
  
 +
* '''<font color="#ff8000">复杂网络 Complex Network</font>'''
  
 +
* '''<font color="#ff8000">无标度网络 Scale-free Network</font>'''
  
−
* [[Graph theory]]
+
* '''<font color="#ff8000">随机网络 Random Graph</font>'''
−
'''<font color="#ff8000">图论 Graph Theory</font>'''
 
−
* [[Complex network]]
 
−
'''<font color="#ff8000">复杂网络 Complex Network</font>'''
 
−
* [[Scale-free network]]
 
−
'''<font color="#ff8000">无标度网络 Scale-free Network</font>'''
 
−
* [[Random graph]]
 
−
'''<font color="#ff8000">随机网络 Random Graph</font>'''
 
−
* [[Structural cut-off]]
 
−
'''<font color="#ff8000">结构截止值 Structural Cut-off</font>'''
 
−
  --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）该部分也为专业名词 需要进行标橙
 
  
−
== References ==
+
* '''<font color="#ff8000">结构截止值 Structural Cut-off</font>'''
 +
 
 +
 
 +
== 参考==
  
 
{{Reflist}}
 
{{Reflist}}
第736行： 第521行：
  
  
−
[[Category:Graph theory]]
+
==编者推荐==
−
 
+
[[File:Last1.png|400px|thumb|right|[https://swarma.org/?p=13364 用神经学习模型计算海量实际网络中的节点中心性度量 | 论文速递1篇|集智俱乐部]]]
−
Category:Graph theory
+
===集智文章推荐===
−
 
+
====[https://swarma.org/?p=13364 用神经学习模型计算海量实际网络中的节点中心性度量 | 论文速递1篇|集智俱乐部]====
−
范畴: 图论
 
−
 
 
−
[[Category:Graph invariants]]
 
  
−
Category:Graph invariants
+
<br/><br/>
  
−
类别: 图形不变量
+
===博客推荐===
  
−
[[Category:Network theory]]
+
====[http://blog.sina.com.cn/s/blog_72ef7bea0102v748.html 社交网络分析：网络中心性]====
 +
该篇博客为社会网络分析的笔记内容，有作者自己的思考，可从不同角度给予灵感。
  
−
Category:Network theory
 
  
−
范畴: 网络理论
 
  
−
<noinclude>
+
<br/>
 +
----
  
−
<small>This page was moved from [[wikipedia:en:Degree distribution]]. Its edit history can be viewed at [[度分布/edithistory]]</small></noinclude>
+
本中文词条由[[用户:Ryan|Ryan]] 参与编译， [[用户:CecileLi|CecileLi]][[用户:趣木木|趣木木]] 审校，[[用户:不是海绵宝宝|不是海绵宝宝]]、[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。
  
−
[[Category:待整理页面]]
+
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
 +
[[分类: 图论]] [[分类: 图形不变量]] [[分类: 网络理论]]

2020年10月28日 (三) 20:01的版本


在图 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]

要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。

函数生成方法 Generating Functions Method

生成函数可以用来计算随机网络的不同性质。给定某些网络的度分布和超度分布，[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协议。

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