Graph drawing software

Question

I need to draw a graph composed by 1876 clusters organized in the following manner:

962 clusters composed by 1 node
651 clusters composed by 2 nodes
144 clusters composed by 3 nodes
52  clusters composed by  4 nodes
24  clusters composed by  5 nodes
8   clusters composed by 6 nodes
8 clusters composed by 7 nodes
2 clusters composed by 8 nodes
4 clusters composed by 9 nodes
3 clusters composed by 10 nodes
1 cluster composed by  11 nodes
1 cluster composed by  12 nodes
4 clusters composed by 13 nodes
1 cluster composed by  16 nodes
1 cluster composed by  21 nodes
1 cluster composed by  22 nodes
1 cluster composed by  24 nodes
1 cluster composed by  25 nodes
1 cluster composed by  26 nodes
1 cluster composed by  29 nodes
2 clusters composed by 31 nodes
1 cluster composed by  43 nodes
1 cluster composed by  65 nodes
1 cluster composed by  4843953 nodes

I tried several software included pajek, SocNet but they seems to be more node centered (they let you perform statistics and some advanced operations on the nodes). Instead, I don't care about the node itself and I neither care about their connections. I just want to show such clusters with the nodes inside.
Does anyone know any software that should help me?

P.S That is the livejournal's graph

Answer 1

I don't think that you will get a reasonable answer to your question, but I want to provide my 2 cents here:

• Have a look at examples how to draw graphs of graphs, and reformulate your problem then.
• How should one cluster visualized? Most of the clusters are easy to visualize, but the one with 4.843.953 nodes is a killer. I suspect that it won't be suitable to visualize that cluster together with the others ...
• The best what I have seen up to now is the Software from TowSawyer to visualize graphs. But the software comes with a high price tag, perhaps it could help to get a clear idea how to visualize.

When you have found answers and details to the remarks above, I think there will be a way to visualize them accordingly.

Answer 2

Tulip, which comes as package with every major Linux distro (but apparently is also available for Windows) is said to be "capable of managing graphs with up to 500,000 nodes and edges on relatively modest hardware (eg. 600MHz Pentium III, 256MB RAM)".

That sounds just like what you want.

Answer 3

In principle, Mathematica 8 should be able to handle your problem with its new Graph object. I say, "in principle", because I have trouble imagining how a cluster of almost 5 million nodes (or vertices) will look when printed on screen or on paper. It will be crucial that you choose a suitable GraphLayout, as this comparison from Hu shows:

They are 3 depictions of the same graph (936 vertices), with the poorest rendering (of course) on the left. The article contains a rendering of a graph with 225k vertices that has a somewhat discernible structure.

Anyway, it can handle input in the form of adjacency matrix or list of edges, among others. Edges may be directed or not. You can show and label all or some or none of the vertices and edges. You can also remove the clusters (GraphComponents) and display them alone or in combination. It also gives you various GraphLayout options: CircularEmbedding, SpiralEmbedding, HighDimensionalEmbedding, LargeNetwork, etc. There are a variety of GraphStyles.

There is a command called NeighborhoodGraph that you may find useful for that huge cluster. Neighborhood[g,v,n] generates a subgraph of all nodes within n steps from vertex v. You can also simplify things by asking for a Subgraph with a predetermined list of edges, vertices or both.

Beware that some of the Graph documentation will refer to Combinatorica, which though excellent and useful for many purposes, does not render graphs with as much precision, in my view, as the version 8 Graph object will.

Some of the issues regarding graph layout for huge graphs are discussed here. There is also a SO discussion about plotting large graphs in which various software solutions are compared.

Answer 4

Try AT&T's graphviz.