# Sampling graphs with a given degree sequence

**URL:** <https://igraph.discourse.group/t/sampling-graphs-with-a-given-degree-sequence/32>\
**Category:** Usage\
**Tags:** Mathematica\
**Created:** [28 January 2020 16:23 UTC](https://igraph.discourse.group/t/sampling-graphs-with-a-given-degree-sequence/32 "2020-01-28T16:23:29Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [28 January 2020 16:23 UTC](https://igraph.discourse.group/t/sampling-graphs-with-a-given-degree-sequence/32/1 "2020-01-28T16:23:29Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [28 January 2020 16:42 UTC](https://igraph.discourse.group/t/sampling-graphs-with-a-given-degree-sequence/32/2 "2020-01-28T16:42:16Z")

</div>

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:

```auto
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:

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

```

Check the usage of `IGDegreeSequenceGame` and the available methods:

![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/8c0db1573b7bdb2463b6249af1924e6e7f7d85af.png)

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.

```auto
IGDegreeSequenceGame[ds, Method -> "ConfigurationModelSimple"]

```

![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/42f70ebfaa8c40c6d49c4d9bcc38531fb9c45d2d.png)

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

```auto
g = IGRealizeDegreeSequence[ds]

```

![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/52e1a42be50688e32c28d91152ab5dffb32fa52a.png)

then rewire its edges while keeping the degree sequence fixed.

```auto
IGRewire[g, 1000]

```

![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/cf9fd94133d2ca43ad51205b7cb3dcd91804a53c.png)

```auto
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.

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

```

![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/1X/0f4a091faf8cc90883acecf8e43e9c50fba3125d.png)

* * *

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.