random rewire

graph-tool
1

Hi,

I am trying to use the random_rewire function to generate a new network,
using the 'correlated' model. The network is pretty small (208 vertices,
594 edges - no loops or parallel edges). If I just run it with default
parameters, it rejects about 300-400 of the moves and 10000 iterations
takes about 1 minute. To improve the shuffling a bit, I tried to add
persist=True. Now the problem is, after 2 hours, it has not even completed
a single iteration. I am suspecting that it is stuck in an infinite loop
somewhere, but I cannot figure out why. Would there be any special property
of a graph which causes this?

For reference, these are the two commands I have tried executing:

K = 10000
# Finishes in about 1 minutes
for i in range(K):
    graph_tool.generation.random_rewire(testg, model='correlated')

# After 2 hours and counting, still has not finished one iteration
for i in range(K):
    graph_tool.generation.random_rewire(testg, model='correlated',
persist=True)
    print "%i done" % i

Also, the question I am trying to answer is, given the original graph and
properties, what is the size of the largest connected component observed
when the network is rewired at random, preserving node degree.

Thanks in advance,
David

attachment.html (1.52 KB)

2

Yes, if you forbid parallel edges or self-loops, not all proposed edge
rewires are possible (since they may generate parallel edges or
self-loops). If you have persist=False, and if a move is not allowed, it
is not made, and the algorithm moves to next edge. If you put
persist=True it keeps trying until it succeeds, but you may get stuck in
situations where all edge movements generate parallel edges or
self-loops, which is what you are experiencing.

The persist option is there because it is useful in some very specific
circumstances. In the vast majority of cases, you should just use
persist=False, and increase the value of "niter" until you achieve
equilibration.

Best,
Tiago