Re: [igraph] Questions about the watts_strogatz parameters for creating small world network [python-igraph]

[Tamas Nepusz]

Hello,

> Nevertheless, I'm finding some trouble understanding the Watts_Strogatz
> implementation. I can't figure out what the dim and size parameters means.
(Let's assume nei=1 for sake of simplicity). The basic idea of the
Watts-Strogatz algorithm is that you start from a regular circular
lattice in some dimension and then rewire each edge with some
probability. With nei=1, size=N and dim=1 you would start from a ring
with N vertices; dim=2 would start from a torus (essentially an NxN
grid such that the nodes on the "opposite edges" of the grid are
connected to each other), dim=3 and above would start from
n-dimensional hypertori and so on. So, the initial graph will always
have size^{dim} vertices (N vertices in 1D, N^2 vertices in 2D, N^3
vertices in 3D and so on), and each vertex in the graph will have
2*dim neighbors (2 in 1D, 4 in 2D, 6 in 3D etc). The total number of
edges is therefore size^{dim}*2*dim/2 = size^{dim+1}.

If nei is larger than 1, this complicates things because each vertex
will be connected with each other vertex if their distance in the
_original_ lattice (with nei=1) is less than or equal to the value of
the 'nei' parameter.

T.