Clustered Graphs Visualization Techniques

Question

I need to visualize a relatively large graph (6K nodes, 8K edges) that has the following properties:

• Distinct Clusters. Approximately 50-100 Nodes per cluster and moderate interconnectivity at the cluster level
• Minimal (5-10 inter-cluster edges per cluster) interconnectivity between clusters

Let global edge overlap = The edge overlaps caused by directly visualizing a graph of Clusters = {A, B, C, D, E}, Edges = {Pentagram of those clusters, which is non-planar by the way and will definitely generate edge overlap if you draw it out directly}

Let Local Edge Overlap = the above but { A, B, C, D, E } are just nodes.

I need to visualize graphs with the above in a way that satisfies the following requirements

• No global edge overlap (i.e. edge overlaps caused by inter-cluster properties is not okay)
• Local edge overlap within a cluster is fine

Anyone have thoughts on how to best visualize a graph with the requirements above?

One solution I've come up with to deal with the global edge overlap is to make sure a cluster A can only have a max of 1 direct edge to another cluster (B) during visualization. Any additional inter-cluster edges between cluster A -> C, A -> D, ... are disconnected and additional node/edges A -> A_C, C -> C_A, A -> A_D, D -> D_A... are created.

Anyone have any thoughts?

Answer 1

Prefuse has some good graph drawing link text algorithms built in and it seems to handle fairly large graphs relatively well. You might try Flow Map Layout which is built on top of Prefuse.

Answer 2

I haven't seen too many graph visualization tools that support separating clusters within a graph visually. One option might be to take a look at WilmaScope. It looks to have some support for cluster based layouts.

Answer 3

Given your objectives, I think that the Fruchterman-Reingold algorithm does a pretty decent job of preventing edge overlap. See for example this screenshot of a network consisting of multiple components drawn using the Fruchterman-Reingold algorithm. IGraph has built-in support for this algorithm (as does Networkx I believe) and is really fast.

Answer 4

Organic layout manages fairly well clustered graphs in yFiles framework. Try first in yEd to see if it does what needed. It is probably reasonable to use nested graphs alias groups for each cluster. Organic layout has feature called Group Layout Policy which can be used if layout needs to be done using different principles for inter-cluster and intra-cluster edges, with incremental layouting. With some effort, one can translate graph into GraphML to avoid manual work.

Answer 5

There is a program built on top of Prefuse called SocialAction. You have to request the code from the author, but it does a lot of statistical analysis on the graph for you, such as identifying subgraphs. I've used it on a graph with more than 18,000 nodes, and although it is very slow at that scale it still works.

Answer 6

Although it may be silly to ask at this point, had you tried out http://www.graphviz.org/ ?