Force Directed Graph and simulation parameters

[Dave]

Hi,

I am rendering a nice FDG with up to 200 nodes. I am scaling node
sizes and line widths using some power laws, and all is well.

I am now getting some complaints about the speed with which the graph
renders, in that it takes a long time to settle into a steady state.

I would like to know some additional information about the FDG
concerning how to tweak the render times by changing the parameters
governing the graph render. Without me being an expert in the
underlying algorithm, could someone kindly steer me towards how to
tweak some of the FDG render process so I can see how it changes?

I realize that a faster render will perhaps affect the layout
negatively, but it would be nice to compare a maximum time to render
VS. a faster render, and comparing the graph incrementally at each
point.

Also, I am wondering, is there a callback that can be setup for a
graph that triggers a "render complete" signal?

Thanks!!

[Mike Bostock]

> Without me being an expert in the underlying algorithm, could
> someone kindly steer me towards how to tweak some of the
> FDG render process so I can see how it changes?

I would start here, if you haven't found it already:

http://vis.stanford.edu/protovis/jsdoc/symbols/pv.Layout.Force.html

If you want the simulation to converge more quickly, that generally
means that you want to bump up the forces. So you could try decreasing
the charge constant from the default -40 to -80, and increasing the
spring constant from .1 to .5.

The real problem with increasing these values is that numerical
instability becomes more likely. You see this when the graph starts
oscillating back and forth, with forces getting stronger and stronger
until everything devolves to NaN. There's a little more information
about that here:

http://en.wikipedia.org/wiki/Numerical_ordinary_differential_equations

Protovis uses position Verlet integration:

http://en.wikipedia.org/wiki/Verlet_integration

You could also try implementing some sliders with jQuery (see the
examples directory in the git repo), and tweak the constants
interactively to see what works best. The best constants are usually
dependent on the size and connectivity of the graph.

There are likely some things we could do to improve the stability of
the simulation, as well as the quality of the graph layout. For
example, we currently normalize spring forces based on the sqrt of the
link degree, so that springs connected to nodes with lots of edges are
weaker. This way, the total force on heavily-connected nodes doesn't
balloon out of control and introduce instability.

One of the tricks I was playing with recently was to scale the spring
force proportional to the link value; this way, the link value can
affect the layout and not just the visual appearance.

> Also, I am wondering, is there a callback that can be setup for a
> graph that triggers a "render complete" signal?

There's no callback at the moment. You can tell the layout to run a
fixed number of iterations if you just want it to be static. However,
for interactive layouts, the simulation restarts when you drag a node
(or add new nodes to the layout). So it's never really "complete".

Mike

[Dave]

Hi Mike,

Thanks for the details. I rendered my graph with some changes to the
springLength, iterations, springDamping, etc.. and was pleased to see
that there is indeed some control over the render.

I am well versed in using Javascript slider widgets and was
wondering... if I render some sliders to change the factors affecting
the graph... I would listen for changes to a slider, and then call
refresh on the graph, but how to inject the changes? I am not sure but
I suppose I could just get a handle on the graph itself, and then the
layout, and overwrite the attributes of interest?

Could you elaborate just a little on the pattern to do this "live"
tweaking... would be awesome!!

Thanks!!

Dave

[Dave]

I see the slider demo on github.. will try and see if that can help me
to tweak the graphs.. .


Thanks

[William Strathearn]

The force-directed layout works quite well for a particular flavor of dense interconnected networks.  Certain other networks that have a star topology before growing cross-connections are impossible to stabilize in this layout.  There are plenty of networks for which no matter of parameter tweaking will keep the nodes from stabilizing at the far corners of the grid.  

I wonder if it would be possible to adapt the pure-tree Node-Link Dendrogram and Indented layouts to operate on sparse graphs.   

[William Strathearn]

I've revisited my edge weights and found that they were the primary reason for my sparse graphs going atomic.  With edge weights on the order of hundres rather than tens or ones seeme to keep everything together, with all the default spring and charge parameters.

[Jamie Love]

great to know, thanks!

On Thu, Oct 28, 2010 at 11:34 AM, William Strathearn <bi...@google.com> wrote:

I've revisited my edge weights and found that they were the primary reason for my sparse graphs going atomic.  With edge weights on the order of hundres rather than tens or ones seeme to keep everything together, with all the default spring and charge parameters.

--
You received this message because you are subscribed to the Google Groups "protovis" group.
To post to this group, send email to prot...@googlegroups.com.
To unsubscribe from this group, send email to protovis+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/protovis?hl=en.

--
Jamie Love
Looking for custom software development? Contact us at www.nsquaredsoftware.com.

[guaz wk]

can show us your sample code?

Best Regards,
Guaz Wei Kiat

[Bill Strathearn]

Sure, here is the final math that seemed to have good results with the types of large and small networks and trees that I tested with.  This code scales the graph to roughly fit the available width and height.  

I highlighted the portions that differed from the example force-directed graph on the protovis site.

  var w = w = document.body.clientWidth;

  var h = document.body.clientHeight;

  var colors = pv.Colors.category19();

  var vis = new pv.Panel()

      .canvas('your-div-id')

      .width(w)

      .height(h)

      .fillStyle("white")

      .event("mousedown", pv.Behavior.pan())

      .event("mousewheel", pv.Behavior.zoom());

  var nodes = getPvNodes();

  var nodeScale = Math.max(2, ((w * h) / nodes.length) * 0.02);

  var force = vis.add(pv.Layout.Force)

      .nodes(nodes)

      .links(getPvLinks(nodeScale))

      .dragConstant(0.05)

      .springLength(Math.max(15, Math.pow(nodeScale, 0.75)))

  force.link.add(pv.Line);

  force.node.add(pv.Dot)

      .size(function(d) {

        return Math.pow(d.linkDegree, 0.75) + nodeScale;

      })

      .fillStyle(function(d) {

        return d.fix ? "brown" : colors(d.group);

      })

      .strokeStyle(function() {

        return this.fillStyle().darker();

      })

      .lineWidth(1)

      .title(function(d) {

        return d.nodeName

      })

      .event("mousedown", pv.Behavior.drag())

      .event("drag", force);

  try {

    vis.render();

  } catch (e) {

    alert(e);

  }

In getPvLinks, there is some complexity in shaping the subgraph structure I have, into vertex and edge arrays, but the edge weights have the value: 

Math.max(nodeScale * .5, Math.sqrt(v.outDegree, 0.75)) where v.outDegree is the total number of edges that lead away from the vertex that the current edge points away from.

Bill

[guaz wk]

Hi Bill,

thanks for your sample. But I got the error on getPvNodes() is not defined.

Sorry, if my question about silly. Because I am new in javascript and protovis.

[robert schaefer]

Mike,

Is it possible to have the springconstant be a function of link value
by simply putting a function into the .springconstant() like so:

.springconstant(function() *some function*) ?

or does this functionality have to be created deeper down?

Thanks

Rob

On Sep 8, 11:46 am, Mike Bostock <mbost...@cs.stanford.edu> wrote:

>
> One of the tricks I was playing with recently was to scale the spring
> force proportional to the link value; this way, the link value can
> affect the layout and not just the visual appearance.
>

> Mike

[Mike Bostock]

> Is it possible to have the springconstant be a function of link value
> by simply putting a function into the .springconstant() like so:

Unfortunately, that won't work. You can specify the springConstant as
a function, but that's only useful if you have multiple force-directed
layouts (in conjunction with panel replication), and you want to use
different spring constants for different graphs.

Spring forces are normalized by the maximum of the connected node's
link degree; see SpringForce.js for details. If you want to change
this behavior, you could either hack SpringForce.js and rebuild
protovis.js, or use pv.Simulation directly with your own pv.Force
implementation.

I wish it were easier to customize the internals of pv.Layout.Force,
but it's difficult to plug that into the standard mark property
evaluation mechanism.

Mike

[robert schaefer]

Thanks Mike!

This might be my first attempt at hacking the underlying code, but I'm
up for a challenge.

I'll let you know it works out!

Rob