Content deleted Content added
Attic Salt (talk | contribs) →Observed degree distributions: Another undo of one of my reverts. |
m Open access bot: arxiv updated in citation with #oabot. |
||
| (22 intermediate revisions by 15 users not shown) | |||
Line 5:
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 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
:<math>P(k) = \frac{n_{k}}{n}</math>. 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''.
Line 16 ⟶ 17:
</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 [[
P(k)\sim k^{-\gamma}
</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 |
== 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|access-date=2020-04-19|archive-date=2020-04-15|archive-url=https://web.archive.org/web/20200415113429/https://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090|url-status=live}}</ref> In other words, it is the distribution of outgoing links from a node reached by following a link.
Suppose a network has a degree distribution <math>
Line 29 ⟶ 30:
</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
k
</math> is <math>
Line 44 ⟶ 45:
<math>
\sum_k kq(k) > 1 \Rightarrow {\langle k^2 \rangle}/{\langle k \rangle} - 1 >1 \Rightarrow {\langle k^2 \rangle}-2{\langle k \rangle}>0
</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" />
==
[[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)
Line 115 ⟶ 116:
</math> iterations of the function <math>
G_1
</math> acting on itself.<ref name=":1">{{Cite journal|
The average number of 1st neighbors, <math>
Line 149 ⟶ 150:
</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>
Line 210 ⟶ 209:
</math>.<ref name=":1" />
== Degree distribution for signed networks ==
In a signed network, each node has a positive-degree <math>
k_{
</math> and a negative degree <math>
k_{-}
</math> which are the positive number of links and negative number of links connected to that node respectfully. So <math>
P(k_{+})
</math> and <math>
P(k_{-})
</math> denote negative degree distribution and positive degree distribution of the signed network.<ref name="10.1038/s41598-021-81767-7">{{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = Topological impact of negative links on the stability of resting-state brain network | journal = Scientific Reports | date = January 2021 | volume = 11 | issue = 1 | page = 2176 | pmid = 33500525 | pmc = 7838299 | doi = 10.1038/s41598-021-81767-7 | url = }}</ref><ref name="10.1016/j.physa.2014.11.062">{{cite journal | vauthors = Ciotti V | title = Degree correlations in signed social networks | journal = Physica A: Statistical Mechanics and Its Applications | date = 2015 | volume = 422 | pages = 25–39 | doi = 10.1016/j.physa.2014.11.062 | url = https://www.sciencedirect.com/science/article/abs/pii/S0378437114010334 | arxiv = 1412.1024 | s2cid = 4995458 | access-date = 2021-02-10 | archive-date = 2021-10-02 | archive-url = https://web.archive.org/web/20211002175332/https://www.sciencedirect.com/science/article/abs/pii/S0378437114010334 | url-status = live }}</ref>
== See also ==
Line 235 ⟶ 246:
| doi = 10.1103/RevModPhys.74.47
| bibcode=2002RvMP...74...47A
| s2cid = 60545
▲}}
}}▼
* {{cite journal
| last = Dorogovtsev
Line 248 ⟶ 260:
| doi = 10.1080/00018730110112519
| issue = 4
|bibcode = 2002AdPhy..51.1079D
}}▼
* {{cite journal
|last=Newman
Line 261 ⟶ 274:
|arxiv=cond-mat/0303516
|bibcode=2003SIAMR..45..167N
|s2cid=221278130
▲}}
}}
▲}}
[[Category:Graph theory]]
| |||