863
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 本词条由Ryan初步翻译+ − 由CecileLi初步审校+ − 原文中neighbor翻译有点生硬，部分修改为邻近点后面的邻边想表示点集，集合的意思。+ + 第28行：
第29行： − + − 超额度分布 − − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）同样 标题为专业名词的 可以把正文中对应的专业名词进行标注标橙 − 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> − + 第72行：
第48行： − − 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: − − − − − − 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. − + − − − − [[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> − 第254行：
第135行： − − 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> − 第295行：
第153行： − − − − 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> − − − − 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} 第396行：
第203行： − − − 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" /> − 第432行：
第221行： − + + + + − + − '''<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]] − − * [[Structural cut-off]] − '''<font color="#ff8000">结构截止值 Structural Cut-off</font>''' − --[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）该部分也为专业名词 需要进行标橙 − + + + + 第736行：
第521行： − + − + − Category:Graph theory+ − + − 范畴: 图论 − − − Category:Graph invariants+ − 类别: 图形不变量+ − + + − Category:Network theory − 范畴: 网络理论 − + + − <small>This page was moved from [[wikipedia:en:Degree distribution]]. Its edit history can be viewed at [[度分布/edithistory]]</small></noinclude>+ − + +
无编辑摘要
{{#seo:
|keywords=度分布,图形不变量,网络理论
|description=图论,图形不变量,网络理论
}}
在'''<font color="#ff8000">图 Graphs</font>'''和'''<font color="#ff8000">网络 Networks</font>'''的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。
在'''<font color="#ff8000">图 Graphs</font>'''和'''<font color="#ff8000">网络 Networks</font>'''的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。
其中γ是一个常数。这种网络被称为'''<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 ==
== 超额度分布 ==
'''<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>
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>{\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>
要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。
要注意的是，最后两个方程只适用于配置模型，想要准确推导出实词网络的超额度分布，还应考虑度相关性。
== The Generating Functions Method ==
== '''<font color="#ff8000">函数生成方法 Generating Functions Method</font>''' ==
'''<font color="#ff8000">函数生成方法 Generating Functions Method</font>'''
生成函数可以用来计算随机网络的不同性质。给定某些网络的度分布和超度分布，<math>
生成函数可以用来计算随机网络的不同性质。给定某些网络的度分布和超度分布，<math>
[[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) 维基百科超链接图(对数尺度)的入/出度分布]]
在有向网络中，每个节点都有一些入度<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>
</math>是网络中节点的平均度(内部和外部)<math>
</math>是网络中节点的平均度(内部和外部)<math>
\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.
\langle{k_{in}}\rangle = \langle{k_{out}}\rangle = c.
</math>
</math>
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>
这里，第一邻边内点的平均数量math>
这里，第一邻边内点的平均数量math>
</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">随机网络 Random Graph</font>'''
== References ==
* '''<font color="#ff8000">结构截止值 Structural Cut-off</font>'''
== 参考==
{{Reflist}}
{{Reflist}}
[[Category:Graph theory]]
==编者推荐==
[[File:Last1.png|400px|thumb|right|[https://swarma.org/?p=13364 用神经学习模型计算海量实际网络中的节点中心性度量 | 论文速递1篇|集智俱乐部]]]
===集智文章推荐===
====[https://swarma.org/?p=13364 用神经学习模型计算海量实际网络中的节点中心性度量 | 论文速递1篇|集智俱乐部]====
[[Category:Graph invariants]]
<br/><br/>
===博客推荐===
[[Category:Network theory]]
====[http://blog.sina.com.cn/s/blog_72ef7bea0102v748.html 社交网络分析：网络中心性]====
该篇博客为社会网络分析的笔记内容，有作者自己的思考，可从不同角度给予灵感。
<noinclude>
<br/>
----
本中文词条由[[用户:Ryan|Ryan]] 参与编译， [[用户:CecileLi|CecileLi]][[用户:趣木木|趣木木]] 审校，[[用户:不是海绵宝宝|不是海绵宝宝]]、[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。
[[Category:待整理页面]]
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[分类: 图论]] [[分类: 图形不变量]] [[分类: 网络理论]]