sna (version 2.8)

rgws: Draw From the Watts-Strogatz Rewiring Model

Description

rgws generates draws from the Watts-Strogatz rewired lattice model. Given a set of input graphs, rewire.ws performs a (dyadic) rewiring of those graphs.

Usage

rgws(n, nv, d, z, p, return.as.edgelist = FALSE)
rewire.ud(g, p, return.as.edgelist = FALSE)
rewire.ws(g, p, return.as.edgelist = FALSE)

Value

A graph or graph stack containing draws from the appropriate W-S process.

Arguments

n

the number of draws to take.

nv

the number of vertices per lattice dimension.

d

the dimensionality of the underlying lattice.

z

the nearest-neighbor threshold for local ties.

p

the dyadic rewiring probability.

g

a graph or graph stack.

return.as.edgelist

logical; should the resulting graphs be returned in edgelist form?

Author

Carter T. Butts

Warning

Remember that the total number of vertices in the graph is nv^d. This can get out of hand very quickly.

Details

A Watts-Strogatz graph process generates a random graph via the following procedure. First, a d-dimensional uniform lattice is generated, here with nv vertices per dimension (i.e., nv^d vertices total). Next, all z neighbors are connected, based on geodesics of the underlying lattice. Finally, each non-null dyad in the resulting augmented lattice is "rewired" with probability p, where the rewiring operation exchanges the initial dyad state with the state of a uniformly selected null dyad sharing exactly one endpoint with the original dyad. (In the standard case, this is equivalent to choosing an endpoint of the dyad at random, and then transferring the dyadic edges to/from that endpoint to another randomly chosen vertex. Hence the "rewiring" metaphor.) For p==0, the W-S process generates (deterministic) uniform lattices, approximating a uniform G(N,M) process as p approaches 1. Thus, p can be used to tune overall entropy of the process. A well-known property of the W-S process is that (for large nv^d and small p) it generates draws with short expected mean geodesic distances (approaching those found in uniform graphs) while maintaining high levels of local "clustering" (i.e., transitivity). It has thus been proposed as one potential mechanism for obtaining "small world" structures.

rgws produces independent draws from the above process, returning them as an adjacency matrix (if n==1) or array (otherwise). rewire.ws, on the other hand, applies the rewiring phase of the W-S process to one or more input graphs. This can be used to explore local perturbations of the original graphs, conditioning on the dyad census. rewire.ud is similar to rewire.ws, save in that all dyads are eligible for rewiring (not just non-null dyads), and exchanges with non-null dyads are permitted. This process may be easier to work with than standard W-S rewiring in some cases.

References

Watts, D. and Strogatz, S. (1998). ``Collective Dynamics of Small-world Networks.'' Nature, 393:440-442.

See Also

rgnm, rgraph

Examples

#Generate Watts-Strogatz graphs, w/increasing levels of rewiring
gplot(rgws(1,100,1,2,0))     #No rewiring
gplot(rgws(1,100,1,2,0.01))  #1% rewiring
gplot(rgws(1,100,1,2,0.05))  #5% rewiring
gplot(rgws(1,100,1,2,0.1))   #10% rewiring
gplot(rgws(1,100,1,2,1))     #100% rewiring 

#Start with a simple graph, then rewire it
g<-matrix(0,50,50)
g[1,]<-1; g[,1]<-1    #Create a star
gplot(g)
gplot(rewire.ws(g,0.05))  #5% rewiring