DEGREE DISTRIBUTION

In graph theory, 'degree distribution' gives the probability distribution of degrees in a network.
Its use originates from the study of random graph by Paul Erdős and Alfréd Rényi Erdos, P. and Renyi, A., 1959, Publ. Math. (Debrecen) '6', 290., and it has become an important concept which describes the topology of complex networks.
__TOC__

Contents

Definition

Degree

Degree distribution

Degree distribution of various networks

Reference

References

Definition

Degree

The degree of a node (or connectivity) is, '$k$', tells how many links (or edges) the node has to other nodes.
In directed networks nodes has two types of degrees. The incoming
degree ''k''_in denotes the number of links that point to a node,
and an outgoing degree ''k''_out denotes the number of links that
start from it. An undirected network with '''N''' nodes and '''L''' links is
characterized by an average degree '$=\; 2L/N$' (where <> denotes
the average)A.-L. Barabási and Z. N. Oltvai, Nature Reviews Genetics 5, 101-113 (2004).

Degree distribution

The degree distribution, '$P(k)$', is a function describing the total number of vertices in a graph with a given degree (number of connections to other vertices).
Formally, the degree distribution is
:$p(k)\; =\; sum\_\{v\; in\; V\; |\; deg(v)=k\}\; 1$
where ''v'' is a vertex in the set of the graph's vertices ''V'', and $deg(v)$ is the degree of vertex v.
This same information is often presented as the ''cumulative degree distribution'',
:$P\_k\; =\; sum\_\{k\text{'}\; =\; k\}^\{infty\}\; p\_\{k\text{'}\}$.

Degree distribution of various networks

Different types of complex network have different characteristic of degree distributions '$P(k)$'. Thus, the shape of a degree distribution allows us to distinguish between different classes of networks.
For example, the Erdős-Rényi random network has Poisson distribution R. Albert and A.-L. Barabási, Reviews of Modern Physics 74, 47-97 (2002).,
:$P(k\_i\; =\; k)\; =\; C^k\_\{N-1\}p^k(1\; -\; p)^\{N-1-k\}$ ,
and the peaked degree distribution of random network indicates that the system has a characteristic degree and that there are no highly connected nodes (which are also known as hubs). By contrast, for scale-free networks, a power-law degree distribution
$P(k)\; sim\; k^\{-\; gamma\}$
indicates that a few hubs hold together numerous small nodes.

Reference

References

★ Newman, Mark E.J. "The structure and function of complex networks".