Generating random k-regular graphs
March 29, 2012 7 Comments
In a previous post, I gave a brief overview of the role of spatial structure in evolutionary game theory. Along with an explanation of what it means for an agent-based simulation to have such structure, several notable types of networks were introduced, including small-world and scale-free networks, as well as random graphs. At the time, random k-regular graphs were singled out as being of particular practical interest to modelers. Consequently, I would now like to touch on some of the practical considerations involved in generating such graphs. Recall that, in our particular case, a graph’s vertices may be thought to represent agents, whereas the graph’s edges characterize the social or reproductive connections between them.
A random k-regular graph is a set of n vertices randomly connected with k edges incident on each vertex. This specification is rather straightforward, as is the naive approach to generating such a graph: In theory, we must simply consider all possible graphs with n vertices and k degree, and then select one of them at random. Unfortunately, the space of possible k-regular graphs is so large that this approach could never work in practice. As years of research have now shown , generating a random k-regular graph by other means is also no trivial task. A variety of algorithms have emerged as a result.
The most popular method to date was first proposed by Bollobás , and is called the pairing model (though it is also sometimes referred to as the configuration model). The algorithm itself is simple:
- Begin with a set of n vertices.
- Create a new set of nk points, distributing them across n buckets, such that each bucket contains k points.
- Take each point and pair it randomly with another one, until ½nk pairs are obtained (i.e., a perfect matching).
- Collapse the points, so that each bucket (and thus the points it contains) maps onto a single vertex of the original graph. Retain all edges between points as the edges of the corresponding vertices.
- Check if the resulting graph is simple. That is to say, make sure that none of the vertices have loops (i.e., self-connections) or multiple edges (i.e., more than one connection to the same vertex). If the graph is not simple, restart.
There are several limitations to this algorithm. The first of these is that nk must be an even number, a requirement that is easily satisfied. The second and more interesting limitation is the need to retain only simple graphs. This is because, if we allow loops or multiple edges, graphs are no longer generated uniformly at random , and the randomization process becomes biased . Luckily, in evolutionary game theory, we are typically quite happy with this constraint and, in fact, often deliberately exclude the possibility of self-connections or parallel connections to the same agent. The final drawback is brought about by the occasional need for a restart. Specifically, as k grows, the probability of obtaining a non-simple graph rises as well, eventually making applying this algorithm impractical. Luckily, it has been shown that so long as k is a smaller constant, this limitation is of no great concern . Other algorithms that bypass this third limitation have been proposed , though they come with a notable drawback: Rather than generating a uniform random regular graph, they typically only generate an asymptotically uniform one. In light of this, there are good reasons for preferring the pairing model, so long as exceptionally large and highly-connected graph structures are not required.
Though the pairing model algorithm is easy to implement, a brief search of the Matlab Central File Exchange reveals that a ready-made implementation is already available for Matlab users. Using it is as simple as loading createRandRegGraph.m, then calling the createRandRegGraph function, using n and k as parameters, respectively. The output of this function is an adjacency matrix, using a sparse matrix representation, though this is readily converted to a standard adjacency matrix by applying the full function. For example, entering full(createRandRegGraph(4, 2)); into the command window yields an adjacency matrix that describes a 4 vertex graph of degree 2, such as this one:
Using a random k-regular graph as the basis for your simulation’s spatial structure, therefore, is as simple as incorporating the output of this function into your work.
- N. Wormald, Models of random regular graphs. Surveys in combinatorics, 1999 (Canterbury), 239-298, London Math. Soc. Lecture Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999.
- B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 (1980), no. 4, 311-316.
- Kim, J. H., & Vu, V. H. (2003). Generating random regular graphs. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, STOC ’03 (pp. 213–222). New York, NY, USA: ACM.