2

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

Giuseppe Di Federico
  • 3,501
  • 4
  • 20
  • 19
  • You should do something about that 5-million-node cluster, before even attempting to draw it. You will have a *very* hard time finding software that can draw over a million nodes or so... – thkala Jul 02 '11 at 19:16
  • Can you clarify what you mean when you say you don't care about the nodes and connections, only the clusters? Do you need to draw each node and edge? – Szabolcs Jul 03 '11 at 07:52
  • It doesen't matter if the nodes connection are not clear or are not visible at all. It matters just the clusters – Giuseppe Di Federico Jul 03 '11 at 09:03
  • @Giuseppe, it's still not totally clear what you mean. Are there any connections between clusters in your case? Why don't you just collapse clusters into a single node then, and visualize the connections between those? – Szabolcs Jul 03 '11 at 10:47
  • Obviously The cluster are disconnected. I don't collapse the cluster into single node, because I would like to visualize the cluster with high nodes inside bigger than other with less nodes inside. What I meant before is that I don't pretend to visualize the connection of the nodes, and neither the nodes that are so much, it would be enough to highlight the weight differences between the clusters – Giuseppe Di Federico Jul 03 '11 at 11:44

4 Answers4

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: 3 graphs

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.

Community
  • 1
  • 1
DavidC
  • 3,056
  • 1
  • 20
  • 30
  • 1
    Printing a 5-million-node graph on paper is easy: Just get a brush and paint the whole page black... – thkala Jul 02 '11 at 19:32
  • Yes, no one can claim you missed any nodes! – DavidC Jul 02 '11 at 19:40
  • @David I didn't have very good experiences trying to use Mathematica for very large graphs, especially with visualizing. Up to a certain size it's great, but after that it gets really slow. Also, when visualizing very large graphs with Mathematica 8, the slowest part might not be computing the layout, but actually rendering it on screen. – Szabolcs Jul 03 '11 at 07:50
  • @Szabolcs. Thanks for your notes. I've only worked with small (nVertices < 1000) graphs in MMA. – DavidC Jul 03 '11 at 07:57
  • @David Still, what we already have in 8 is very useful, if still a bit buggy ... I'm very much looking forward to improvements in the next release! – Szabolcs Jul 03 '11 at 07:59
  • @David @thkala I'm consciuous about the difficult to draw such graph, and if I want to be precise it would result a black page. For this reason I told that it's just a matter of clusters, I don't care about the nodes and their connections, for example If I can draw a cluster big in scale as the nodes it contains, it would be enough. Do you have any Idea ? – Giuseppe Di Federico Jul 03 '11 at 09:05
2

Try AT&T's graphviz.

duffymo
  • 305,152
  • 44
  • 369
  • 561
  • It doesn't fit, what I need it's a clustered graph. It's enough to draw clusters where their size is related to the amount of node they got inside. I need an automatic program that do it. – Giuseppe Di Federico Jul 03 '11 at 14:52
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.

mliebelt
  • 15,345
  • 7
  • 55
  • 92
  • Thank you milebelt, you're answer is a good picture of my problem. In fact, the time helped me to understand that such graph it's not drawable and if I want to do it I have to reformulate the problem in some way. At the end, I decided to report the output that I showed on my question (there are x cluster composed by bla bla bla) instead that graphic graph (forgive the pun). – Giuseppe Di Federico Jul 11 '11 at 07:56
0

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.

Damon
  • 67,688
  • 20
  • 135
  • 185
  • It still doesn't fit my needs. I give up, it's not possible to draw a graph like that. I also have another problem that consist in how to represent such graph on A4 paper. Even if I concentrate just on clusters ignoring the node connections it would be too much as well. – Giuseppe Di Federico Jul 06 '11 at 10:22