Network Degree Distribution

A network (or graph) consists of nodes (vertices) connected by edges. Networks appear everywhere in complex systems: social connections, neural circuits, power grids, the internet.

Representation

We represent networks as adjacency lists — a Python dict mapping each node to a set of its neighbours:

adj = {
    0: {1, 2, 3},
    1: {0, 2},
    2: {0, 1},
    3: {0},
}

Degree

The degree $k_i$ of node $i$ is the number of its neighbours:

$k_i = |\text{neighbours}(i)|$

The mean degree of a network with $N$ nodes and $E$ edges is:

$\langle k \rangle = \frac{2E}{N}$

(each edge contributes 2 to the total degree sum).

Degree Distribution

The degree distribution $P(k)$ gives the fraction of nodes with exactly $k$ neighbours. For:

• Random (Erdős–Rényi) graphs: $P(k)$ is Poisson-distributed
• Scale-free (Barabási–Albert) graphs: $P(k) \propto k^{-\gamma}$ (power law)

Clustering Coefficient

The local clustering coefficient $C_i$ measures how tightly connected node $i$'s neighbours are:

$C_i = \frac{\text{edges among neighbours of } i}{\binom{k_i}{2}} = \frac{\text{edges among neighbours}}{k_i(k_i-1)/2}$

$C_i = 1$ means all neighbours are connected to each other; $C_i = 0$ means none are.

Your Task

Implement:

• node_degree(adj, node) — degree of a single node
• mean_degree(adj) — average degree over all nodes
• degree_distribution(adj) — dict {k: fraction} of nodes with that degree
• clustering_coefficient(adj, node) — local clustering coefficient (return 0 if degree < 2)