Sampling graphs with a given degree sequence

Usage
1

Example question.

I need to randomly sample graphs with a given degree sequence d = (d_1, d_2, \dots). I want to do uniform sampling, i.e. each graph should be generated with the same probability.

Can igraph do this? It has several functions for generating graphs with a certain degree, but it is unclear if the sampling is uniform.

2

igraph’s “degree sequence game” can do this, but not all methods sample uniformly. It is available as IGDegreeSequenceGame in IGraph/M (the Mathematica interface).

Let us create an example degree sequence:

In[1]:= Needs["IGraphM`"];

In[2]:= ds = ReverseSort@VertexDegree@IGBarabasiAlbertGame[20, 2, DirectedEdges -> False]
Out[2]= {13, 10, 9, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

Check if it is graphical:

In[3]:= IGGraphicalQ[ds]
Out[3]= True

Check the usage of IGDegreeSequenceGame and the available methods:

image

The default method is FastSimple. This method is relatively fast, and generates simple graphs. But it does not sample uniformly. For that we need the ConfigurationModelSimple method which generates graphs using the configuration model, and throws away any non-simple ones. Unfortunately, most graphs with this degree sequence are not simple, so this algorithm takes a rather long time before it finds a simple graph.

IGDegreeSequenceGame[ds, Method -> "ConfigurationModelSimple"]

image

Perhaps a more practical method is to first generate a single graph with this degree sequence:

g = IGRealizeDegreeSequence[ds]

image

then rewire its edges while keeping the degree sequence fixed.

IGRewire[g, 1000]

image

In[10]:= VertexDegree[%] == ds
Out[10]= True

The rewiring algorithm is such that this will effectively sample uniformly, provided that a sufficient number of rewiring steps were performed. The problem with this method is that it is unclear how many rewiring steps are sufficient. Use too few, and your samples will be correlated. There are no exact mathematical results for this. As a guideline, you can compute some graph quantity and keep rewiring until the correlation with the original graph is lost.

To illustrate the correlations, here is the plot of the assortativity in 5 different random rewiring sequence (all starting from the same graph) as a function of the number of rewiring steps.

SeedRandom[1234]
ds = VertexDegree@IGBarabasiAlbertGame[100, 2, DirectedEdges -> False];
ListLinePlot[
 Table[
  GraphAssortativity /@ 
   NestList[IGRewire[#, 1] &, IGRealizeDegreeSequence[ds], 2000],
  {5}
  ],
 PlotRange -> All
 ]

image

Notes:

  • Also check out the VigerLatapy method of IGDegreeSequenceGame. It uses a conceptually similar rewiring algorithm to what I showed above, but it generates only connected graphs, something that may or may not be desirable depending on the application.
  • Like other igraph interfaces, IGraph/M uses Mathematica’s own random generator even for igraph functions. Therefore, it can be influenced with Mathematica’s built-in SeedRandom command.