Watts-Strogatz networks without loops and multiple edges

[Gábor Csárdi]

Loops seem straightforward, multiple edges are maybe a bit more tricky.

[Gábor Csárdi (gabor.csardi)]

Loops are done in revision #2306 (0.6-main).

[Alastair Droop (apd500)]

As far as we can tell from the code, the current implementation for rewire.edges is not implementing the Watts-Strogatz rewiring model in all cases.

My project uses the WS rewiring method for 'edge' cases that break some of the original WS conditions. The R code that we use to perform the rewiring as defined in the original WS 'small-world' paper is attached below. This code is much slower than the current implementation, but follows the WS method correctly.

Thanks!
Alastair

# Performs random edge rewiring on g following the ws model
# g is a graph to rewire
# p is the probability of each edge being rewired
ws.rewire <- function(g, p){
 if((p < 0) || (p > 1)) stop('p out of range')
 # Create vectors of the vertex possibilities to consider:
 valid.connections <- do.call('rbind', sapply(1:floor(vcount(g) / 2), function(d){
  vertices.from <- (1:vcount(g)) - 1
  vertices.to <- (vertices.from + d) %% vcount(g)
  return(cbind('from'=vertices.from, 'to'=vertices.to))
 }, simplify=FALSE, USE.NAMES=TRUE))[1:ecount(g), ]
 # Go through each valid connection in turn, rewiring if necessary:
 for(i in 1:nrow(valid.connections)){
  vertex.start <- valid.connections[i, 'from']
  vertex.current.end <- valid.connections[i, 'to']
  # Find out if the edge between the two selected vertices exists:
  if(!are.connected(g, vertex.start, vertex.current.end)) next
  # 'Roll the dice' to see if we need to do anything:
  if(runif(1, min=0, max=1) > p) next
  # Get the selection of vertices that we can rewire to:
  valid.new.end.vertices <- setdiff(setdiff(V(g), V(g)[nei(vertex.start)]), vertex.start)
  # If there are no possible new end vertices, return NA:
  if(length(valid.new.end.vertices) == 0) return(NA)
  # Choose a new end point from the list of valid new end points:
  vertex.new.end <- sample(valid.new.end.vertices, 1)
  # Update the graph:
  g <- add.edges(g, c(vertex.start, vertex.new.end))
  g <- delete.edges(g, E(g, P=c(vertex.start, vertex.current.end)))
 }
 # Return the new graph:
 return(g)
}

[Gábor Csárdi (gabor.csardi)]

Thanks Alastair, the challenge is to make detecting and avoiding the multiple edges fast....

[Gábor Csárdi (gabor.csardi)]

Finished in revision #2456 (0.6-main).

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/210