[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Degree-preserving rewiring of a large graph

From: Salvatore Loguercio
Subject: Re: [igraph] Degree-preserving rewiring of a large graph
Date: Wed, 02 Apr 2014 10:52:52 -0700
User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0

Thanks very much, Tamas - very useful information. I am going to use degree.sequence.game() for this task then - I agree with you, I don't really need rewire() - and this will make things much faster.

On 4/1/2014 11:30 AM, Tamás Nepusz wrote:

I am using igraph in R, and need a clarification about the rewire()
function. The parameter niter is the number of times the algorithm will
choose two arbitrary edges and shuffle them?
Yes; more precisely, niter is the number of times the algorithm will *try* to 
choose two random edges and shuffle them. This means that the iteration counter 
is increased even if the random selection happened to have yielded a pair which 
cannot be rewired sensibly because it would have created multiple edges 

I am working with a graph of ~150K edges - if my understanding of niter
is correct, how many iterations would be recommended to obtain a
reasonably rewired graph?
If you want to rewire your graph, I would suggest at least 10 times the number 
of your edges -- however, I’m pretty sure that there are more rigorous results 
in the literature. For instance, this deck of slides states that you need at 
least m/2 * ln(1/epsilon) steps where m is the number of edges and epsilon is 
some kind of tolerance value (although I did not find any definition for 
epsilon in the slides):


A pretty arbitrary choice of epsilon = 10^-6 would yield ~7 times the number of 

My current problem is to compute the probability of observing each
particular edge in a random graph with the same degree sequence.
In this case, you don’t really need rewiring; you can use the 
degree.sequence.game() function which generates graphs for you with a 
prescribed degree distribution. If you want to avoid loop and multiple edges, 
make sure to use method=“vl” or method=“simple.no.multiple”. method=“vl” is 
probably better as it is said to sample the space of all possible graphs with a 
prescribed degree sequence uniformly.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]