Reverse graph generation

Question

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?

Answer 1

Using IGraph/M, to check if a degree sequence is graphical (i.e. if there's a simple graph with that degree sequence):

IGGraphicalQ[degseq]

To generate a single graph with a given degree sequence:

IGRealizeDegreeSequence[degseq]

This uses the Havel–Hakimi algorithm. See also my blog post on the connectivity of the resulting graph.

To "randomize" the edges of a graph while preserving its degree sequence:

IGRewire[graph, n]

If n is large, then this will effectively sample graphs having the same degree sequence uniformly. However, there is no clear rule on what n is large enough.

The IGDegreeSequenceGame function implements multiple methods to generate random graphs with a given degree sequence:

IGDegreeSequenceGame[degseq]

Be sure to read the documentation on the various methods available in this function, their performance characteristics, and whether they sample uniformly. Only the "ConfigurationModelSimple" method will perform exact uniform sampling of simple graphs, but it will be slow if the degrees are large.

IGKRegularGame currently uses the same underlying function as IGDegreeSequenceGame to generate random regular graphs.

---

To approximate a certain degree distribution (not degree sequence), you can use

• IGStaticPowerLawGame which creates graphs with power-law degree distributions.

• IGStaticFitnessGame which effectively implements the Chung–Lu model. The expected degree of each vertex will be (approximately) proportional to its "fitness value".