Re: [igraph] rewire

[Tamas Nepusz]

(2) If I set  niter = 100, does it mean 100 edge pairs will be rewired?

No, it means that 100 attempts will be made.  Some may be unsuccessful.

Correct.

 

Is there a probability that controls whether to rewire each selected edge pairs?

No, there isn't - each edge is selected with equal probability for a rewiring attempt. You can control the probability indirectly by specifying the number of trials. For instance, if the number of trials is equal to half the number of edges, then each edge is expected to be selected for rewiring once (although of course this is not guaranteed).

Some times a randomly selected edge pair can not be rewired, will this counted a trial or only successfully rewired ones will be counted as a trail?

"Trial" means "attempt".  Not all attempts will be successful.

Correct.

 

(3) Sometimes, the rewired network will be divided into several components, even when the original network is one connected component. Is there is a way to control the rewire process make the network connected?

No, there isn't - this would involve checking whether the network stays connected after each rewiring attempt, and this is costly. You can do this yourself, however:

1. make a copy of your graph

2. perform 1000 rewiring attempts, check whether the graph is connected

3. if the graph is connected, go to step 1 and continue rewiring.

4. if the graph is not connected, take the last copy of your graph and continue from step 2.

You could of course perform only one attempt in step 2, but this would probably be slow because the implementation of igraph_rewire first converts the graph to an alternative representation where rewiring is faster, and then converts it back. Therefore, the more attempts you perform in a single batch, the faster it will be - although of course you risk performing more trials unnecessarily before you realize that the graph became disconnected.

Rewiring many times creates a random graph with the same degree sequence as your starting point.  You can check out the degree sequence game function with the Viger-Latapy method, which creates connected graphs.

This is a very good point - in many cases, you are not actually interested in rewiring the graph, you just want to get another graph with the same degree sequence. The Viger-Latapy method in the degree sequence game does exactly this, and it also ensures connectedness.

Best,

T.