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. Degree distribution_sentence_0

Definition Degree distribution_section_0

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. Degree distribution_sentence_1

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. Degree distribution_sentence_2

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. Degree distribution_sentence_3

Observed degree distributions Degree distribution_section_1

The degree distribution is very important in studying both real networks, such as the Internet and social networks, and theoretical networks. Degree distribution_sentence_4

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: Degree distribution_sentence_5

Excess degree distribution Degree distribution_section_2

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. Degree distribution_sentence_6

In other words, it is the distribution of outgoing links from a node reached by following a link. Degree distribution_sentence_7

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. Degree distribution_sentence_8

The Generating Functions Method Degree distribution_section_3

And in general: Degree distribution_sentence_9