The more usual way of generating graphs and random graphs, is to start from a mechanism of adding nodes (e.g. randomly embedding or connecting, or randomly rewiring edges, etc), and for which we know the resulting degree distribution, such as the Poisson one for Erdos-Renyi random graphs.
- But what about the reverse problem, namely: Given that we know a degree sequence/distribution, could we generate a graph with the prescribed degree distribution?
There exists already a built-in function in Mathematica that seems to cover exactly this, but already for a degree sequence of e.g. $100$ elements (i.e. corresponding to a graph of $100$ nodes), the computation speed scales quite harshly, where it took my machine an hour for such sequence. To test this reverse generation, I simply generate a random graph first, take its degree sequence and try a reverse generation as follows: (small example showcased)
n = 10;
p = 0.3;
g = RandomGraph[BernoulliGraphDistribution[n, p]]
Histogram[VertexDegree[g], {1}, "Probability"]
which produces
and the reverse generation
greverse = RandomGraph[DegreeGraphDistribution[VertexDegree[g]]]
Which is indeed a random graph with the exact same degree distribution, quite neat!
Considering the built-in features of Mathematica and libraries such as IGraph/M, could one perform this reverse generation more efficiently? Because the above solution only works efficiently for very small ($n<100$) graphs (or short degree sequences).
Is it possible that for certain degree distributions generating a corresponding graph becomes a much simpler task computationally? For instance considering extreme cases, such as a Dirac delta (constant degree), a power-law, or a Poisson distribution.
Intuitively, if nothing else works, could one resort to a Monte Carlo sampling scheme, where we sample various random graphs until the sampled degree distribution converges to the targeted one?