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).
Statistics:Posted by jacomyma — 16 Jun 2011 15:28
]]>