Using Simulation for Graph Visualization

[Sane]

Firstly, let me excuse myself for not knowing the most appropriate location to post this question. This is a question pertaining to Graph Theory, but the heart of the application is intended to be driven by the math and/or simulation of classical physics.

At work I am currently attempting to visualize a very large graph. The graph is initially too squished together and is altogether incomprehensible when drawn on screen. My plan is to simulate a physical scenario involving the graph, in which the end result of the system should yield a more "eye-pleasing" arrangement of vertices (nodes or points) and edges (a link between two nodes). The details are as follows:

I have a very specific graph that, due to its size, requires visualization of overall structure. I cannot use any out-of-the-box graph visualization tools because the graph is simply too big, the goal is to get an idea of how the general layout looks, and I want to have fine-grain control over aspects such as the colour and the y-coordinates. This is going to fit into one image (maybe 5,000x5,000) so there won't even be enough room to have nodes larger than a few pixels. Point being: I doubt any free applications out there can satisfy my needs.

The graph is special because I've arranged it in the following way:

There are approximately 500,000 vertices. Every vertex already has a desired y-coordinate that should not change. There are around 500 "rows" (one for each y-coordinate), and each row contains anywhere between 1 and 100,000 nodes. Edges can only exist between vertices on different rows (edges will never join vertices on the same row). Finally, the graph is sparse with only around 5,000,000 edges.

Every vertex also has a desired colour/shape. The x-coordinates are currently unknown.

I need a way to determine the x-coordinate of each and every node, such that vertices on the same row do not crowd each other, and the geometrical/physical length of each edge is minimized. Clearly, some more precise objective function will be necessary, but this description should suffice for the planning stages. In the end, plotting the (x,y,colour) of each node (and potentially joining some of the more major nodes with a transparent edge) should give a visual representation of how the graph is structured.

My plan is to motivate the algorithm by the physics required to simulate an interaction between "balls" joined by elastic "strings". Balls will gravitationally repel all other balls on the same row, and strings will have tension and elastic energy that try to bring the two ends closer together (and could potentially break if need be).

The physics would be simulated in an iterative fashion, where the system begins with some amount of potential energy, and each step of the simulation assigns new x-coordinates to each ball, based on the x-components of all surrounding forces, to put the system into a more "stable" condition. The iterations would continue until the changes become minimal, converge, or after a fixed amount of time.

Any suggestions or pointers as to the kind of equations or algorithms that could be used here? Thank you very much!

 

[Sane]

I have been thinking about this for quite a while, and thought of the following simulation:

for node in graph:
    node.x = <arbitrary value near 0> must be distinct per row
    node.velocity = 0

for number of STEPS:
    for node in graph:
        node.accel = 0
        for node's row: 
            node.accel += G/r^2
        for node.neighbours: 
            node.accel += K*x/sqrt(x^2 + y^2)
        node.velocity += node.accel * TIME

    for node in graph:
        node.x += node.velocity * TIME

The first equation is Attraction[/url] (where r is the distance in x co-ordinates between the two nodes -- note: needs a direction added), the second equation is Law[/url] using the x-distance between the nodes as the stretch factor normalized by their euclidean distance, and G/K/TIME/STEPS are constants to play with. Mass is implicitly 1 throughout to simplify equations and set force equal to acceleration.

This method seems appealing. However, there is always the chance that the system might stand still, oscillate, diverge, or generally do something stupid. I can try it out tomorrow, but anyone want to add their thoughts or point out some potential short-comings or improvements?