Degree distribution

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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

Degree distribution for directed networks Degree distribution_section_4

Since every link in a directed network must leave some node and enter another, the net average number of links entering Degree distribution_sentence_10

a node is zero. Degree distribution_sentence_11

Therefore, Degree distribution_sentence_12

which implies that, the generation function must satisfy: Degree distribution_sentence_13

See also Degree distribution_section_5

Degree distribution_unordered_list_0


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Degree distribution.