Does rewire(g, keeping_degseq) preserve the degree sequence (degree of each node is preserved), or the degree distribution? My nodes have identities, and I would like a rewiring that preserves the degree distribution but permits degrees of individual nodes to change as the graph is re-wired.
When you use rewire with keeping_degseq, edges are only rewired, so nodes are guaranteed to keep the exact same degree. Hence, degrees of individual nodes will never change.
The alternative that you can use is sample_degseq which will sample a graph from a degree sequence. Here, the degree for each node will be exactly the degree that is provided. Perhaps this still does not satisfy your needs. If that is the case, you could first create a distribution of node degrees, and then sample degrees from this distribution, and then sample a graph from the sampled degrees. See some of the later examples provided in the documentation for sampling from a particular distribution, for example:
## Power-law degree distribution
## Note, that we correct the degree sequence if its sum is odd
degs <- sample(1:100, 100, replace=TRUE, prob=(1:100)^-2)
if (sum(degs) %% 2 != 0) { degs[1] <- degs[1] + 1 }
g <- sample_degseq(degs, method="vl")
all(degree(g) == degs)
I don’t understand the question. Can you show a small example which illustrates what you mean by keeping the degree distribution but not the degree sequence?
Do you have some vertex attributes and you simply want to randomly permute the vertices and change which attribute is assigned to which?
I don’t understand the question. Can you show a small example which illustrates what you mean by keeping the degree distribution but not the degree sequence?
I think one way of asking my question is this.
Consider a graph g
d0=as.vector(degree(g))
g1=rewire(g, keeping_degseq)
d1=as.vector(degree(g1))
Is it the case that d1==d0 is TRUE everywhere? That is how I understand preserving the degree sequence.
But it could be that d1 is a permutation of d0. (i.e. d1==d0 is FALSE in at least some places but sort(d1)==sort(d0) is TRUE everywhere). That would preserve the degree distribution but not the degree sequence (at least in the jargon I use).
Do you have some vertex attributes and you simply want to randomly permute the vertices and change which attribute is assigned to which?
I think just permuting the node attributes doesn’t do it, because that preserves the network architecture. For example it retains degree assortativity, average path length… and (all) other aggregate structural properties of the network.
Ahh, perhaps the solution is rewiring preserving degree sequence and then permuting node attributes. That might do it.
I do have another question about re-wiring.
Is it possible to re-wire part of the graph (eg a pre-specified subset of nodes, limiting the re-wiring to the edges within that subset).
Essentially I have a graph of many components and I want to re-wire within each component without changing which nodes are in which component.
I know I could create a subgraph; remove those nodes from the graph; re-wire the subgraph; add the re-wired subgraph back to the larger graph. And do that for each component. But is there a direct way to do it?
I could also write a function to implement the re-wiring algorithm on a subset of nodes, but it might be slow to execute (this is in R).
Thanks (I see I answered you and Szabolcs in the wrong order).
Your first paragraph answers my basic question.
Thanks for your suggestions about sampling. I will see what I can make work.
If there are no attributes, then all these measures will be invariant to the vertex ordering. Without attributes, the graph is essentially unlabelled and the vertex ordering is merely an irrelevant technical detail of how the graph is stored on the computer.
If there are vertex attributes, then some graph measures are still do not depend on them. Assortativity or mean path length, or any other “structural” property (i.e. depending only on which vertices are connected, but not any of their attributes) are invariant of vertex ordering.
The mean path length depends on edge weights/lengths, but note that igraph only keep vertex attributes but discards any edge attributes during rewiring.