 Degree distribution

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.
Contents
Definition
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 greater than or equal to k.
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 (Bernoulli) random graph, in which each of n nodes is connected (or not) with independent probability p (or 1 − p), has a binomial distribution of degrees:
(or Poisson in the limit of large n). 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.
See also
References
 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. doi:10.1080/00018730110112519.
 Newman, M. E. J. (2003). "The structure and function of complex networks". SIAM Review 45 (2): 167–256. doi:10.1137/S003614450342480. http://siamdl.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SIREAD000045000002000167000001.
 Shlomo Havlin and Reuven Cohen (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press. http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php.
Categories: Graph theory
 Graph invariants
Wikimedia Foundation. 2010.
Look at other dictionaries:
Degree (graph theory) — A graph with vertices labeled by degree In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.[1] The degree of a vertex … Wikipedia
distribution theory — ▪ economics Introduction in economics, the systematic attempt to account for the sharing of the national income among the owners of the factors of production land, labour, and capital. Traditionally, economists have studied how the costs of … Universalium
degree — n. 1 a stage in an ascending or descending scale, series, or process. 2 a stage in intensity or amount (to a high degree; in some degree). 3 relative condition (each is good in its degree). 4 Math. a unit of measurement of angles, one ninetieth… … Useful english dictionary
degree — Extent, measure or scope of an action, condition or relation. Legal extent of guilt or negligence. Title conferred on graduates of school, college, or university. The state or civil condition of a person. The grade or distance one thing may be… … Black's law dictionary
degree — Extent, measure or scope of an action, condition or relation. Legal extent of guilt or negligence. Title conferred on graduates of school, college, or university. The state or civil condition of a person. The grade or distance one thing may be… … Black's law dictionary
degree of freedom — noun 1. (statistics) an unrestricted variable in a frequency distribution (Freq. 1) • Topics: ↑statistics • Hypernyms: ↑variable, ↑variable quantity 2. one of the minimum number of parameters needed to describe the state of a physical system … Useful english dictionary
Cauchy distribution — Not to be confused with Lorenz curve. Cauchy–Lorentz Probability density function The purple curve is the standard Cauchy distribution Cumulative distribution function … Wikipedia
Maxwell–Boltzmann distribution — Maxwell–Boltzmann Probability density function Cumulative distribution function parameters … Wikipedia
Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function … Wikipedia
Negative binomial distribution — Probability mass function The orange line represents the mean, which is equal to 10 in each of these plots; the green line shows the standard deviation. notation: parameters: r > 0 number of failures until the experiment is stopped (integer,… … Wikipedia