Re: [igraph] Rewire probabilities question

[Tamas Nepusz]

Hi,

Q1:  Does the code below identify properly the new edges in the rewired graph in comparison to the original?

Well, the code is more or less correct -- it does not account for corner cases like when an edge ends up being rewired twice or more (in such cases, the edge may even end up being identical with some other edge from the original one), but for large graphs, the probability of such corner cases is negligible. Also, the function currently relies on the fact that the order of edges is not changed during rewire, i.e. edge i in the original graph ends up being edge i in the rewired graph -- the documentation does not guarantee this so it may break in future releases.

Q2:  Why is it that, with a rewire of approx p=.30, I get approx 50% new edges (given the way I’ve defined new below).

It is because p is not equal to the probability of selecting an edge for rewiring. I am not sure about the documentation of the R interface of igraph; it may not be stated there, but the documentation of the C core says that "each endpoint of each edge is rewired to a uniformly randomly chosen vertex with constant probability". Since an edge in an undirected graph has two endpoints, each edge gets *two* chances to be rewired -- therefore, the probability of an edge _not_ being rewired is equal to (1 - 0.3) * (1 - 0.3) = 0.49.

T.