5

I have the following graph graph:

As you can see, there are two natural clusters. I would like to figure out a way to separate these clusters into two graphs.

The key step, of course, is to compute the right split. I would like to insert two nodes n1 & n2, link them e(n1, n2), and move them around, minimizing the number of edge crossings (of course fixing all nodes/edges exactly where they are).

Can anyone offer any help here? I don't think graphviz has anything that enables me to do it.

7
  • 9
    +1 just for the impressive image :) Commented Nov 3, 2012 at 1:11
  • 1. Get Transparency International data for 88 countries; 2. Create distance matrix between countries; create full graph. 3. One planet, two different worlds.
    – linhares
    Commented Nov 3, 2012 at 1:23
  • Just to be clear...do you already know the clustering of the graph and your question is how to get graphviz to layout the graph more cleanly, or is your first problem to (algorithmically) find the clustering and then assume that graphviz will produce a cleaner layout? Commented Nov 3, 2012 at 6:42
  • I want to automate the findings of these clusters, and look inside each one recursively. Problem is graphviz doesn't offer me a way to peek into weighted edge crossings.
    – linhares
    Commented Nov 3, 2012 at 10:11
  • I read your question several times, but I don't understand what you're lookging for: Do you want two separate graphs? Or one graph with two clusters? Why exactly do you want to new nodes? And if you're fixing nodes/edges where they are right now - what is supposed to change?
    – marapet
    Commented Nov 3, 2012 at 11:01

1 Answer 1

2

I think you mingle two different tasks here: the one is Analysis of a graph, the other one is Visualization of the same.

Graphviz, as the name suggests, is a tool for visualization of graphs. Visualization can take many forms, typically one tries to "make it look good" by having those nodes close to each other that are connected, thus reducing the visual edge lengths. One can utilize some spring- or gravitational model to calculate optimal positions for all nodes. Other options include circular- or shell-layouts.

A certain visualization should not be the basis for the analysis of a graph. Graph properties, like average shortest path length or clustering coefficient, are independent of any visualization.

You say you want to "minimize the number of edge crossings". The number of edge crossings is a property of your visualization, not of your graph! It probably changes each time you let graphviz calculate the layout, even if the graph is unchanged. Who says that 2d is the only possible representation of your graph? Add just one dimension, and you won't have any edge crossing.

I'd recommend to concentrate on graph analysis. I don't know if you're aware of NetworkX. They have dozens of Algorithms to analyze your graph. Maybe the clustering and clique sections are of interest to you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.