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.

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.

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 nk of them have degree k, we have 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. 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

Most networks in the real world, however, have degree distributions very different from this.

Most are highly right-skewed, 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 were argued to have degree distributions that approximately follow a power law:

[1][2][3][4] 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.

The reason is that, whenever some node is selected in a heterogeneous network, it is more probable to reach the hubs by following one of the existing neighbors of that node.

which is called the excess degree of that node.

is the mean-degree (average degree) of the model.

It follows from that, that the average degree of the neighbor of any node is greater than the average degree of that node.

It can be shown that a network can have a giant component, if its average excess degree is larger than one:

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.

[5] Generating functions can be used to calculate different properties of random networks.

respectively, it is possible to write two power series in the following forms:

If we know the generating function for a probability distribution

Some properties, e.g. the moments, can be easily calculated from

and its derivatives: And in general:[5] For Poisson-distributed random networks, such as the ER graph,

, that is the reason why the theory of random networks of this type is especially simple.

The probability distributions for the 1st and 2nd-nearest neighbors are generated by the functions

which are the number of links which have run into and out of that node respectfully.

is the probability that a randomly chosen node has in-degree

then the generating function assigned to this joint probability distribution can be written with two valuables

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

is the mean degree (both in and out) of the nodes in the network;

can be defined as generating functions for the number of arriving links at a randomly chosen node, and

can be defined as the number of arriving links at a node reached by following a randomly chosen link.

and the average number of 2nd neighbors reachable from a randomly chosen node is given by:

These are also the numbers of 1st and 2nd neighbors from which a random node can be reached, since these equations are manifestly symmetric in