6
$\begingroup$

I want to generate a random connected simple labeled graph with $n$ vertices and $m$ edges, selected uniformly over all connected graphs with such $n$ and $m$. I found this approach. It says: build a random spanning tree using a loop-erased random walk (also called Wilson's algorithm); then add remaining $m-n+1$ edges between random pairs of vertices.

I implemented and investigated this algorithm and have several doubts.

First, what do they denote with random spanning tree in the first part? A random spanning tree of $K_n$? If so, there are $n^{n-2}$ of them, so we may directly restore the tree by its (random) Prüfer sequence. Why do we need the loop-erased random walk here? As far as I experimented it gives the same distribution as the Prüfer-based generation.

Second. If I'm right at the first part and each tree is equiprobable, then different graphs may have different probabilities. For example, if $n=4$ and $m=4$, we have two graphs (I skipped the labels as they are irrelevant here):

o--o    o---o
|  |    |\ /
o--o    o o

The first one can be produced from some spanning tree in 4 distinct ways, while the second one only in 3 ways. If all trees are equiprobable, this obviously introduces bias in graphs.

Where is my mistake? I don't understand Wilson's algo and the distribution on trees is not uniform, or I don't understand the latter part, or this algorithm is in fact incorrect?

Finally, if it is incorrect, how does one generate a random connected graph? The approach of generating a random graph and checking its connectivity fails if $m = \Theta(n)$.

P.S. When saying about randomness, I assume that I have an oracle which returns me a uniform random number in range $[0, n)$ for a reasonable $n$.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Don't trust answers on stackoverflow. Notice that there is no proof, and also no link to a proof. It is just some heuristic that somebody thought about. In defense of stackoverflow, that question actually did not ask for a uniformly random sample – it asked for an arbitrary graph. $\endgroup$
    – Yuval Filmus
    Mar 23, 2017 at 18:24
  • $\begingroup$ @YuvalFilmus That's why I came here. After investigating the approach and almost becoming sure that it's incorrect. $\endgroup$
    – Ivan Smirnov
    Mar 23, 2017 at 18:27
  • $\begingroup$ Interesting question! Looks like you've gotten a reasonable answer to your main question (about that specific algorithmic approach from Stack Overflow). If none of the techniques here are satisfactory, I suggest asking a new question where you ask how to generate a random connected graph, and describe the range of parameters you have in mind (asking about all possible parameters feels a bit broad to me, but if you can narrow things down that might enable better answers). $\endgroup$
    – D.W. ♦
    Mar 23, 2017 at 21:30

1 Answer 1

Reset to default
4
$\begingroup$

Here are two alternative algorithms. There are probably better ones.

Large $m$ When $m \gg \frac{1}{2} n\log n$, it is very likely that a $G(n,m)$ random graph will be connected. Generate $G(n,m)$ graphs until one of them is connected.

Small $m$ When $m$ is small, you can try the following algorithm, which however might be a bit slow (or perhaps very slow). Generate a random graph according to the stackoverflow procedure, calculate the number of $T$ spanning trees it has, and accept with probability $1/T$. You can check that this produces a uniform sample, though the expected running time is $n^{n-2}\binom{(n-1)(n-2)/2}{m-n+1}/G_{n,m}$, where $G_{n,m}$ is the number of connected graphs on $n$ vertices and $m$ edges.

You can speed up the algorithm by sacrificing the accuracy of the sample. Find a number $M$ such that "most" graphs generated by the stackoverflow algorithm have at least $M$ spanning trees, and accept with probability $\min(M/T,1)$. You can estimate $M$ by sampling.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm not aware of any method of counting spanning trees faster than $O(n^\omega)$ using Kirchhoff's theorem, or even estimating it with reasonable error. This is definitely better than just random sampling and checking connectivity, but I doubt that it can be practical for $n$ being around $10^5$. $\endgroup$
    – Ivan Smirnov
    Mar 23, 2017 at 20:47
  • $\begingroup$ There might be an MCMC algorithm (for your original problems), but even such algorithms might be a stretch for graphs that large. $\endgroup$
    – Yuval Filmus
    Mar 23, 2017 at 22:34
  • $\begingroup$ Regarding the expected running time, isn't the expression you gave more like the probability of halting after one step (so the expected time is the inverse). Also, you choose from $n(n-1)/2-(n-1)$ edges since you already have the tree edges, and I think there should be a $|\mathcal{T}|$ in the denominator, where $\mathcal{T}$ is the set of all spanning trees on $n$ vertices. In any case, is there a simple estimate on $G_{n,m}$, I wonder how this expression looks like, since it might be more consuming then the matrix multiplication part. $\endgroup$
    – Ariel
    Mar 23, 2017 at 23:31
  • 1
    $\begingroup$ @Ariel Right, I forgot to take the reciprocal and forgot a factor. I'm not sure there are simple estimates for $G_{n,m}$, but since it's the same as the probability that a random graph is connected, somebody must have done the calculation and has good estimates. It's hard to guess in advance whether this method is ever any better than the first one – perhaps it never is. $\endgroup$
    – Yuval Filmus
    Mar 23, 2017 at 23:39

Your Answer

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

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