Degree distributions
The degree distribution describes how connectivity varies across the nodes of a network. It moves from the degree of one node to a population-level description of network heterogeneity.
Degree as a node property
For a simple undirected network with adjacency matrix \(A\), the degree of node \(i\) is
\[k_i=\sum_jA_{ij}.\]If the network contains \(N\) nodes, the observed degrees are
\[k_1,k_2,\ldots,k_N.\]Empirical degree distribution
Let \(N_k\) be the number of nodes having degree \(k\). The empirical degree distribution is
\[\boxed{P(k)=\frac{N_k}{N}}.\]Thus \(P(k)\) is the probability that a uniformly randomly selected node has degree \(k\).
Because every node has some degree,
\[\boxed{\sum_{k=0}^{N-1}P(k)=1}.\]For an idealised distribution with unbounded support, the upper limit is written as infinity.
A simple example
Suppose six nodes have degrees
\[1,1,2,2,2,4.\]Then
\[P(1)=\frac26,\qquad P(2)=\frac36,\qquad P(4)=\frac16,\]and all other observed degree probabilities are zero.
Mean degree
The mean degree is the first moment of the degree distribution:
\[\boxed{\langle k\rangle=\sum_k kP(k)}.\]For a finite undirected graph, this agrees with the handshaking identity:
\[\langle k\rangle=\frac{2|E|}{N}.\]Second moment
The second moment is
\[\boxed{\langle k^2\rangle=\sum_k k^2P(k)}.\]It gives greater weight to high-degree nodes and becomes important in spreading processes on heterogeneous networks.
Variance of degree
The degree variance is
\[\boxed{\operatorname{Var}(K)=\langle k^2\rangle-\langle k\rangle^2}.\]A small variance means degrees are concentrated near the mean. A large variance indicates stronger degree heterogeneity.
Regular networks
If every node has exactly degree \(k_0\), then
\[P(k)=\begin{cases}1,&k=k_0,\\0,&k\ne k_0.\end{cases}\]Therefore
\[\langle k\rangle=k_0,\qquad\operatorname{Var}(K)=0.\]This is the narrowest possible degree distribution.
Broad degree distributions
A broad distribution contains nodes with substantially different numbers of connections. In a contact network, this means some individuals have many more potential transmission contacts than others.
Such heterogeneity can alter early epidemic growth and the effectiveness of targeted interventions.
Random node versus random edge
Choosing a node uniformly at random gives degree distribution \(P(k)\). Arriving at a node by following a randomly selected edge gives a different distribution.
A degree-\(k\) node has \(k\) edges through which it can be reached, so it is sampled in proportion to \(k\). Hence
\[\boxed{Q(k)=\frac{kP(k)}{\langle k\rangle}}.\]This is the degree distribution seen at the end of a randomly followed edge.
Excess degree
If we reach a degree-\(k\) node along one edge, only
\[k-1\]other edges remain available to continue a path.
The mean excess degree is therefore
\[\sum_k(k-1)Q(k).\]Substituting \(Q(k)\) gives
\[\boxed{\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}}.\]This quantity is central to branching approximations for locally tree-like random networks.
Why \(\langle k^2\rangle\) matters for epidemics
An infection reached through an edge is more likely to arrive at a high-degree node. That node may then have many remaining edges through which infection can spread.
Consequently, epidemic potential can depend on both
\[\langle k\rangle\quad\text{and}\quad\langle k^2\rangle,\]not simply on average degree.
A network branching condition
For a configuration-model network with independent transmission probability \(T\) across each edge, an early locally tree-like epidemic has mean number of onward successful transmissions approximately
\[\boxed{R_{\mathrm{edge}}=T\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}}.\]A giant transmission process becomes possible when this quantity exceeds one, under the assumptions of the model.
Poisson degree distribution
A common random-network degree distribution is Poisson:
\[\boxed{P(k)=e^{-z}\frac{z^k}{k!}},\]where
\[\langle k\rangle=z.\]For a Poisson distribution,
\[\operatorname{Var}(K)=z\]and
\[\langle k^2\rangle=z^2+z.\]Therefore the mean excess degree is also \(z\).
Heavy-tailed degree distributions
Some observed networks contain a small number of nodes with extremely large degree relative to most nodes. Such distributions are often described as heavy-tailed.
A power-law form is sometimes written
\[P(k)\propto k^{-\gamma}.\]However, observing a few highly connected nodes is not sufficient evidence that a network truly follows a power law. Statistical model comparison is needed.
Finite networks have finite maximum degree
In a simple network of \(N\) nodes,
\[0\le k\le N-1.\]Thus empirical degree distributions are always finite. Infinite-support distributions such as Poisson or ideal power laws are mathematical approximations to finite networks.
Cumulative degree distribution
The tail probability
\[P(K\ge k)=\sum_{j=k}^{\infty}P(j)\]gives the fraction of nodes with degree at least \(k\).
This can be useful when examining the frequency of highly connected nodes.
Generating function
The probability generating function of the degree distribution is
\[\boxed{G_0(x)=\sum_{k=0}^{\infty}P(k)x^k}.\]It satisfies
\[G_0(1)=1\]and
\[G_0'(1)=\langle k\rangle.\]Generating functions provide a compact way to derive component-size and epidemic results in random-network models.
Excess-degree generating function
The distribution reached by following an edge has generating function
\[\boxed{G_1(x)=\frac{G_0'(x)}{G_0'(1)}}.\]Its derivative at one gives the mean excess degree:
\[G_1'(1)=\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}.\]Directed networks
A directed network has both in-degree and out-degree. Its structure may require a joint distribution
\[P(k_{\mathrm{in}},k_{\mathrm{out}}),\]because knowing the marginal distributions separately does not reveal whether highly connected receivers are also highly connected senders.
Weighted networks
Degree counts neighbours, whereas weighted networks also contain interaction strengths. Two nodes can have the same degree but very different total contact intensity.
The corresponding node strength is
\[s_i=\sum_jw_{ij}.\]A strength distribution may therefore be more informative than degree alone for some biological processes.
Degree distribution does not determine the network
Many different graphs can have exactly the same degree distribution. They may nevertheless differ in clustering, communities, degree correlations, path lengths and centrality.
Degree distributions are therefore an important summary, not a complete description of network structure.
Sampling and measurement
Observed degree distributions depend on how contacts are measured. Missing edges can make degrees appear smaller, while aggregating contacts over a long time window can make them appear larger.
Comparisons between biological networks should therefore use compatible definitions and sampling procedures.
Transition to random networks
The degree distribution tells us how many connections nodes have but not exactly how those connections are arranged. The next lesson introduces random-network models that generate network structure probabilistically.