5
$\begingroup$

In graph data mining it is often useful to generate random (simple) graphs with a given degree sequence (e.g. in searching for network motifs), and ideally these would be uniformly at random.

[For this question, we'll consider the undirected case (the directed case can also be treated similarly, but it's a bit more messy).]

We could use the configuration model to generate these graphs (each node is given stubs corresponding to its degree, and these stubs are connected uniformly at random; repeat until a simple graph is obtained). But, unfortunately, often this results in too many restarts, and is impractical. This is worse for larger graphs, or graphs with unfavourable degree distributions. [When it does work, however, the configuration model is surprisingly quick.]

In cases when the configuration model is impractical, a switching method is often used, where two edges {a,b} and {c,d} are replaced by {a,d} and {b,c}, provided no clashes arise (loops or parallel edges). If we perform this operation a zillion times, we'll get something empirically fairly close to the uniform distribution (it is not actually uniform, but is plenty good enough for most real-world studies, where other errors dominate).

Let me propose another scheme: We select some induced subgraph H, and use the configuration model on H alone. Repeat this a zillion times.

Question: Has this scheme, or a similar scheme, been considered previously? If so, would it result in a distribution that is "empirically close" to uniform? Could it possibly be more efficient than the "switching pairs of edges" method?

When I say, "more efficient" I don't mean O(...) efficiency. E.g. simply being twice as fast would be great.

[NB. In the above, I'm (for the time being) putting aside the process of choosing the subgraph H, which is a problem in itself.]

$\endgroup$
1

1 Answer 1

3
$\begingroup$

There is the algorithm of Blitzstein and Diaconis -- they claim very good practical performance.

$\endgroup$
2
  • $\begingroup$ Thanks for that! It has quite a lot of detail about a range of methods (including their own). Also, unlike the MCMC method, their method could readily be used in parallel computation (e.g. if you want to generate 1000 random graphs). $\endgroup$ Jan 23, 2012 at 23:54
  • $\begingroup$ Another interesting solution (with implementation), published in 2019, is discussed here: mathoverflow.net/questions/365865/… $\endgroup$ Jan 30, 2021 at 2:34

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.