Degree distribution
Network science  

Network types  
Graphs  


Models  


 
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.
Definition[edit]
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 indegree, which is the number of incoming edges, and the outdegree, 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_{k} of them have degree k, we have P(k) = n_{k}/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).
Observed degree distributions[edit]
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:
(or Poisson in the limit of large n, if the average degree is held fixed). Most networks in the real world, however, have degree distributions very different from this. Most are highly rightskewed, 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 are found to have degree distributions that approximately follow a power law: P(k) ~ k^{−γ}, where γ is a constant. Such networks are called scalefree networks and have attracted particular attention for their structural and dynamical properties.^{[1]}^{[2]}^{[3]}</ref>^{[4]}
See also[edit]
References[edit]
 ^ Barabási, AlbertLászló; Albert, Réka (19991015). "Emergence of Scaling in Random Networks". Science. American Association for the Advancement of Science (AAAS). 286 (5439): 509–512. arXiv:condmat/9910332. doi:10.1126/science.286.5439.509. ISSN 00368075.
 ^ Albert, Réka; Barabási, AlbertLászló (20001211). "Topology of Evolving Networks: Local Events and Universality" (PDF). Physical Review Letters. American Physical Society (APS). 85 (24): 5234–5237. doi:10.1103/physrevlett.85.5234. ISSN 00319007.
 ^ Dorogovtsev, S. N.; Mendes, J. F. F.; Samukhin, A. N. (20010521). "Sizedependent degree distribution of a scalefree growing network". Physical Review E. American Physical Society (APS). 63 (6): 062101. arXiv:condmat/0011115. doi:10.1103/physreve.63.062101. ISSN 1063651X.
 ^ Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Scalefree behavior of networks with the copresence of preferential and uniform attachment rules". Physica D: Nonlinear Phenomena. arXiv:1704.08597. Bibcode:2018PhyD..371....1P. doi:10.1016/j.physd.2018.01.005.
 Albert, R.; Barabasi, A.L. (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74: 47–97. arXiv:condmat/0106096. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
 Dorogovtsev, S.; Mendes, J. F. F. (2002). "Evolution of networks". Advances in Physics. 51 (4): 1079–1187. arXiv:condmat/0106144. Bibcode:2002AdPhy..51.1079D. doi:10.1080/00018730110112519.
 Newman, M. E. J. (2003). "The structure and function of complex networks". SIAM Review. 45 (2): 167–256. arXiv:condmat/0303516. Bibcode:2003SIAMR..45..167N. doi:10.1137/S003614450342480.^{[permanent dead link]}
 Shlomo Havlin & Reuven Cohen (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.