[SOLVED] ForceAtlas Automatic stabilization

Algorithms and parameters to put data in space
Post Reply
graphdrawer
Posts: 7
Joined: 04 Oct 2010 11:28

[SOLVED] ForceAtlas Automatic stabilization

Post by graphdrawer » 16 Jun 2011 14:40

Hi you all,

I'm looking at the code of ForceAtlas but I'm not able to figure out how the auto stabilization is done.
I mean, during the layout I see no flickering of nodes at all toward the end of the layout.

What is the mathematical formulation of the auto stabilization? A sort of better integration method for the forces acting of single nodes?

Are there some references?


Thanks!

User avatar
jacomyma
Gephi Core Developer
Posts: 61
Joined: 09 Feb 2010 23:23
Contact:

Re: Automatic stabilization

Post by jacomyma » 16 Jun 2011 15:28

Hi,

The autostab in the ForceAtlas is a "cooling" applied to nodes that swing. The more a node swings, the more it is "cooled".
Cooling is lowering how much displacement is caused by the forces (for this node).

It is a quite old mechanic that has been updated in ForceAtlas2.

Find below a sample of the ForceAtlas2 paper that I am currently writing. It might be useful to understand how it works.


III. Automatic "speed vs. precision" approximation

III. A. The issue of speed
Users have to deal with the "speed vs. precision" settings. The choice is supposed to depend on the size and properties of the graph, as well as the time available and the goal of the spatialization. In practical terms, it is possible to find the right speed by increasing it up to the moment problems appear. Unfortunately users don't do it, mostly because they misinterpret the effects of the precision drop. The technique that we implemented aims at doing it instead of the user.

In a classic force vector, increasing the speed makes the precision drop. The effect of the approximation is a swinging for some nodes and even for the whole graph. Nodes swing when they are close to their balancing position. The approximation prevents them from finding the right position.

[Illustration: Swinging.png]

Our technique is based on the minimization of this swinging. The user choses how much swinging he tolerates and the speed is constantly computed to fit this requirement.
The only setting managing speed is "Tolerance (speed)". In Gephi's implementation, we chose default values of 0.1 under 5000 nodes, 1 up to 50000 nodes and 10 above.


III. B. Adapting the local speed
We evaluate the symptom of the pathologic precision drop as the swinging value of a node. Intuitively, the swinging is the divergence, at each step, of the force applied to the node. The more the node is asked to change direction, the more it swings.

swinging(n) = |force(t)-force(t-1)|

A node that converges to its balancing position keeps its course. Its swinging is then null. Else the more it changes its course, the more it swings.

The more a node swings, the more chances we have to make it find its balancing position by slowering it. ForceAtlas2 applies a local speed to nodes, computed like this:

localSpeed(n) = c1 * globalSpeed / (1 + globalSpeed * sqrt(swinging(n)))
NB: c1 = 0.1 in Gephi's implementation

The more swinging, the more the node is lowered. If there is no swinging, the node moves at the global speed.
As a protection, we implemented an additional constraint that prevents the local speed from being too high, even in case of very high global speeds.

localSpeed(n) < c2 / |force(t)|
NB: c2 = 10 in Gephi's implementation


III. C. Adapting the global speed
At each step we compute two global values that we will use to get the global speed: the total swinging and the total effective traction.

The total swinging represents how much erratic movement there is in the movement of the graph. It is the sum of local swingings, weighted like our repulsion force (1+degree). The local swinging is the instant divergence of the force applied to the node.
totalSwinging = Sum(Nodes n, (1+degree(n)) * swinging(n))

The effective traction is the amount of "useful" force. It is the opposite of the swinging. It is defined as follow:
effectiveTraction(n) = |(force(t) + force(t-1))/2|

If a node keeps its course, the effective traction is the force applied to it. If it goes back to its previous position (a perfect swinging) then its effective traction is null.

The total effective traction is the weighted sum of effective traction of nodes:
totalEffectiveTraction = Sum(Nodes n, (1+degree(n)) * effectiveTraction(n))

The right global speed keeps the total swinging under a certain ratio of the total effective traction. It is defined as:

globalSpeed = toleranceToSwinging * totalEffectiveTraction / totalSwinging

The tolerance to swinging is set by the user.

NB: During our tests we observed that an excessive rise of the global speed could have a negative impact. That's why we limited the increase of global speed to 50% (compared to last step).
Attachments
Swinging.png

graphdrawer
Posts: 7
Joined: 04 Oct 2010 11:28

Re: Automatic stabilization

Post by graphdrawer » 21 Jun 2011 10:03

Many thanks for your detailed answer,

a last question: what is your stopping condition? I mean, when do you believe the layout is finished?
This could be implemented using an optimality measure, like a sum of squared delta positions:

optimality = \sum_{n=1}^{Nodes} dx_i^2 + dy_i^2

where dx is the difference (x(t)-x(t-1)) and dy=(y(t)-y(t-1))
This measure, from one side is simply applicable to many kind of graphs, but on the other side it doesn't prevent a potential swinging in the last phase of layout.

How about implement a stopping condition using the so called totalEffectiveTraction?

User avatar
jacomyma
Gephi Core Developer
Posts: 61
Joined: 09 Feb 2010 23:23
Contact:

Re: Automatic stabilization

Post by jacomyma » 21 Jun 2011 11:09

I made the design choice to let the user decide if he is satisfied.
Actually, there could be different reasons to stop the graph. It is a question of evaluating the quality of the spatialization. Your optimality is one option amongst many, I think.
This is a good question.

User avatar
mbastian
Gephi Architect
Posts: 728
Joined: 10 Dec 2009 10:11
Location: San Francisco, CA

Re: Automatic stabilization

Post by mbastian » 22 Jun 2011 02:17

It would be nice to have such an option, so the layout could be used in Toolkit applications.

User avatar
jacomyma
Gephi Core Developer
Posts: 61
Joined: 09 Feb 2010 23:23
Contact:

Re: Automatic stabilization

Post by jacomyma » 22 Jun 2011 05:45

To make available the algo in the toolkit, the straightforward solution is to stop after a certain count of steps. I'll probably do that first, since it's trivial, and useful for other purposes.

Post Reply