Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

NetworkX multi-directed graph possible?

I have a network for which I'm trying to figure out the best possible graph representation. I'm no graph theorist, but a biologist, so please pardon my lack of technicality here.

Currently, the network can be thought of as follows: "n" layers of networks, each layer holding a different set of edges between the nodes. Each edge is directed, and has a probability associated with it, but that probability property isn't used until later. Each layer is stored as a separate graph, as a CSV file, in an adjacency list representation.

Using an adjacency list representation, I have a "summary" layer, in which I compress all "n" layers, with each layer contributing a value of "+1" to the weights between each node. This is currently stored as a separate graph, as a CSV file, in an adjacency list representation.

If there were "n" edges between a pair of nodes, then in the summary layer, there the edge would have a weight of "n"; there can only be "n" or fewer edges between any pair of nodes.

I also have a "full-only" layer, which is only comprised of the edges that have weight "n". Similarly, currently stored as a CSV file, in an adjacency list representation.

Finally, I have a "most probable full-only" layer. In this layer, the probabilities kick in. For each of the "full-only" layer edges, I multiply all of the probabilities associated with each of the n edges (recall: the "full" layer is the sum of "n" edges, each edge with a probability).

In my analysis of this network, sometimes it's convenient to be able to switch between any of the "n" layers and the "summary" layers. However, the most convenient minimal storage format (i.e. without pre-computing anything) is to store the individual edges as a table (illustrated below):

|Node 1 | Node 2 | Layer 1 Weight | Layer 2 Weight | ... | Layer n Weight |
|-------|--------|----------------|----------------|-----|----------------|
|  x    |   y    |   0.99         |       1.00     | ... |       1.00     |
|  x    |   z    |   0.98         |       1.00     | ... |       0.97     |
|  y    |   z    |   0 (no edge)  |       1.00     | ... |       1.00     |

I say that this format is convenient, because I am able to generate such a table very easily.

So here's my question: is it possible in NetworkX to store such a graph (multi-layered, directed on each layer)? If it were possible, then I'd imagine being able to write functions to compute, on-the-fly, the "summary" graph, the "full-only" graph, and the "most probable full-only" graph, since they are subsets of one another. I can also imagine writing functions that compute other graphs, such as the graph that also incorporates complementary sets of multiple edges into the nodes that don't have full edges going into each node.

However, checking the NetworkX documentation, I can't find anything like what I'm looking for. The best I could find is a "multigraph", which allows multiple edges between nodes, but each edge has to be undirected. Am I missing something here?

Also, is there a better representation for what I'm trying to achieve? Again, I'm lacking experience with graph theory here, so I might be missing something. Many thanks (in advance) to everyone who takes time to respond!

like image 294
ericmjl Avatar asked Dec 18 '13 06:12

ericmjl


1 Answers

There is a MultiDiGraph() object in NetworkX that might work in your case. You can store multiple directed edges, each with arbitrary attributes. The nodes can also have arbitrary attributes.

In [1]: import networkx as nx

In [2]: G = nx.MultiDiGraph()

In [3]: G.add_edge(1,2,color='green')

In [4]: G.add_edge(1,2,color='red')

In [5]: G.edges(data=True)
Out[5]: [(1, 2, {'color': 'green'}), (1, 2, {'color': 'red'})]

In [6]: G.node[1]['layer1']=17

In [7]: G.node[1]['layer2']=42

In [8]: G.nodes(data=True)
Out[8]: [(1, {'layer1': 17, 'layer2': 42}), (2, {})]

There are some helper functions to get and set node attributes that might be useful, e.g.

In [9]: nx.get_node_attributes(G,'layer1')
Out[9]: {1: 17}
like image 144
Aric Avatar answered Oct 10 '22 20:10

Aric