Szabolcs Horvát
2018-03-06 13:28:55 UTC
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.
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.