Generating random k-regular graphs

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 [1], 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 [2], and is called the pairing model (though it is also sometimes referred to as the configuration model). The algorithm itself is simple:

  1. Begin with a set of n vertices.
  2. Create a new set of nk points, distributing them across n buckets, such that each bucket contains points.
  3. Take each point and pair it randomly with another one, until ½nk pairs are obtained (i.e., a perfect matching).
  4. 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.
  5. 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 [1], 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, asgrows, 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 is a smaller constant, this limitation is of no great concern [1]. Other algorithms that bypass this third limitation have been proposed [3], 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 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:

\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}

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.

References

  1. 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.
  2. 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.
  3. 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.
About these ads

About Marcel Montrey
Marcel Montrey is a graduate student at McGill University, working in Tom Shultz's Laboratory for Natural and Simulated Cognition (LNSC). His primary interests lie in computational models of learning and evolution.

9 Responses to Generating random k-regular graphs

  1. Pingback: Ohtsuki-Nowak transform for replicator dynamics on random graphs « Theory, Evolution, and Games Group

  2. Pingback: Some stats on the first 50 posts « Theory, Evolution, and Games Group

  3. Pingback: Social learning dilemma | Theory, Evolution, and Games Group

  4. Pingback: Evolutionary games in set structured populations | Theory, Evolution, and Games Group

  5. Pingback: Game theoretic analysis of motility in cancer metastasis | Theory, Evolution, and Games Group

  6. Pingback: Evolving useful delusions to promote cooperation | Theory, Evolution, and Games Group

  7. Pingback: Liquidity hoarding and systemic failure in the ecology of banks | Theory, Evolution, and Games Group

  8. Pingback: Approximating spatial structure with the Ohtsuki-Nowak transform | Theory, Evolution, and Games Group

  9. Pingback: Useful delusions, interface theory of perception, and religion. | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,270 other followers