grid_graph algorithm and initialization of Watts-Strogatz graph

[Maurício Girardi Schappo]

Greetings everyone!

I've read the grid_graph method algorithm and seen it's results and I keep with a doubt:

When I'm going to create a 2x2 square lattice, for instance, with free boundary conditions, I'd expect the following adjacency matrix:

0 1 1 0

1 0 0 1

1 0 0 1

0 1 1 0

because the elements are connected as follow

1 - 2

|     |

3 - 4

when I use networkx to generate the same adjacency matrix:

python -c "import networkx as nx; import numpy as np; np.savetxt('grid.dat',nx.adj_matrix(nx.grid_graph(dim=[2,2])),fmt='%1d')"

the output is

0 0 1 1

0 0 1 1

1 1 0 0

1 1 0 0

what would imply in the following connections

1 - 3

|     |

4 - 2

And this takes me to a question (sorry if this question is too obvious):

- Are these graphs topologically identical? (I think so, but I don't have means to prove that - I mean, the adjacency matrix of the latter is just a reorganization of the rows and columns of the first one, i.e. they are linearly dependant on each other, aren't they? - I'm just arguing without a paper and a pencil, so excuse me if I've just said no truth)

Well, even if they are identical, I'd like to build a graph with the first adjacency matrix in order to feed it to the watts_strogatz_graph generator, is there a straight forward way to do it? If it gets too much complicated, I'll have to content myself feeding it with the standard grid_graph of networkx.

Thanks in advance!

--

PS: just to clarify, I don't know python, I only use networkx as an "plugin" in my C# program to create random graphs adjacency matrixes, so I've done my own algorithms to create square and linear lattices (rings), with first neighbour connections and free or periodic boundary conditions, in order to create the first mentioned graph type.

-- 

Maurício
"De que serve do labor a sina, se o elaborado ao nada se destina?" (Goethe)

[Aric Hagberg]

Yes, they are isomorphic. You can control the ordering in the output
by specifying the "nodelist" parameter like this:

In [1]: import networkx as nx

In [2]: G=nx.grid_graph(dim=[2,2])

In [3]: nx.adj_matrix(G)
Out[3]:
matrix([[ 0., 0., 1., 1.],
[ 0., 0., 1., 1.],
[ 1., 1., 0., 0.],
[ 1., 1., 0., 0.]])

In [4]: nx.adj_matrix(G,nodelist=sorted(G.nodes()))
Out[4]:
matrix([[ 0., 1., 1., 0.],
[ 1., 0., 0., 1.],
[ 1., 0., 0., 1.],
[ 0., 1., 1., 0.]])

Aric

[Maurício Girardi Schappo]

Thanks, Aric.

But I think I misunderstood what create_using parameter is. I mean, looking more accuretely to the code available in the track, NetworkX does not use the create_using as a base to the generated graph, but only uses its instance.

I mean, if I do:

gg = nx.grid_graph(dim=[20,20])

wsg = nx.watts_strogatz_graph(4, 4, 0.02, gg)

the method watts_strogatz_graph will still build the graph based on that default ring, etc, not based on the passed grid_graph gg attribute, isn't it?

So is it possible to build a Watts Strogatz Graph based on a square lattice, or a grid_graph, instead of a ring? Will it still be a Small-world network?

thanks!

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[Dan Schult]

The routine watts_strogatz_graph implements their algorithm which
uses a ring as the starting point. It would be fairly straight
forward to pull off the last 12-15 lines of that function and
make a new function that rewires any given network with probability
p for each edge. This will not be a Watts Strogatz network, and
I suspect that whether it is small world or not depends on the
network you start with.

Essentially, rewiring starting from a lattice lets you choose
(by choosing p) where your network will be between a lattice
and gnp random graph. If you start with a different network your
choice of p will put you somewhere between a gnp random network
and what you started with. Watts and Strogatz's article shows
that somewhere along that range of p-values, the networks have
the small world property. I suspect it would be true if you
started with a grid graph that for some values of p you would also
have that property, but I don't have a guarantee.

Even the Watts Strogatz algorithm won't give a small world graph
unless you choose p to be in the right range.

I would suggest that you try creating a function using the last
lines of the watts_strogatz_graph code if you are interested in
tweaking their model to start with other graphs. If that is useful
to others, we could include it in networkx somewhere....
Dan

[Maurício Girardi Schappo]

I think commenting out lines 403, 411, 412 and 413 would result in the functionality I mentioned before, wouldn't?

[Dan Schult]

You'll need to change more than that because the
nodes in a grid graph aren't range(n) and the code
relies on that.