igraph-help
[Top][All Lists]

## [igraph] status of the Viger-Latapy sampling method for graphs with a gi

 From: Szabolcs Horvát Subject: [igraph] status of the Viger-Latapy sampling method for graphs with a given degree sequence Date: Tue, 6 Mar 2018 14:28:55 +0100

Hello everyone,

I am looking at the various methods available in igraph to *uniformly* sample random graphs with a given degree sequence.  The obvious candidate function is  igraph_degree_sequence_game().

http://igraph.org/c/doc/igraph-Generators.html#igraph_degree_sequence_game

This function provides three generation methods:

"SIMPLE" is explained, and it's clear that the sampling is not uniform.  Also, this method allows multigraphs and self-loops.

"SIMPLE_NO_MULTIPLE" is explicitly mentioned as not uniform.

What remains is the Viger-Latapy method. The link here is broken, but it's easy to google up the original paper, https://arxiv.org/pdf/cs/0502085.pdf, the abstract of which says:

"We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence."

While I didn't read the entire paper, the abstract suggests that this method should sample uniformly from the set of *connected* simple graphs.  However, this does not appear to be the case in a simple test.

Consider the degree sequence (1, 2, 1, 2).  The only two simple graphs with this degree sequence are:

But the Viger-Latapy method, as implemented in igraph, will generate only the second one.

Let's look at a more complicated example, the sequence (1, 2, 2, 2, 1). Here's the list of such graphs (one of which is not connected):

The Viger-Latapy method generates only these:

Within this set, the sampling is indeed uniform, but there are three connected graphs which are never generated.

Question:

Is the Viger-Latapy method known to be flawed, or is there something I'm missing here?  There doesn't seem to be a peer-reviewed publication about this.

Szabolcs

P.S. A method that does work in practice is generating a single realization of the degree sequence, then using igraph_rewire() on it. What is unclear in such situations is how many rewiring steps are necessary to approximate uniform sampling.