# Dynamic Graph visualization

I'm working on a C++ library that will be used to construct and study certain graphs (as in a set of connected vertices, not a function plot). These graphs will be dynamic in nature (and can potentially be very large) and I'm looking for ways to visualize them.

I looked at a few solutions such as Gephi which can visualize dynamic graphs, but then decided that this should be something that Mathematica would do well.

My C++ library keeps track of a 'lifetime' for each vertex and edge and I can output the graph data any way I need to.

Although I've visualized a lot of graphs in Mathematica with GraphPlot and GraphPlot3D I'm not sure what's the best way to visualize a dynamic graph?

I've used Dynamic and Manipulate extensively and I've been able to use Manipulate to draw a series of successive 'snapshots' of a graph at each time step. The problem with this approach is that you're redrawing the entire graph each time even though only one vertex or edge has changed. Also when you redraw the entire graph there's no guarantee that the vertices will be put in similar places, so adding one edge causes the picture to totally change. This kills the ability to animate the changing graph.

What seems to be needed is the ability to change the graph slightly and then locally recompute the graph drawing forces without redrawing the graph from scratch. Is this possible? Something like a hypothetical GraphPlotDynamic[].

Edit

Here is a contrived example showing the problem. The format for each edge is.

{source, target, begin, end}


This creates the graph connectivity.

dynamicGraph =
{{0, 1, 0, 20}, {1, 2, 1, Infinity}, {2, 3, 2, 21}, {3, 4, 3, 22},
{4, 5, 4, Infinity}, {5, 6, 5, Infinity}, {6, 7, 6, 26}, {7, 8, 7, 25},
{8, 9, 8, Infinity}, {9, 10, 9, 24}, {0, 6, 10, 27}, {1, 6, 11, Infinity},
{1, 5, 12, Infinity}, {2, 5, 13, Infinity}, {2, 4, 14, Infinity},
{6, 8, 15, Infinity}, {5, 8, 16, Infinity}, {5, 9, 17, Infinity},
{4, 9, 18, Infinity}, {4, 10, 19, 23}};


Now the graph is rendered with GraphPlot. The edges are selected based on whether t is within the edge's lifetime.

Manipulate[
GraphPlot[#1 -> #2 & @@@ Select[dynamicGraph, #[[3]] <= t <= #[[4]] &],
VertexRenderingFunction -> (Text[#2, #1] &)], {t, 0, 31, 1}]


This graph has a relatively natural progression of adding nodes in a line then connecting the line by folding it back on itself twice. Then all the outside edges are deleted and you are left with hexagon with all vertices connected to one vertex at the center. But when clicking through the Manipulate the graph jumps around at each step so it's hard to keep track of what is being added and taken away.

Edit

Here is an example video of what I'm talking about. This is from Ubigraph and does more than what I'm asking for since it does fancy camera angles and rotations as the graph is being constructed. But what's important is that as the vertices and edges are being added the force directed algorithm is continuously running so the graph is constantly updated.

http://ubietylab.net/ubigraph/content/Demos/Animation.html

-
I added more details. –  Sean Lynch Dec 21 '12 at 19:16
I found Gephi to be somewhat unstable. It crashed a few times and wouldn't work with a dynamic graph. Also, the c++ libgexf for graph IO is incomplete and doesn't support dynamic graphs. So since I would have to fix that anyway to get it to work, I figured I'd just try to stick with Mathematica because I know it. –  Sean Lynch Dec 21 '12 at 19:19
@Nasser I think what he wants is a way to modify a graph locally and update it without mma attempting to recompute the orientation/layout and rendering it again. This process can be time consuming for larger graphs and if you're doing some minor modifications at each step, it can get annoying. As an example, consider g = CirculantGraph[100, Union@RandomInteger[{1, 100}, {10}]]; With[{edges = EdgeList[g]}, Manipulate[ HighlightGraph[EdgeDelete[g, RandomSample[edges, 50]], PathGraph@FindShortestPath[g, 2, i]], {i, 1, 100, 1}]] (set it to autorun; increase the size to see the slowdown) –  rm -rf Dec 21 '12 at 22:15
Having looked through the options in the GraphPlot documentation, my guess is that what you want is only possible if you write your own force-directed graph layout routine and animate the vertices yourself. In my comments below I was just trying to suggest how to get as close as possible to a nice result with only the existing GraphPlot functionality. –  Rahul Dec 23 '12 at 3:33

## 1 Answer

Not quite sure how this could handle with very large amounts of data, but maybe this is something of use.

The following code I think could easily be adapted to take an input stream efficiently. Essentially I predesignate each vertices position using RandomReal, but I bet there's a way to make things look less erratic despite an arbitrary amount of vertices being allowed.

Options[GraphPlotDynamic] = {VertexRenderingFunction -> (Point[#1] &)};

GraphPlotDynamic[lis:{{_, _, _, _}..}, OptionsPattern[]] :=
Module[{posHash, chosenEdges, chosenVerts, vRender},

vRender = OptionValue[VertexRenderingFunction];

Set[posHash[#], RandomReal[{0, 1}, 2]] & /@ Range[0, Length[lis] - 1];
posHash[{args__}] := posHash /@ {args};

Manipulate[
chosenEdges = Select[dynamicGraph, #[[3]] <= t <= #[[4]] &][[All, 1 ;; 2]];
chosenVerts = vRender[posHash[#], #] & /@ Union[Flatten[chosenEdges]];

Graphics[{
Red, Line[posHash[##]] & /@ chosenEdges,
Black, chosenVerts
}, PlotRange -> {{0, 1}, {0, 1}}],

{t, 0, 31, 1}]

]


And here's your example (t=24, t=25):

GraphPlotDynamic[dynamicGraph, VertexRenderingFunction -> (Style[Text[#2, #1], Large] &)]


-
This is nice. The essential feature however is the placement of the vertices. When drawing a graph, some type of force directed algorithm is used to place the vertices. So every time a new vertex is added the placement would shift slightly. The key is to make it so that the placement doesn't shift wildly that you loose the understanding of the pattern of connections. –  Sean Lynch Dec 22 '12 at 14:44
Did you run my code? As you move the slider, the placement of the vertices remained the same. –  Chip Hurst Dec 22 '12 at 19:09
@Sean, RiemannZeta: What if you set the precomputed vertex placement by doing a GraphPlot with all the input edges enabled regardless of lifetime? Then, granted the layout won't adjust itself as the structure changes over time, but it would still reflect the "average" structure of the graph to some extent. –  Rahul Dec 23 '12 at 0:19
@RiemannZeta: My comment wasn't as clear as I had hoped. It is a cool piece of code but it's not correct to just put the vertices in a spot and leave them there. Their placement should be based on a force directed algorithm. –  Sean Lynch Dec 23 '12 at 0:52
@RahulNarain: Computing the positions at first with a force directed algorithm is better. But it is not correct to say that this would reflect the average. Yes in some cases this is correct but that is only if the graph hasn't changed much. If it has changed a lot then this wouldn't be correct at all. And what about the case where you start with only one vertex and then add vertices and edges. Then the initial placement is irrelevant. What is needed is for the force directed algorithm to be running while vertices and edges are being added. –  Sean Lynch Dec 23 '12 at 0:56