Re: [igraph] Can rewire() reach all possible directed graphs?

[Tamas Nepusz]

> R/igraph has a function rewire() for rewiring edges of a graph while
> preserving the degree sequence.  This function has changed between v0.7 and
> v1.0, so my question applies separately to both versions:
> 
> With the rewiring method it uses, does it sample the space of _all_
> possible directed graphs?
Hmmm, tricky question -- you have to search the literature to see if it has
actually been proven that it is possible to reach any graph with the given
(directed) degree sequence from any other graph with appropriate rewiring
steps. If I remember correctly, it has been proven for undirected graphs but
I'm not sure about the directed case. But note that even if the graph space is
traversable, it is still not guaranteed that the rewiring method will sample
uniformly if it is being run for a long time.

This paper might be relevant to you:

http://arxiv.org/abs/1109.4590

-- 
T.