3d graphs

[jeffg]

Could someone point me to the best functions to create a 3d (providing
x,y,z) force-directed / spring layout? I'm trying to work though the
documentation but quick searches don't pull up much on 3d. However,
I've read that NextworkX can do it... is this correct, if so.. some
examples would be great! Thanks

[Aric Hagberg]

Some of the algorithms in
https://networkx.lanl.gov/trac/browser/networkx/trunk/networkx/drawing/layout.py
work in arbitrary dimensions.

In particular spring_layout() is a force-directed node positioning
algorithm that will produce 3d coordinates:

In [1]: import networkx

In [2]: G=networkx.complete_graph(5)

In [3]: pos=networkx.spring_layout(G,dim=3)

In [4]: pos
Out[4]:
{0: array([ 0.82464301, 0.51411248, 0.32319794]),
1: array([ 0.52827386, 0.25559755, 0.34263581]),
2: array([ 0.50416188, 0.74054859, 0.31596981]),
3: array([ 0.71561698, 0.53219317, 0.70112578]),
4: array([ 0.34086317, 0.50437363, 0.58353033])}

I see the documentation is really sad. I've opened a ticket to improve that.
https://networkx.lanl.gov/trac/ticket/223

Aric

[Andrew Conway]

The layout algorithm in UbiGraph is also force-directed, and NX support calls to UG with the UbiGraph() class.

Examples: http://ubietylab.net/blog/?p=21

___________________________________

Drew Conway

Ph.D. Candidate

Department of Politics, New York University

agc...@nyu.edu

http://homepages.nyu.edu/~agc282

[jeffg]

Thanks for the example.
I'm getting an odd error though. This is the first time I've used
NetworkX (and Python).

When I issue the command

>>> pos=networkx.spring_layout(G,dim=3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'module' object has no attribute 'spring_layout'

So I then issued the command

>>> from networkx.drawing.layout import *
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\Python26\Lib\site-packages\networkx\drawing\layout.py",
line 33, in <module>
Raise ImportError, "numpy and/or Numeric can not be imported."
ImportError: numpy and/or Numeric can not be imported.

Thoughts?

On Feb 5, 11:26 pm, Aric Hagberg <hagb...@lanl.gov> wrote:
> On Thu, Feb 05, 2009 at 06:34:08PM -0800, jeffg wrote:
> > Could someone point me to the best functions to create a 3d (providing
> > x,y,z) force-directed / spring layout?  I'm trying to work though the
> > documentation but quick searches don't pull up much on 3d.  However,
> > I've read that NextworkX can do it... is this correct, if so.. some
> > examples would be great!  Thanks
>

> Some of the algorithms inhttps://networkx.lanl.gov/trac/browser/networkx/trunk/networkx/drawin...

[Aric Hagberg]

On Fri, Feb 06, 2009 at 09:56:17AM -0800, jeffg wrote:
>
> Thanks for the example.
> I'm getting an odd error though. This is the first time I've used
> NetworkX (and Python).
>
> When I issue the command
>
> >>> pos=networkx.spring_layout(G,dim=3)
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> AttributeError: 'module' object has no attribute 'spring_layout'
>
> So I then issued the command
>
> >>> from networkx.drawing.layout import *
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> File "C:\Python26\Lib\site-packages\networkx\drawing\layout.py",
> line 33, in <module>
> Raise ImportError, "numpy and/or Numeric can not be imported."
> ImportError: numpy and/or Numeric can not be imported.
>
> Thoughts?

Yes, you need the Python package "numpy" for the layout functions.
Depending on your operating system and setup there are a few different
ways to get it. See http://scipy.org/Download for some help.

Feel free to post back here if you get stuck on how to proceed.

Aric

[Dan Schult]

Looks like your installation didn't get the numpy or scipy modules.
Take a look at the "requirements" and "optional packages" sections of
http://networkx.lanl.gov/install.html

It might be easiest if you have room and bandwidth to install the
Enthought Python distribution which has most of these tools combined.


spring_layout should be enabled automatically with networkx when you
have numpy installed.
Dan

[jeffg]

Great - That worked! Had to downgrade to python 2.5.4 though...

Another question... :-) Any way to make the nodes case insensitive.
I want it to treat "Jeff" and "jeff" as the same object.
Also, noticed the spring_layout does not output the edges - any way to
tell it to output them as well. I was planning to just do a G.edges()
dump and then resolved the location, but figured I'd ask since I was
posting.

Thanks again,
- Jeff

On Feb 6, 1:11 pm, Dan Schult <dsch...@colgate.edu> wrote:
> Looks like your installation didn't get the numpy or scipy modules.

> Take a look at the "requirements" and "optional packages" sections ofhttp://networkx.lanl.gov/install.html

[jeffg]

I forgot to ask this as well... :-)
Is there any way to adjust the scale on the spring_layout? I'm
working with smaller factors.

[Aric Hagberg]

On Fri, Feb 06, 2009 at 01:13:32PM -0800, jeffg wrote:
>
> Great - That worked! Had to downgrade to python 2.5.4 though...
>
> Another question... :-) Any way to make the nodes case insensitive.
> I want it to treat "Jeff" and "jeff" as the same object.

Use the lower() sting method (probably when adding edges).

In [1]: s="Jeff"

In [2]: s.lower()
Out[2]: 'jeff'

> Also, noticed the spring_layout does not output the edges - any way to
> tell it to output them as well. I was planning to just do a G.edges()
> dump and then resolved the location, but figured I'd ask since I was
> posting.

One approach is to consider the edge as a line segment between
the two node positions. e.g. e=(u,v), epos=(pos[u],pos[v]).

Aric

[Aric Hagberg]

You can do it yourself:

In [23]: G=networkx.complete_graph(5)

In [24]: pos=networkx.spring_layout(G,dim=3)

In [25]: pos
Out[25]:
{0: array([ 0.23307185, 0.90192513, 0.59320213]),
1: array([ 0.32391126, 0.79692837, 0.96722863]),
2: array([ 0.63120853, 0.92457472, 0.6060652 ]),
3: array([ 0.35269727, 0.52267822, 0.5608564 ]),
4: array([ 0.63876546, 0.59418772, 0.82962413])}

In [26]: for p in pos:
pos[p]*=10.0
....:
....:

In [28]: pos
Out[28]:
{0: array([ 2.33071854, 9.01925133, 5.93202133]),
1: array([ 3.23911259, 7.96928369, 9.67228628]),
2: array([ 6.31208531, 9.24574724, 6.06065198]),
3: array([ 3.52697273, 5.22678218, 5.60856403]),
4: array([ 6.38765461, 5.94187721, 8.29624132])}

etc.

Aric

[jeffg]

Thanks for all the assistance.
Another question... on the spring layout, I'm trying to set the
"node_pos=". My intent is to set the first node (dim=3) at 0 0 0,
instead of the random 1x1. Any examples of the formatting of this
would be very helpful.

Thanks,

Jeff

[Aric Hagberg]

On Mon, Feb 09, 2009 at 12:27:01PM -0800, jeffg wrote:
>
> Thanks for all the assistance.
> Another question... on the spring layout, I'm trying to set the
> "node_pos=". My intent is to set the first node (dim=3) at 0 0 0,
> instead of the random 1x1. Any examples of the formatting of this
> would be very helpful.

You can set the initial positions for the spring layout

In [1]: import numpy

In [2]: import networkx as nx

In [3]: G=nx.complete_graph(4)

In [4]: pos=nx.random_layout(G,dim=3) # assign random positions

In [5]: pos
Out[5]:
{0: array([ 0.288445 , 0.91503167, 0.86394004]),
1: array([ 0.04104901, 0.13421718, 0.62346402]),
2: array([ 0.38496808, 0.76948755, 0.83526977]),
3: array([ 0.19058883, 0.61016701, 0.82655111])}

In [6]: pos[0]=numpy.array([0,0,0]) # assign node 0 position

In [7]: pos
Out[7]:
{0: array([0, 0, 0]),
1: array([ 0.04104901, 0.13421718, 0.62346402]),
2: array([ 0.38496808, 0.76948755, 0.83526977]),
3: array([ 0.19058883, 0.61016701, 0.82655111])}

Then use vpos=pos in spring_layout().

Currently there is no way to fix the position of nodes during
the layout process (but that could be added to the code).

Aric

[jeffg]

I'd like to assign 0,0,0 to the node with the most edges. Any good
way to find out which node has the most edges? Then I can hopefully
follow Aric's suggestion above, set it to zero, and plug it into the
spring graph to center the entire thing on 0,0,0.

- Jeff

[jeffg]

Here is what I ended up doing. Instead of getting the nodes to center
on 0 0 0, I centered my program to the nodes. This will attempt to
find the average center of the graph. Thought I would post in case
others might find it useful.

import numpy
slist = []
for spot in nodes:
slist.append(nodes[spot])
w=numpy.array(slist)
print w.mean(axis=0) # mean

w=numpy.array([w.min(axis=0),w.max(axis=0)])
print w.sum(axis=0)/2 # median

[jeffg]

Looks like Aric just added some "fixed" features to hold it at 0.0.
Nice!!! I test it out.
Now if we can just reduce the memory overhead. ;-) Great Work Aric!

[jeffg]

Wow, I just tested the new code and it looks like Aric solved the
memory issue for large graphs and performance is good. I still
haven't tried the "fixed" command yet (I'd like to try and figure
which node has the most edges and set it as fixed).

To give an idea as to the performance change...

16432 nodes, 17599 edges, 50 iterations
Prior to this week: 156 hours (approx 1 week)
As of change 1157: 1 hour (and didn't consume more than 40mb of
memory)

It is processor bound (and single threaded), so additional performance
might be achievable through multi-threading. Aric mentions multilevel
methods in the code as a way to further improve performance. I plan
to through a lot more data at this thing (500,000 - 1,000,000 -
perhaps more). So I'd appreciate any additional boost we can
muster. :-)

Fantastic work!