directed small world graph?

[Jie]

Hi all,

I'm looking for a way to generate a directed small world network and
did some search on the previous posts, where it was suggested to first
create an undirected one and use the to_directed method. However, as a
result, the edges are always symmetric, is there an alternative to
generate a small world graph with asymmetric directed links? Thanks!

best,
jie

[Rohan Dixit]

I'm curious, isn't there a little more complexity in a directed vs un-directed small world graph? There may be nodes which are unreachable from other nodes, so average shortest path length is infinity..... does preferential attachment work for indegree or outdegree hubs... etc? I don't know but would like to understand how this is done in the literature

Rohan

On Wed, May 4, 2011 at 10:45 AM, Minh Nguyen <nguye...@gmail.com> wrote:

Hi Jie,

On Thu, May 5, 2011 at 12:26 AM, Jie Bao <jie...@gmail.com> wrote:
> I thought about this, but random pruning could make the graph
> disconnected, right?

If you're talking about the Watts-Strogatz small-world network model,
the original model didn't explicitly require that a graph generated
via the Watts-Strogatz model to be connected (in the case of
undirected graphs) or strongly connected (in the case of digraphs).
But NetworkX should have a function to create a connected small-world
graph; I remember writing such a function for NetworkX.

Let G be a connected small-world graph that is undirected. Use some
function, say to_directed(), to get G to be directed; the result
should be a graph D that has the same vertex set as G, but the edge
list is slightly different from G. Note that the edge list E(G) of G
is such that if uv \in E(G) is an edge of G, then vu \in E(G) as well
due to G being undirected. Now D is such that if uv \in E(G), then we
have uv \in E(D) and vu \in E(D), both the latter being directed
edges. At least that's how I think to_directed() should behave. By
asymmetric, I mean that if uv \in E(D) then we also have vu \in E(D).
To obtain a version of D that is still directed and (possibly
strongly/weakly) connected, proceed as follows.

for each v \in V(D)
   for each u \in V(D)
       if vu \in E(D) and uv \in E(D)
           randomly delete from E(D) either uv or vu

The above is a simple way to achieve what I think you wanted. Now D is
originally strongly connected by virtue of the function to_directed().
So it's possible that by the end of the above random deletion
procedure, the resulting digraph is not strongly connected, but is
weakly connected.

--
Regards
Minh Van Nguyen

--
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.

[Chris Myers]

I wanted to do something similar to this the other day. In my case, I wanted to create a directed hypercube, with edges flowing through the hypercube from (0,0,...,0) to (1,1,...,1). nx.grid_graph enables me to build an undirected hypercube, but I needed to preferentially add edges to get them to point in the direction I desired.

In general, one needs to break the symmetry that is inherent in Graph.to_directed(). Another poster suggested breaking that symmetry by randomly selecting one of the two possible edges, but that is only one possible choice.

So this led me to wonder whether it would be useful to parameterize Graph.to_directed() with an optional function that differentiates between the two possible directed edges, similar to the way that Python list.sort() can be parameterized with a pairwise comparison function that specifies a local ordering for sorting. (The optional sort comparison function must have the same "behavior" as the builtin cmp function, such at cmp(x,y)=-1 if x<y, cmp(x,y)=0 if x==y, and cmp(x,y)=1 if x>y, but the whole point of providing one's own comparison function is that one is free to choose what <, ==, and > mean for arbitrary list elements.)

An edge ordering comparison function could be modeled, perhaps, on the same sort of cmp behavior: a directed edge is added from node x,y if cmp(x,y)==-1 (i.e., x is "less than" y), with both directed edges are added if cmp(x,y)==0. (This would be the default, thereby preserving the current behavior of Graph.to_directed() if no cmp function is provided.) Here is a modified version of Graph.to_directed():

def to_directed(self, cmp=None):
"""docstring ignored"""
from networkx import DiGraph
G=DiGraph()
G.name=self.name
G.add_nodes_from(self)
if cmp is None:
cmp = lambda x,y: 0
G.add_edges_from( ((u,v,deepcopy(data))
for u,nbrs in self.adjacency_iter()
for v,data in nbrs.items() if cmp(u,v)<1))
G.graph=deepcopy(self.graph)
G.node=deepcopy(self.node)
return G

For my directed hypercube, for example, I can act on an undirected grid_graph g as follows:

dg = g.to_directed(cmp=lambda x,y: cmp(sum(x), sum(y))) # edges point from nodes with lower index sum to higher index sum

The process of randomly selecting one of the two possible directed edges, though, is trickier, since the processing of the two possible directed edges is correlated (i.e., one edge is selected, and the other is not) and doesn't depend on the values of the node IDs. While the proposed construct could presumably handle such a situation, it is a bit more awkward than for cases where the selection can be made based on those node values.

Any thoughts on whether such a thing would be useful, and if so, whether there is a better solution than what I have proposed?

Thanks,
Chris

[Aric Hagberg]

On Thu, May 5, 2011 at 6:59 AM, Chris Myers <c.m...@cornell.edu> wrote:
> I wanted to do something similar to this the other day.  In my case, I wanted to create a directed hypercube, with edges flowing through the hypercube from (0,0,...,0) to (1,1,...,1).  nx.grid_graph enables me to build an undirected hypercube, but I needed to preferentially add edges to get them to point in the direction I desired.
>
> In general, one needs to break the symmetry that is inherent in Graph.to_directed().  Another poster suggested breaking that symmetry by randomly selecting one of the two possible edges, but that is only one possible choice.
>
> So this led me to wonder whether it would be useful to parameterize Graph.to_directed() with an optional function that differentiates between the two possible directed edges, similar to the way that Python list.sort() can be parameterized with a pairwise comparison function that specifies a local ordering for sorting.  (The optional sort comparison function must have the same "behavior" as the builtin cmp function, such at cmp(x,y)=-1 if x<y, cmp(x,y)=0 if x==y, and cmp(x,y)=1 if x>y, but the whole point of providing one's own comparison function is that one is free to choose what <, ==, and > mean for arbitrary list elements.)
>
> An edge ordering comparison function could be modeled, perhaps, on the same sort of cmp behavior: a directed edge is added from node x,y if cmp(x,y)==-1 (i.e., x is "less than" y), with both directed edges are added if cmp(x,y)==0.  (This would be the default, thereby preserving the current behavior of Graph.to_directed() if no cmp function is provided.)  Here is a modified version of Graph.to_directed():
>
>   def to_directed(self, cmp=None):
>       """docstring ignored"""
>       from networkx import DiGraph
>       G=DiGraph()
>       G.name=self.name
>       G.add_nodes_from(self)
>       if cmp is None:
>           cmp = lambda x,y: 0
>       G.add_edges_from( ((u,v,deepcopy(data))
>                          for u,nbrs in self.adjacency_iter()
>                          for v,data in nbrs.items() if cmp(u,v)<1))
>       G.graph=deepcopy(self.graph)
>       G.node=deepcopy(self.node)
>       return G
>
> For my directed hypercube, for example, I can act on an undirected grid_graph g as follows:
>
> dg = g.to_directed(cmp=lambda x,y: cmp(sum(x), sum(y)))   # edges point from nodes with lower index sum to higher index sum
>
> The process of randomly selecting one of the two possible directed edges, though, is trickier, since the processing of the two possible directed edges is correlated (i.e., one edge is selected, and the other is not) and doesn't depend on the values of the node IDs.  While the proposed construct could presumably handle such a situation, it is a bit more awkward than for cases where the selection can be made based on those node values.
>
> Any thoughts on whether such a thing would be useful, and if so, whether there is a better solution than what I have proposed?

That is an interesting idea.

An alternative approach (not sure it works for all cases proposed
here) is to skip the to_directed() method completely and just add the
edges to a new digraph. E.g. for sorted order you could use
(untested)

>>> D=nx.DiGraph(sorted(nx.hypercube_graph(3).edges()))

or for random selection of edge orientation

>> D=nx.DiGraph([random.sample(e,2) for e in nx.hypercube_graph(3).edges()])

This only works if the graph has no isolated nodes. But those can be
added with

>>> D.add_nodes_from(G)

Aric