sample_degseq edge.switching.simple vs rewire with = keeping_degseq

1

What is the relationship between this new option for sample_degseq

sample_degseq method = “edge.switching.simple”

The “edge.switching.simple” is an MCMC sampler based on degree-preserving edge switches. It generates simple undirected or directed graphs.

and rewire with = keeping_degseq?

This function can be used together with rewire() to randomly rewire the edges while preserving the original graph’s degree distribution.

Different implementations? Any reason to prefer one over the other?

Thanks, Dan

2

Effectively, sample_degseq() calls realize_degseq() to build a single graph, then it calls rewire(with=keeping_degseq()) with a constant time the edge count steps. Of course, this is all done in C, not in R.

At the moment it does 10 times the edge count switches (rewiring steps), but we may change this without notice (which is why the exact number is not documented). I believe there are no hard mathematical results on how many switches are “enough”, except for specific graph types, such as regular graphs. I meant to look into empirical studies on the same and improve the stopping condition, but I didn’t have time. This is interesting and it’s been on my TODO list for a couple of years now: [2105.12120] Sampling random graphs with specified degree sequences

No and no (other than convenience).

3

Sorry for the shameless plug, but I think section 2.1 is a pretty good overview of the topic :slight_smile:

https://iopscience.iop.org/article/10.1088/2632-072X/abced5/meta#jpcomplexabced5s2

4

And for full disclosure, there’s a low-consequence bug when dealing with directed graphs: igraph_rewire cannot reach all directed graphs with the same degree sequence · Issue #1456 · igraph/igraph · GitHub It turns out that switching two edges is not sufficient for reaching all realizations. One needs switches between 3 edges, i.e. (a,b), (c,d), (e,f) → (a,f), (c,b), (e,d), to handle some very dense structures. This has little practical consequence for typical networks we work with, but it’s been on my radar to fix for a while now …

5

Sz, thank you for your explanation, and I agree that your article gives a clear explanation!

I have been using niter = ecount(g)*100 as a minimum rewiring, but have always wondered whether this is overkill. It would be good to hear if anyone has empirically or theoretically grounded results. (I’m not doing any work that might be affected by it; just want to pass accurate info on to my students.)

6

What I do to investigate it in practice is to see how a graph measure evolves with rewiring, which gives some clues about how many rewiring steps might be enough in practice. My experience was that a few times the edge count is likely enough, 100 times the edge count may be overkill.

Here’s an interesting experiment:

  • Take a graph degree sequence (for example, by first generating a simple graph, then taking its degrees).
  • Create two graphs with these degrees, in such a way that one has high positive, the other high negative assortativity. igraph_realize_degree_sequence() with the “largest first” and “smallest first” methods achieves this.
  • Rewire both, step by step, and keep track of the assortativity. See how many steps are needed until their assortativities become the same. This is Fig 6b in my paper.