Finding loops and double edges ASAP in configuration model random graph

Question

A common approach (at least in theory) to generating a random $n$ vertex graph uniformly subject to having a given (feasible) degree sequence $(d_i)_{i = 1}^n$ is to use the configuration model, i.e. just attach $d_i$ half-edges to vertex $i$ and then pair up all the half-edges uniformly at random.

Loops or double edges can occur- if they do, repeat the procedure until you obtain a simple graph.

(The probability of obtaining a simple graph is usually small in practice so the expected number of restarts is large, and this algorithm isn't used much in practice for $n$ large.)

Now, the pairings in the configuration model can performed sequentially:

1. Select a half-edge arbitrarily. (SELECT)
2. Sample a remaining half-edge uniformly at random. (SAMPLE)
3. Pair up the SELECT'd half-edge and SAMPLE'd half-edge (to form or 'reveal' an edge).
4. If there are half-edges remaining then return to 1.

Of course, in practice, you'd also restart the whole procedure when the first loop or double edge is discovered.

You want to find any loop or double edge as quickly as possible.

What is the best (adapted) strategy for SELECT'ing half-edges in step 1?

Easy guess: SELECT any half-edge from a vertex with maximal (conditional) probability of being incident to a double edge or loop. I.e. letting $H_i$ be the number of half-edges remaining at vertex $i$, then we choose the vertex that maximises $B_i = (H_i - 1) + \sum_{j\sim i} H_j$, where the sum is over vertices $j$ that already have an edge revealed to vertex $i$. (B_i is the number of remaining half-edges which, if SAMPLE'd, would lead to a loop/double edge). So you'd begin by SELECT'ing a half-edge from a vertex of maximal degree.

Is this strategy known to minimise the expected number of pairings needed to find the first loop/double edge (assuming there is one)?

N.b. I'm specifically asking about the best way to select the half-edge in step 1 of the algorithm given above, (just for curiosity, not because I think it will yield a practical improvement over other approaches to simulating random graphs)

Small update:

1. I implemented this algorithm (c++), and it does offer a marked improvement over naively pairing up half-edges from vertices chosen in a lexicographic way. The speed up is not as much as I'd hoped though (less than a factor of 1/2 for the degree sequences I looked at).
2. Computing the "badness" scores $B_i$ above isn't too computationally intensive. In fact the scores can be updated on the fly and this seems pretty quick.
3. For anyone generally interested in efficiently sampling graphs Igor's link below or Blitzstein-Diaconis survey some methods (probably better).

Answer 1

Check out this work of Kim and Vu and references therein. WARNING: their algorithm is of very questionable use in practice, since the distribution is only asymptotically uniform, and since in the limit the Sun turns nova, this is not useful without bounds, which are sadly lacking.