7 - Configuration Model

Summary

In this chapter, we investigate graphs with fixed degrees. Ideally, we would like to investigate uniform random graphs having a prescribed degree sequence, i.e, a degree sequence which is given to us beforehand. An example of such a situation could arise from a real-world network of which we know the degree sequence, and we would be interested in generating a random, or even uniform, graph with precisely the same degrees.

Such a random graph can be created by uniformly matching half-edges, at the expense of possibly creating self-loops and multiple edges, and the result is called the configuration model. The main results in this chapter describe the degree structure in such random graphs, as well as the probability for the random graph to be simple. We also draw connections between the configuration model and the generalized random graphs defined in Chapter 6.

Motivation for the Configuration Model

The configuration model is a model in which the degrees of vertices are fixed beforehand. Such a model is more flexible than the generalized random graph. For example, the generalized random graph always has a positive proportion of vertices of degree 0, 1, 2, etc. (see Exercises 6.15–6.16). In some real-world networks, however, it is natural to investigate graphs where every vertex has at least one or two neighbors. We start by discussing a few examples where random graphs with prescribed degrees appear naturally:

Example 7.1 (Facebook wall posts) In Facebook wall posts, the vertices of the network are Facebook users, and each directed edge represents one post, linking the user writing the post to the user on whose wall the post is written. This gives rise to a (directed) network of a small subset of posts to the walls of other users on Facebook. Since users may write multiple posts on a wall, the network allows multiple edges between pairs of vertices. Since users may write on their own wall, the network contains loops. The degree distribution in log-log scale is displayed in Figure 7.1, and we see that the degree distribution resembles a power law. We see that the degrees are, by definition, all at least 1. Thus, this data set is poorly modeled by the generalized random graph, which always has many vertices of degree 0.