Configuration model

The algorithm described above matches any stubs with the same probability. The uniform distribution of the matching is an important property in terms of calculating other features of the generated networks. The network generation process does not exclude the event of generating a self-loop or a multi-link. If we designed the process where self-loops and multi-edges are not allowed, the matching of the stubs would not follow a uniform distribution. However, the average number of self-loops and multi-edges is a constant for large networks, so the density of self-loops and multi-links goes to zero as ${\displaystyle N\rightarrow \infty }$[2] (see the cited book for details).

A further consequence of self-loops and multi-edges is that not all possible networks are generated with the same probability. In general, all possible realizations can be generated by permuting the stubs of all vertices in every possible way. The number of permutation of the stubs of node ${\displaystyle i}$ is ${\displaystyle k_{i}!}$, so the number of realizations of a degree sequence is ${\displaystyle N\{k_{i}\}=\Pi _{i}k_{i}!}$. This would mean that each realization occurs with the same probability. However, self-loops and multi-edges can change the number of realizations, since permuting self-edges can result an unchanged realization. Given that the number of self-loops and multi-links vanishes as ${\displaystyle N\rightarrow \infty }$, the variation in probabilities of different realization will be small but present.[2]

A stub of node ${\displaystyle i}$ can be connected to ${\displaystyle 2m-1}$ other stubs (there are ${\displaystyle 2m}$ stubs altogether, and we have to exclude the one we are currently observing). The vertex ${\displaystyle j}$ has ${\displaystyle k_{j}}$ stubs to which node ${\displaystyle i}$ can be connected with the same probability (because of the uniform distribution). The probability of a stub of node ${\displaystyle i}$ being connected to one of these ${\displaystyle k_{j}}$ stubs is ${\displaystyle {\frac {k_{j}}{2m-1}}}$. Since node ${\displaystyle i}$ has ${\displaystyle k_{i}}$ stubs, the probability of ${\displaystyle i}$ being connected to ${\displaystyle j}$ is ${\displaystyle {\frac {k_{i}k_{j}}{2m-1}}}$ (${\displaystyle {\frac {k_{i}k_{j}}{2m}}}$ for sufficiently large ${\displaystyle m}$). The probability of self-edges cannot be described by this formula, but as the density of self-edges goes to zero as ${\displaystyle N\rightarrow \infty }$, it usually gives a good estimate.[2]

Given a configuration model with a degree distribution ${\displaystyle p_{k}}$, the probability of a randomly chosen node ${\displaystyle i}$ having degree ${\displaystyle k}$ is ${\displaystyle p_{k}}$. But if we took one of the vertices to which we can arrive following one of edges of i, the probability of having degree k is ${\displaystyle {\frac {k}{2m}}*np_{k}={\frac {kp_{k}}{<k>}}}$ . (The probability of reaching a node with degree k is ${\displaystyle {\frac {k}{2m}}}$, and there are ${\displaystyle np_{k}}$ such nodes.) This fraction depends on ${\displaystyle kp_{k}}$ as opposed to the degree of the typical node with ${\displaystyle p_{k}}$. Thus, a neighbor of a typical node is expected to have higher degree than the typical node itself. This feature of the configuration model describes well the phenomenon of "my friends having more friends than I do".

The global clustering coefficient ${\displaystyle C_{g}}$ (the average probability that the neighbors of a node are connected) is computed as follows:

${\displaystyle C_{g}=\sum _{k_{i},k_{j}=0}^{\infty }q_{k}(i)q_{k}(j)*{\frac {k_{i}k_{j}}{2m}}}$,

where ${\displaystyle q_{k}(i),q_{k}(j)}$ denotes the probabilistic distributions of vertices ${\displaystyle i}$ and ${\displaystyle j}$ having ${\displaystyle k_{i},k_{j}}$ edges, respectively.

${\displaystyle C_{g}={\frac {1}{2m}}\left[\sum _{k=0}^{\infty }kq_{k}\right]^{2}}$

After transforming the equation above, we get approximately

${\displaystyle \thickapprox {\frac {1}{2m}}*constant\thickapprox {\frac {1}{N}}*constant}$, where ${\displaystyle N}$ is the number of vertices, and the size of the constant depends on ${\displaystyle p_{k}}$.[2] Thus, the global clustering coefficient ${\displaystyle C_{g}}$becomes small at large n limit.

In the configuration model, a giant component (GC) exists if

${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0,}$

where ${\displaystyle \langle k\rangle }$ and ${\displaystyle \langle k^{2}\rangle }$ are the first and second moments of the degree distribution. That means that, the critical threshold solely depends on quantities which are uniquely determined by the degree distribution ${\displaystyle p_{k}}$.

Configuration model generates locally tree-like networks, meaning that any local neighborhood in such a network takes the form of a tree. More precisely, if you start at any node in the network and form the set of all nodes at distance ${\displaystyle d}$ or less from that starting node, the set will, with probability tending to 1 as n → ∞, take the form of a tree.[3] In tree-like structures, the number of second neighbors averaged over the whole network, ${\displaystyle c_{2}}$, is: ${\displaystyle c_{2}=\langle k^{2}\rangle -\langle k\rangle .}$

Then, in general, the average number at distance ${\displaystyle d}$ can be written as:

${\displaystyle c_{d}=({\frac {c_{2}}{c_{1}}})^{d-1}c_{1}.}$

Which implies that if the ratio of ${\displaystyle {\frac {c_{2}}{c_{1}}}}$ is larger than one, then the network can have a giant component. This is famous as the Molloy-Reed criterion.[4] The intuition behind this criterion is that if the giant component exists, then the average degree of a randomly chosen vertex ${\displaystyle i}$ in a connected component should be at least 2. Molloy-Reed criterion can also be expressed as: ${\displaystyle \sum _{i}k_{i}(k_{i}-2)>0,}$ which implies that, although the size of the GC may depend on ${\displaystyle p_{0}}$and ${\displaystyle p_{2}}$, the number of nodes of degree 0 and 2 have no contribution in the existence of the giant component.[3]

Configuration model can assume any degree distribution and shows the small-world effect, since to leading order the diameter of the configuration model is just ${\displaystyle d={\frac {ln(N)}{ln(c_{2}/c_{1})}}}$.[5]

As total number of vertices ${\displaystyle N}$ tends to infinity, the probability to find two giant components is vanishing. This means that in the sparse regime, the model consist of one giant component (if any) and multiple connected components of finite size. The sizes of the connected components are characterized by their size distribution ${\displaystyle w_{n}}$- the probability that a randomly sampled vertex belongs to a connected component of size ${\displaystyle n.}$ There is a correspondence between the degree distribution ${\displaystyle p_{k}}$ and the size distribution ${\displaystyle w_{n}.}$ When total number of vertices tends to infinity, ${\displaystyle N\rightarrow \infty }$, the following relation takes place:[6]

${\displaystyle w_{n}={\begin{cases}{\frac {\langle k\rangle }{n-1}}u_{1}^{*n}(n-2),&n>1,\\p_{0}&n=1,\end{cases}}}$

where ${\displaystyle u_{1}(k):={\frac {k+1}{\langle k\rangle }}p_{k+1},}$ and ${\displaystyle u_{1}^{*n}}$ denotes the ${\displaystyle n}$-fold convolution power. Moreover, explicit asymptotes for ${\displaystyle w_{n}}$ are known when ${\displaystyle n\gg 1}$and ${\displaystyle |\langle k^{2}\rangle -2\langle k\rangle |}$is close to zero.[6] The analytical expressions for these asymptotes depend on finiteness of the moments of ${\displaystyle p_{k},}$ the degree distribution tail exponent ${\displaystyle \beta }$(when ${\displaystyle p_{k}}$features a heavy tail), and the sign of Molloy-Reed criterium. The following table summarises these relationships (the constants are provided in[6]).

Moments of ${\displaystyle p_{k}}$	Tail of ${\displaystyle p_{k}}$	${\displaystyle {\text{sign}}(\langle k^{2}\rangle -2\langle k\rangle )}$	${\displaystyle w_{n},\;n\gg 1,\;\alpha =\beta -2}$
${\displaystyle \langle k^{3}\rangle <\infty }$	light tail	-1 or 1	${\displaystyle C_{1}e^{-C_{2}n}n^{-3/2}}$
		0	${\displaystyle C_{1}n^{-3/2}}$
	heavy tail, ${\displaystyle \beta >4}$	-1	${\displaystyle C_{3}n^{-\alpha -1}}$
		0	${\displaystyle C_{1}n^{-3/2}}$
		1	${\displaystyle C_{1}e^{-C_{2}n}n^{-3/2}}$
${\displaystyle \langle k^{3}\rangle =\infty ,}$ ${\displaystyle \langle k^{2}\rangle <\infty ,}$	heavy tail, ${\displaystyle \beta =4}$	-1	${\displaystyle C_{3}n^{-\alpha -1}}$
		0	${\displaystyle C_{1}'{\frac {n^{-3/2}}{\sqrt {\log n}}}}$
		1	${\displaystyle C_{1}'{\frac {n^{-3/2}}{\sqrt {\log n}}}e^{-C_{2}'{\frac {n}{\log n}}}}$
	heavy tail, ${\displaystyle 3<\beta <4}$	-1	${\displaystyle C_{3}n^{-\alpha -1}}$
		0	${\displaystyle C_{4}n^{-{\frac {1}{\alpha }}-1}}$
		1	${\displaystyle C_{5}e^{-C_{6}n}n^{-3/2}}$
${\displaystyle \langle k^{2}\rangle =\infty ,}$ ${\displaystyle \langle k\rangle <\infty ,}$	heavy tail, ${\displaystyle \beta =3}$	1	${\displaystyle C_{7}e^{-C_{8}-C_{9}n^{\frac {2}{\pi }}}n^{{\frac {1}{\pi }}-2}}$
	heavy tail, ${\displaystyle 2<\beta <3}$	1	${\displaystyle C_{10}e^{-C_{11}n}n^{-3/2}}$

Three general properties of complex networks are heterogeneous degree distribution, short average path length and high clustering.[1][7][8] Having the opportunity to define any arbitrary degree sequence, the first condition can be satisfied by design, but as shown above, the global clustering coefficient is an inverse function of the network size, so for large configuration networks, clustering tends to be small. This feature of the baseline model contradicts the known properties of empirical networks, but extensions of the model can solve this issue (see [9]).

The configuration model is applied as benchmark in the calculation of network modularity. Modularity measures the degree of division of the network into modules. It is computed as follows:

${\displaystyle Q={\frac {1}{2L}}\sum _{i\neq j}{\Bigl (}A_{ij}-{\frac {k_{i}k_{j}}{2L}}{\Bigr )}\delta (C_{i},C_{j})}$[10]

in which the adjacency matrix of the network is compared to the probability of having an edge between node ${\displaystyle i}$ and ${\displaystyle j}$ (depending on their degrees) in the configuration model (see the page modularity for details).