| 第2行： |
第2行： |
| | 由CecileLi初步审校 | | 由CecileLi初步审校 |
| | 原文中neighbor翻译有点生硬，部分修改为邻近点后面的邻边想表示点集，集合的意思。 | | 原文中neighbor翻译有点生硬，部分修改为邻近点后面的邻边想表示点集，集合的意思。 |
| − |
| |
| − | {{Network Science}}
| |
| − |
| |
| − | In the study of [[Graph (discrete mathematics)|graphs]] and [[complex network|networks]], the [[degree (graph theory)|degree]] of a node in a network is the number of connections it has to other nodes and the '''degree distribution''' is the [[probability distribution]] of these degrees over the whole network.
| |
| − |
| |
| − | In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.
| |
| | | | |
| | 在'''<font color="#ff8000">图 Graphs</font>'''和'''<font color="#ff8000">网络 Networks</font>'''的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。 | | 在'''<font color="#ff8000">图 Graphs</font>'''和'''<font color="#ff8000">网络 Networks</font>'''的研究领域，网络节点的度是它与其他节点的连接数，而度分布就是整个网络中这些度的概率分布。 |
| | | | |
| − | ==Definition== | + | ==定义== |
| − | 定义
| |
| − | | |
| − | The [[degree (graph theory)|degree]] of a node in a network (sometimes referred to incorrectly as the [[Connectivity (graph theory)|connectivity]]) is the number of connections or [[Edge (graph theory)#Graph|edges]] the node has to other nodes. If a network is [[directed graph|directed]], meaning that edges point in one direction from one node to another node, then nodes have two different degrees, the in-degree, which is the number of incoming edges, and the out-degree, which is the number of outgoing edges.
| |
| − | | |
| − | The degree of a node in a network (sometimes referred to incorrectly as the connectivity) is the number of connections or edges the node has to other nodes. If a network is directed, meaning that edges point in one direction from one node to another node, then nodes have two different degrees, the in-degree, which is the number of incoming edges, and the out-degree, which is the number of outgoing edges.
| |
| | | | |
| | 网络中一个节点的度(有时会被误认为连通性)是该节点与其他节点的连接或边的数量。如果网络是有向的，它的边就可能沿着不同方向从一个节点指向另一个节点，那么这些节点们就会有两个不同的度，一个度表示入射边的数量，另一个度表示出射边的数量。 | | 网络中一个节点的度(有时会被误认为连通性)是该节点与其他节点的连接或边的数量。如果网络是有向的，它的边就可能沿着不同方向从一个节点指向另一个节点，那么这些节点们就会有两个不同的度，一个度表示入射边的数量，另一个度表示出射边的数量。 |
| − |
| |
| − |
| |
| − |
| |
| − | The degree distribution ''P''(''k'') of a network is then defined to be the fraction of nodes in the network with degree ''k''. Thus if there are ''n'' nodes in total in a network and ''n''<sub>''k''</sub> of them have degree ''k'', we have ''P''(''k'') = ''n''<sub>''k''</sub>/''n''.
| |
| − |
| |
| − | The degree distribution P(k) of a network is then defined to be the fraction of nodes in the network with degree k. Thus if there are n nodes in total in a network and n<sub>k</sub> of them have degree k, we have P(k) = n<sub>k</sub>/n.
| |
| | | | |
| | 度分布''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''。 |
| − |
| |
| − |
| |
| − |
| |
| − | The same information is also sometimes presented in the form of a ''cumulative degree distribution'', the fraction of nodes with degree smaller than ''k'', or even the ''complementary cumulative degree distribution'', the fraction of nodes with degree greater than or equal to ''k'' (1 - ''C'') if one considers ''C'' as the ''cumulative degree distribution''; i.e. the complement of ''C''.
| |
| − |
| |
| − | The same information is also sometimes presented in the form of a cumulative degree distribution, the fraction of nodes with degree smaller than k, or even the complementary cumulative degree distribution, the fraction of nodes with degree greater than or equal to k (1 - C) if one considers C as the cumulative degree distribution; i.e. the complement of C.
| |
| | | | |
| | 度分布的定义也可以用'''<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'')的节点比例）的形式表示，这一定义与积累度分布互补。 |
| | | | |
| − | == Observed degree distributions == | + | == 观察度分布 == |
| − | 观察度分布
| |
| − | | |
| − | The degree distribution is very important in studying both real networks, such as the [[Internet]] and [[social networks]], and theoretical networks. The simplest network model, for example, the (Erdős–Rényi model) [[random graph]], in which each of ''n'' nodes is independently connected (or not) with probability ''p'' (or 1 − ''p''), has a [[binomial distribution]] of degrees ''k'':
| |
| − | | |
| − | The degree distribution is very important in studying both real networks, such as the Internet and social networks, and theoretical networks. The simplest network model, for example, the (Erdős–Rényi model) random graph, in which each of n nodes is independently connected (or not) with probability p (or 1 − p), has a binomial distribution of degrees k:
| |
| | | | |
| | 度分布无论是在研究真实网络(如互联网和社会网络)中还是在理论网络中都非常重要。以最简单的网络模型(Erdős–Rényi 模型)w | | 度分布无论是在研究真实网络(如互联网和社会网络)中还是在理论网络中都非常重要。以最简单的网络模型(Erdős–Rényi 模型)w |
| | '''<font color="#ff8000">随机图 Random Graph</font>'''为例，它的每''n''个节点都以概率''p'' (或1 − ''p'')独立连接(或不独立连接) ，其中'''<font color="#ff8000">二项分布 Binomial Distribution</font>'''的度值为''k'': | | '''<font color="#ff8000">随机图 Random Graph</font>'''为例，它的每''n''个节点都以概率''p'' (或1 − ''p'')独立连接(或不独立连接) ，其中'''<font color="#ff8000">二项分布 Binomial Distribution</font>'''的度值为''k'': |
| − |
| |
| | | | |
| | :<math> | | :<math> |
| | P(k) = {n-1\choose k} p^k (1 - p)^{n-1-k}, | | P(k) = {n-1\choose k} p^k (1 - p)^{n-1-k}, |
| | </math> | | </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]]:
| |
| − |
| |
| − |
| |
| − |
| |
| − | (or 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 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:
| |
| − |
| |
| | | | |
| | (即使平均度\langle k\rangle=p(n-1)</math>保持不变，也会出现有限节点的泊松分布)。现实世界中的大多数网络的度分布却往往与上述分布非常不同，它们的大多数节点是高度右倾的，这就意味着这些节点的度值较低，但少数节点，即所谓的“枢纽” ，度值较高。一些网络，尤其是互联网、万维网和一些社交网络，被认为具有近似遵循幂定律的幂律分布:<math> | | (即使平均度\langle k\rangle=p(n-1)</math>保持不变，也会出现有限节点的泊松分布)。现实世界中的大多数网络的度分布却往往与上述分布非常不同，它们的大多数节点是高度右倾的，这就意味着这些节点的度值较低，但少数节点，即所谓的“枢纽” ，度值较高。一些网络，尤其是互联网、万维网和一些社交网络，被认为具有近似遵循幂定律的幂律分布:<math> |
| 第65行： |
第26行： |
| | </math> | | </math> |
| | | | |
| − | | + | 其中γ是一个常数。这种网络被称为'''<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> |
| − | 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. 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>'''，但它们无标度分布的特点并不明显。
| |
| | | | |
| | == Excess degree distribution == | | == Excess degree distribution == |