MCMC to generate/sample directed random graphs with a given degree sequence

Question

Note: Updated below.

If the following steps are repeated for a given directed random graph, will we uniformly sample simple random graphs with a conserved degree sequence, or is there some bias introduced?

 Randomly choose two edges u-v and x-y in the existing graph
 If u!=x and v!=y and u!=y and v!=x:
    If u-y and x-v do not exist:
        add u-y and x-v
        delete u-v and x-y

This question was also asked over at SO, and suggested in a networkx ticket.

Update: Over at the networkx ticket, there is some discussion that Theorem 7 of the paper P Erdos et al., "A simple Havel–Hakimi type algorithm to realize graphical degree sequences of directed graphs", Combinatorics 2010 implies that we need 3-edge swaps to sample the whole space. Is this true?

Update: This was answered at the Mathematics Stack Exchange site. It seems that we need 3-edge swaps also.

Answer 1

1

You need to remove the original u-v and x-y edges or the degree sequence won't be preserved. I think you probably just forgot to say that in the text. Otherwise your limit case will be missing at most two edges and that would be a bit of a bias for all the samples after that point.

I'm not sure about the answer to your underlying question. It sounds reasonable at first glance. The paired edge flips reminds me of some of the local TSP searches.

answered Feb 09 '11 at 09:54

John Henderson
16●1

@John, yes, you are right. I forgot to mention it. I have edited the problem to reflect deleting the selected edges. Just to make sure, the bias you are talking about is if I were to not delete the edges? Or do you think there is a bias in the algorithm after editing? If so, could you please explain which edges give the bias? Thanks!

(Feb 09 '11 at 10:50) probreasoning

Answer 2

0

I think there is a bug in this. Take a graph with three nodes and one edge. This edge, then, can never be removed or flipped. Adding one extra node to the graph seems to fix this, but this sort of behavior might bias the algorithm in later steps.

answered Feb 09 '11 at 11:00

Alexandre Passos ♦
18967●44●214●334

So if there is only one edge, then I do not think there exists any other simple graph with the same degree sequence, and no MCMC steps should be accepted. Adding extra nodes do not impact this. If we were to add one extra edge to the graph, then the edge targets could be swapped, giving another graph. I do not see the limiting case wherein this algorithm will not reach a portion of the valid space. If I am missing something, please let me know. But this is exactly what I am looking for, are there any holes in the algorithm?

(Feb 09 '11 at 11:06) probreasoning

@Alexandre, do you think 3-edge swaps mentioned in the Peter Erdos paper have something to do with the limit case you mentioned?

(Feb 15 '11 at 21:20) probreasoning

MCMC to generate/sample directed random graphs with a given degree sequence

Subscription:

Related questions