3
$\begingroup$

Goal:

I want to generate a r-regular graph with n vertices. rn = 2m.

Current best:

(1) take n vertices; randomly pick a vertex v of degree < r.
(2) S = set of all vertices of degree < r, and not a neighbor of v.
(3) create an edge between v and a random element of S.
(4) repeat.

Question:

Is there a more parallel way to do this?

Clarification:

Suppose I wanted to randomly pick an element in [1...n]. I could do it sequentially like:

take 1 w/ prob 1/n
else take 2 w/ prob 1/n-1
else take 3 w/ prob 1/n-2
...

Or I could do it "one shot" by generating a random element between [1...n].

Similarly, I want to generate a r-regular graph "one shot" rather than an single edge at a time.

Goal:

This is to build mental intuition of what it means to "uniformly pick a r-regular graph."

Thanks!

$\endgroup$
1
  • $\begingroup$ What sorts of random entities are available? Specifically, can you generate a random permutation? Part of my reason for asking is that the special case $r=2$ of your question is pretty close to asking for a random permutation. Another part is that conversely, for general $r$, by thinking of each vertex as having $r$ half-edges already attached, your problem becomes one of pairing up these half-edges, which looks similar to finding a random permutation of the set of half-edges (though you'd have to do something to avoid loops and multiple edges). $\endgroup$ Aug 26, 2011 at 3:43

2 Answers 2

4
$\begingroup$

This question is more difficult that it seems.

Firstly, there is a difference between picking edges of a graph uniformly, and picking a $r$-regular graph uniformly.

Let $G_{r,n}$ be the set of $r$-regular graphs on $n$ nodes. By "uniformly pick a $r$-regular graph", you need to create an algorithm that chooses $G \in G_{r,n}$ with probability $1/|G_{r,n}|$. There are probabilistic methods to do this, perhaps they even lend themselves to parallelization.

See the section on algorithms for generation of random regular graphs here. In particular,B. McKay and N. Wormald, Uniform Generation of Random Regular Graphs of Moderate Degree, Journal of Algorithms, Vol. 11 (1990), pp 52-67

$\endgroup$
5
$\begingroup$

The Wormald method (alluded to in @Daniel's answer) is an application of the "configuration model" introduced by Bollobas (look in his "Random Graphs") It does not work (not in finite time) for graphs of degree greater than around 4. There has been more recent work on this by Kim and Vu (see http://dl.acm.org/citation.cfm?id=780576, there is presumably an arxiv version also), but be forewarned that it is of more theoretical than practical value (it is not clear how large a graph needs to be before the distribution is "close enough" to uniform). Interestingly, while the Wormald algorithm is morally parallel (you generate a configuration at once, then throw it out if it is not a simple graph), the algorithm Kim/Vu analyze (the algorithm is not due to them, and goes back to the ancients, the analysis is theirs) does it one vertex at a time, so "parallelism" is quite expensive, to get back to the OP's original question.

$\endgroup$
1
  • 1
    $\begingroup$ This answer is really good and deserves to be upvoted (but I can't upvote), and since I could only accept one answer; accepted the one with the user with lower reputation score to encourage more MO participation. $\endgroup$ Aug 26, 2011 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.