Configuration model
In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions. Rationale for the model. In the configuration model, the degree of each vertex is pre-defined, rather than having a probability distribution from which the given degree is chosen. As opposed to the Erdős–Rényi model, the degree sequence of the configuration model is not restricted to have a Poisson distribution, the model allows the user to  give the network any desired degree distribution. Algorithm. The following algorithm describes the generation of the model: Self-loops, multi-edges and implications. 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 some large networks, so the density of self-loops and multi-links goes to zero as formula_4 (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 formula_5 is formula_6, so the number of realizations of a degree sequence is formula_7. 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 formula_4, the variation in probabilities of different realization will be small but present. Properties. Edge probability. A stub of node formula_5 can be connected to formula_10 other stubs (there are formula_11 stubs altogether, and we have to exclude the one we are currently observing). The vertex formula_12 has formula_13 stubs to which node formula_5 can be connected with the  same probability (because of the uniform distribution). The probability of a stub of node formula_5 being connected to one of these formula_13 stubs is formula_17. Since node formula_5 has formula_19 stubs, the probability of formula_5 being connected to formula_12 is formula_22 (formula_23 for sufficiently large formula_24). Note that this formula can only be viewed as a probability if formula_25, and more precisely it describes the expected number of edges between nodes formula_5 and formula_12. Note that this formula does not apply to the case of self-edges. Given a configuration model with a degree distribution formula_28, the probability of a  randomly chosen node formula_29 having degree formula_30 is formula_28. 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 formula_32 . (The probability of reaching a node with degree k is formula_33, and there are formula_34 such nodes.) This fraction depends on formula_35 as opposed to the degree of the typical node with formula_28. 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". Clustering coefficient. The clustering coefficient formula_37 (the average probability that the neighbors of a node are connected) is computed approximately as follows: where formula_39 denotes the probability that a random edge reaches a degree-formula_40 vertex, and the factors of the form "formula_41" rather than "formula_1" appear because one stub has been accounted for by the fact that these are neighbors of a common vertex. Evaluating the above results in Using formula_44 and formula_45, with formula_46 denoting the degree distribution, formula_47 denoting the average degree, and formula_48 denoting the number of vertices, the above  becomes with formula_50 denoting the second moment of the degree distribution. Assuming that formula_50 and formula_52 are constant, the above behaves as where the constant depends on formula_54. Thus, the clustering coefficient formula_55 becomes small in the formula_56 limit. Giant component. In the configuration model, a giant component (GC) exists if where formula_58 and formula_59 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 formula_46. 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 formula_61 or less from that starting node, the set will, with probability tending to 1 as n → ∞, take the form of a tree. In tree-like structures, the number of second neighbors averaged over the whole network, formula_62, is: formula_63 Then, in general, the average number at distance formula_61 can be written as: Which implies that if the ratio of formula_66 is larger than one, then the network can have a giant  component. This is famous as the Molloy-Reed criterion. The intuition behind this criterion is that if the giant component (GC) exists, then the average degree of a randomly chosen vertex formula_5 in a connected component should be at least 2. Molloy-Reed criterion can also be expressed as: formula_68 which implies that, although the size of the GC may depend on formula_69and formula_70, the number of nodes of degree 0 and 2 have no contribution in the existence of the giant component. Diameter. 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 formula_71. Components of finite size. As total number of vertices formula_72 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 formula_73- the probability that a randomly sampled vertex belongs to a connected component of size formula_74 There is a correspondence between the degree distribution formula_46 and the size distribution formula_76 When total number  of vertices tends to infinity, formula_4, the following relation takes place: where formula_79 and formula_80 denotes the formula_81-fold convolution power. Moreover, explicit asymptotes for formula_73 are known when formula_83and formula_84is close to zero. The analytical expressions for these asymptotes depend on finiteness of the moments of formula_85 the degree distribution tail exponent formula_86 (when formula_46features a heavy tail), and the sign of Molloy–Reed criterium. The following table summarises these relationships (the constants are provided in). Modelling. Comparison to real-world networks. Three general properties of complex networks are heterogeneous degree distribution, short average path length and high clustering . 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 ). Application: modularity calculation. 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: formula_88 in  which the adjacency matrix of the network is compared to the probability of having an edge between node formula_5 and formula_90 (depending on their degrees) in the configuration model (see the page modularity for details). Directed configuration model. In the DCM (directed configuration model), each node is given a number of half-edges called tails and heads. Then tails and heads are matched uniformly at random to form directed edges. The size of the giant component, the typical distance, and the diameter of DCM have been studied mathematically. There also has been extensive research on random walks on DCM. Some  real-world complex networks have been modelled by DCM, such as neural networks, finance and social networks.