Hcfyk

I am trying to reproduce a network generated by a configuration model given degree vector truncated power law distribution.

I am relying on the following function from the IGraph/M package for Mathematica:

IGDegreeSequenceGame[yy, Method -> "FastSimple"];

where yy is the data and FastSimple is the method option.

An example degree sequence is

yy = {10, 7, 6, 6, 7, 8, 9, 11, 8, 7, 6, 9, 13, 8, 13, 19, 6, 12, 11, 11, 6, 7, 6, 6, 12};

Method doesn't converge; the dimension of yy is 25, and I would like to use it on bigger networks.

Is there a fast way I can generate a network from a configuration model (without loops) with Mathematica?

Exact sampling with a given degree sequence

The example degree sequence that you provided is:

yy = {10, 7, 6, 6, 7, 8, 9, 11, 8, 7, 6, 9, 13, 8, 13, 19, 6, 12, 11, 11, 6, 7, 6, 6, 12};

With this degree sequence,

IGDegreeSequenceGame[yy, Method -> "FastSimple"]

returns immediately, contrary to your claim.

However, Method -> "FastSimple" does not implement the configuration model. It implements a similar algorithm that is much faster but does not sample graphs uniformly. In other words, not all graphs that have this degree sequence will be generated with the same probability.

To use the configuration model to generate simple graphs, use

IGDegreeSequenceGame[yy, Method -> "ConfigurationModelSimple"]

As you say, this will not return. It takes too long. This algorithm (i.e. the configuration model) is simply too slow on this degree sequence, whether implemented in IGraph/M or another package.

I am not aware of any method which is capable of the exact and uniform sampling of simple graphs with such a degree sequence (if you are, let me know).

Approximate sampling with MCMC

One alternative option you have is to use Markov-Chain based sampling. First, create a single realization of the degree sequence then "shuffle its edges around" while keeping the degree sequence with IGRewire. Provided that enough rewiring steps are made, this method will sample approximately uniformly. It would sample uniformly for an infinite number of rewiring steps.

g = IGRealizeDegreeSequence[yy]

IGRewire[g, 1000]

You can use some heuristics to decide on how many rewiring steps are sufficient for the degree sequence you are working with. For example, correlations seem to be lost with less than 1000 rewiring steps for the sequence you quoted.

am = AdjacencyMatrix[g];

ListLogLinearPlot@Table[

  {k, Flatten[am].Flatten@AdjacencyMatrix@IGRewire[g, k]},

  {k, Round[2^Range[0, 15, 0.1]]}

  ]

You can also use Method -> "VigerLatapy" in IGDegreeSequenceGame, which implements a similar method for sampling connected graphs specifically. See the documentation for a reference to the paper.

Sampling graphs with power-law degree distributions

If your goal is to generate a graph with a power-law degree distribution (not a specific degree sequence), also take a look at IGStaticPowerLawGame. See the references within the C/igraph documentation for how it works. It implements a variation of the Chung-Lu model.

A note about the built-in DegreeGraphDistribution

A note about RandomGraph[DegreeGraphDistribution[...]]: it does not sample uniformly and I was not able to get information from Wolfram Support about how this method works. I would be cautious when using it.