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.]
