In network science, the Configuration Model is a family of random graph models designed to generate networks from a given degree sequence. Unlike simpler models such as the Erdős–Rényi model, Configuration Models preserve the degree of each vertex as a pre-defined property. This flexibility allows the modeler to construct networks with arbitrary degree distributions, making it widely used as a reference model for real-life networks, particularly in social, biological, and technological domains. The concept of "Configuration Model" was first introduced by Béla Bollobás, who laid the foundation for its application in graph theory and network science.Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4), 311-316.
Rationale for the model The key advantage of the Configuration Model lies in its ability to decouple the degree sequence from specific edge generation processes. This makes it suitable for analyzing networks with heterogeneous degree distributions, such as scale-free networks, which exhibit heavy-tailed degree distributions. By preserving these structural properties, Configuration Models provide a null hypothesis for understanding the role of degree distributions in shaping network properties.
Configuration Models can be specified for different types of graphs:
Simple graphs: Graphs without self-loops or multi-edges.
Multi-edge graphs: Graphs allowing multiple edges between the same pair of nodes.
Loopy graphs: Graphs that include self-loops (edges connecting a node to itself).
Directed graphs: Models with specified in-degrees and out-degrees for each node.
Undirected graphs: Models that consider the total degree of each node.
Configuration Models The family of Configuration Models can be categorized into two main groups:
Microcanonical Configuration Models: Fix the degree sequence exactly.
Canonical Configuration Models: Fix the degree sequence in expectation.
Micro-Canonical Configuration Model
The Micro-Canonical Configuration Model is the most common variation of the configuration model. It exactly preserves the degree sequence of a given graph by assigning stubs (half-edges) to nodes based on their degrees and then randomly pairing the stubs to form edges.
The preservation of the degree sequence is exact in the sense that all realizations of the model result in graphs with the same predefined degree distribution. This variation is referred to as micro-canonical because it defines a uniform probability space where all possible graphs consistent with the given degree sequence are equally likely to be sampled. This approach ensures that the degree sequence is strictly maintained.
The model can be formalized as stub-labelled model, where stubs are explicitly labelled and paired; alternatively, it can be formalised as a vertex-labelled models, where edges between vertices are indistinguishable.Fosdick, Bailey K., et al. "Configuring random graph models with fixed degree sequences." Siam Review 60.2 (2018): 315-355.
Canonical Configuration Models
Canonical Configuration Models relax the exact degree sequence constraint and preserve it only in expectation. These models define probability distributions over the edges of the network. Canonical configuration models are often referred to as soft configuration models.
Chung-Lu Configuration Model
The Chung-Lu Configuration Model is a canonical configuration model variant for simple graphs (i.e., without multi-edges). It assumes that edges between nodes are independent from each other, differently from the micro-canonical model. The probability of an edge between nodes and is proportional to the product of their degrees and, in the case of a loopy undirected graph, is given by:
where and are the degrees of nodes and , and is the total number of edges in the graph. In this formulation, the expected degree sequence matches the input degrees, but the actual degree sequence in any realization may vary slightly due to the probabilistic nature of edge formation.
Application: Modularity Calculation
The Chung-Lu configuration model, provides the benchmark in the calculation of network modularity. Modularity measures how well a network is divided into modules or communities, comparing the observed structure against a null model: the configuration model. The modularity is computed as:
where: is the adjacency matrix of the observed network, with if there is an edge between and , and otherwise. represents the expected probability of an edge between nodes and under the configuration model. is the Kronecker delta, equal to 1 if nodes and are in the same module and 0 otherwise.
This equation compares the observed network to the configuration model, where edges are distributed based solely on the degree sequence. Modularity scores provide insights into the quality of community structures in the network, with higher scores indicating stronger modularity.
For further details, refer to the page on modularity.
Norros-Reittu Configuration Model
The Norros-Reittu Configuration ModelNorros, I., & Reittu, H. (2006). On a conditionally Poissonian graph process. Advances in Applied Probability, 38(1), 59-75. extends the Chung-Lu configuration model by allowing for multi-edges between nodes. In this model, the number of edges between nodes and follows a Poisson distribution, given by:
where is the expected number of edges between nodes and , defined as:
Here: and are the degrees of nodes and , respectively. is the total number of edges in the graph. As for Chung-Lu configuration model, nodes pairs are assumed to be independent from each other.
Connection to Degree-Corrected Stochastic Block Model The Norros-Reittu Configuration Model is particularly important as it provides the degree correction for the Degree-Corrected Stochastic Block Model (DC-SBM).Karrer, Brian, and Mark EJ Newman. "Stochastic blockmodels and community structure in networks." Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 83.1 (2011): 016107. By incorporating the degree sequence into the edge probability, this model allows the DC-SBM to distinguish between structural patterns in communities and variations driven by node degrees. This degree correction ensures that the observed degree heterogeneity in networks does not bias the identification of community structures.
Casiraghi-Nanumyan Hypergeometric Configuration Model
The Casiraghi-Nanumyan Hypergeometric Configuration ModelCasiraghi, Giona, and Vahan Nanumyan. "Configuration models as an urn problem." Scientific reports 11.1 (2021): 13416. extends canonical configuration models by accounting for dependencies between edges. Unlike models assuming independent edge generation, this model uses a multivariate hypergeometric distribution to represent the probability of an entire graph configuration. This approach preserves the degree sequence while modeling competition for resources. The probability of observing a specific graph with adjacency matrix is given by:
where is the number of edges between nodes and , represents the propensity for interaction between nodes and based on their degrees, is the total number of edges in the graph and .
This model captures resource competition by enforcing that the sum of interactions across all node pairs is fixed. Forming an edge between two nodes reduces the availability of resources for other connections, reflecting realistic constraints in systems like social or ecological networks. The model naturally generates multi-edges for any node pair and where .
Configuration Model from Maximum Entropy Principles Starting from the maximum entropy principle, one can generate another canonical configuration model, referred to as the soft configuration model. This model belongs to the family of exponential random graph models (ERGMs) and generates random graphs by constraining the expected degree sequence while maximizing the entropy of the graph model. The probability of a graph is given by:
where are Lagrange multipliers ensuring the expected degree of node matches the target degree, is the degree of node in the graph .
Generating from the Micro-Canonical Configuration Model The following algorithm describes the generation of the model: Take a degree sequence, i. e. assign a degree to each vertex. The degrees of the vertices are represented as half-links or stubs. The sum of stubs must be even in order to be able to construct a graph (). The degree sequence can be drawn from a theoretical distribution or it can represent a real network (determined from the adjacency matrix of the network). Choose two stubs uniformly at random and connect them to form an edge. Choose another pair from the remaining stubs and connect them. Continue until you run out of stubs. The result is a network with the pre-defined degree sequence. The realization of the network changes with the order in which the stubs are chosen, they might include cycles (b), self-loops (c) or multi-links (d) (Figure 1).
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 essential property in calculating other features of the generated networks. The network generation process does not exclude the development of 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.
The expected total number of multi-links in a configuration model network would be:
where is the n-th moment of the degree distribution. Therefore, the average number of self-loops and multi-links is a constant for some large networks, and the density of self-loops and multi-links, meaning the number per node, goes to zero as as long as is constant and finite. For some power-law degree distributions where the second moment diverges, density of multi-links may not vanish or may do so more slowly than .
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 is , so the number of realizations of a degree sequence is . 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 , the variation in probabilities of different realization will be small but present.
Properties
Edge probability A stub of node can be connected to other stubs (there are stubs altogether, and we have to exclude the one we are currently observing). The vertex has stubs to which node can be connected with the same probability (because of the uniform distribution). The probability of a stub of node being connected to one of these stubs is . Since node has stubs, the probability of being connected to is ( for sufficiently large ). Note that this formula can only be viewed as a probability if , and more precisely it describes the expected number of edges between nodes and . Note that this formula does not apply to the case of self-edges.