Re: [igraph] rewire vs. degree.sequence.game

[Chris Watson]

Thank you for the response.

One of the graphs I am using currently only has ~1e2 edges, so I think 1e4 may be enough. I remember reading a paper citing that 10*|E| is sufficient, but will have to look again.

Additionally, I will be using a Markov Chain method to rewire graphs so that they match the transitivity of my graph of interest (in addition to the degree distribution). I was mainly wondering if using 'rewire' with ~1e4 iterations would create a graph that is "random enough" from which to start the Markov Chain process.

Thanks,
Chris

On Fri, Jul 4, 2014 at 5:48 AM, Tamás Nepusz <address@hidden> wrote:

 
Hello,

> I was wondering how different the functions 'rewire' and 'degree.sequence.game' are.

degree.sequence.game() constructs a graph from scratch, while rewire() rewires an existing graph. This means that you must "guesstimate" the number of rewiring attempts to perform in case of your particular graph to ensure that you do enough rewires so that the starting point (i.e. the original graph) becomes irrelevant. I think there are some theoretical results (or at least rules of thumb) in the literate about the optimal number of rewiring attempts, but I cannot cite any off the top of my head. In general, the number of rewiring attempts is usually chosen so that every edge of the graph is attempted to be rewired at least k times on average -- choosing the right k is then up to you.

> Would there be a problem with calling rewire with, e.g. 1e4 iterations?

It depends on the size of your graph. If your graph contains, say, 1e6 edges, then using only 1e4 rewiring attempts is not enough because it will touch only 2e4 edges out of the 1e6 -- and even then it is not guaranteed that every rewiring attempt is successful.

You might also try static.fitness.game(), which generates networks where the probability of an edge between two vertices is proportional to some fitness scores of the endpoints. It can be shown that the _expected_ degrees of the vertices are then proportional to the fitness scores (but not the _actual_ degrees) if we allow loop and multiple edges. (Banning loop and multiple edges introduces some bias, but it might not be noticeable for your graphs so it's worth trying if you don't need to match the degrees of the original graph *exactly* but only on average).

Best,
T.