ForceAtlas publication

[seinecle]

By the way,

I finally got the principle of the "distributed attraction" feature. The possibility to twist the mechanism of the layout, to make it depend on the topology of the network, opens many possibilities. For example, does it mean that, following the same principle, it would be possible to scale the attractive or repulsive forces according to attributes of the nodes?
Say, I have an attribute ranging from 1 to 10: nodes with an attribute value of 10 would be 10 times more attractive than nodes with att value of 1.
Again, following this logic, node's dynamic attributes (say, their date of start and date of end) could be a factor playing a role in the determination of attractive and repulsive forces - great possibilites I guess. Like, younger nodes in the network would have a lesser attraction force, which would scale up to the mean with time passing.
All that makes me cringe because I can't code in Java! Would love to try all those ideas!! ))

[jacomyma]

Yes, these are good ideas. Not so hard to implement in a layout.

I'm astonished by the fact that, what you like in ForceAtlas, is just that it is a clean and smooth layout. Sure, the settings of the forces make the graph good-looking. But the point isn't that it has more than other layouts. You like that fact that it has less. This is a very good point to me. It means that even if sometimes you need something rough and powerful like OpenOrd, there are times where you need something simple. And the simpler it is, the better you can understand and interpret data.

I'm gonna dig in this direction.

[martin.pernollet]

You'll at least tell me what interests you to read

I'm especially interested in understanding the details about the forces the algorithm relies on. We can read it in the code, but it's nicer on a paper
Sometime I'm thinking about visualizing the forces, at least repulsion using for example a 3d surf showing the energy as z on point x,y. I was also thinking about drawing all force vectors applying to a node at the node position. I think this can help to debug a layout on which one adds other forces (e.g. bounding forces http://forum.gephi.org/viewtopic.php?f=26&t=943). If you have any other idea for a force viewer, just tell me!

Everybody is enjoined to review the work in progress.

With pleasure!

[jacomyma]

Here's a draft. I'll be off during the next 2 weeks, so don't worry if I don't post here. I hope you'll find here some useful information, even if it is not very clear for the moment. Feel free to comment and criticize this draft. Tell what you would develop, unanswered questions, what you dislike and so on...

Draft paper about ForceAtlas


I. Introduction
ForceAtlas is a force vector proposed in the Gephi software. It is appreciated for its simplicity and readibility, despite being limited to relatively small graphs.
This paper explains how it works and why such a simple algorithm is still useful to users, particularly researchers in humanities.


II. Anatomy of ForceAtlas
ForceAtlas is a force directed layout: it simulates a physical system with custom forces.
At each step forces are calculated, and a displacement of each node is given by the force and a "speed vs. precision" approximation.

II. A. Energy Model
The (attraction,repulsion)-model of ForceAtlas (1,-1), as formalised by A. Noack, is between Früchterman Rheingold (2,-1) and LinLog (0,-1).

II. B. Repulsion by degree
The repulsion between two nodes is proportional to the produce of the two degrees.
It makes the graph clearer. We can see its effect on "star" structures.
This is almost the same thing as Noack's "edge-repulsion", even if it is not how we understand this feature.
It also causes instability and side effects (with gravitation)

II. C. The formulas
attraction(n1,n2) = attraction_factor * distance(n1,n2)
repulsion(n1,n2) = repulsion_factor * (1+degree(n1)) * (1+degree(n2)) / distance(n1,n2)

II. D. Options
- Settled nodes: The force takes in account the nodes that are manually settled by the user.
- Gravity: There is also a gravity that prevents nodes from drifting away: gravity(n) = gravity_factor * distance(n)
- Weight: if edges have a weight, it is used as a factor for the attraction
- "DistributedAttracion" differenciates hubs from authorities by dividing the attraction of each edge by (1+degree(node_from)). The hub attract less and appear more peripheric than authorities.
- "AdjustBySize" prevents nodes from overlapping: nodes that overlap are repulsed by a constant force.

II. E. Optimizations
There is no sophisticated optimization such as Barnes Hut or so. Thus the algorithm is exponentially slow as the size of the graph rises (n² complexity) and is unable to deal with big graphs.
But the advantage is that it converges to a very low energy (good quality).
Two basic optimizations allow to manage convergence speed:
- the essential "speed vs. quality" application of the force, including the necessary max_displacement protection
- a dynamic freezing of nodes that works this way: nodes "freeze" when the force applying to them changes quickly. "frozen" nodes have a malus for displacement. This prevents nodes from swinging around their balance position.


III. Spatialization quality
Here we compare ForceAtlas to other layouts such as OpenOrd, Yifan Hu and Früchtermann Rheingold, on different graphs.
We do not test performance, but quality, meaning: interpretability.

III.1. Are close nodes more connected ?
III.2. Are close nodes structurally equivalent ?
III.3. Are close nodes in the same modularity clusters ?

IV. Conclusion

[martin.pernollet]

III. Spatialization quality
Here we compare ForceAtlas to other layouts such as OpenOrd, Yifan Hu and Früchtermann Rheingold, on different graphs.
We do not test performance, but quality, meaning: interpretability.

III.1. Are close nodes more connected ?
III.2. Are close nodes structurally equivalent ?
III.3. Are close nodes in the same modularity clusters ?

I confirm ForceAtlas has a better readability that FR layout for a lot of small (50 nodes) graphs: clusters are grouped with sense, and there is really fewer edge intersection (if not none) than with FR layout.
If you define a quality metric, then we can apply it to our graphs if that helps you comparing some layout. It won't be loosed time for us, since it will force us to dive into more rigorous selection of a layout.
Regards,
Martin

[martin.pernollet]

Tell what you would develop, unanswered questions, what you dislike and so on...

Something I would require as a force atlas user is a set of advices for settings the algorithm parameters. Actually I would both like to know how you work them, and discuss a thing I noticed.

Usually, the node size consideration + repulsion by degree do a great job. I found few constants for having a clean graph, but I noticed the following problem: if I apply the same graph structure with larger nodes, I have to increase the repulsion force to avoid small non connected nodes to get stucked in the middle of some big connected nodes.

I found that setting repulsion = 200 * maxNodeRadius generally works well on my dataset. It's a very experimental fact that probably rely on my data. Do you have a similar experience?

Regards,
Martin

[jacomyma]

Thanks for these comments !

About settings:
- Attraction, repulsion and gravity do what we expect them to do, these are the main settings that impact the shape of the graph.
- Autostab, Max displacement and Speed, impact performance and the swinging of nodes.

I have no generic advice for the "shape" settings (except attraction distribution and adjust by size, I think of it). But I can show you a way to improve performance by settings. Try these settings, very spectacular for a 1000 nodes graph for example:

Maximum displacement: 100
Autostab Strength: 95
Autostab sensibility: 0.98
Speed: 5

In the end, if it swings too much, just slow the speed manually. The spectacular point is that it converges extremely fast to a balanced position. Autostab at its best...

[jacomyma]

Hi everybody! I'm back and I am happy.

I updated the whole ForceAtlas code to make it "modern" and the result exceeds my expectations. Just for you (since you're interested in ForceAtlas) there is my current version of the ForceAtlas2 plug-in that I will officially publish soon. It has the same formulas and options (though with different names) with some simplifications, and features two main improvements:
- A better auto-stabilization with no settings needed, except a "sort of" speed called "tolerance to swinging"
- A Barnes Hut optimization that approximates repulsion, from n² to n.log(n) complexity -> far more performance.

Feel free to try it, and I will write the paper on the basis of this code.

Here is the NBM to install in Gephi's "plug-in" center:
[Download ForceAtlas2]
NB: NEEDS Gephi 0.8alpha at least !

[aurelienb]

Nice optimization !
BTW I cannot install it. I have " The Plugin Installer found problem timeout of loading ForceAtlas 2, Quality Layout[org.webatlas.forceatlas2/1.3] while install the following plugins: "... During the plugin install (after select plugin in Tool>Plugin >Downloaded >Install plugin

[aurelienb]

Update about installing>>>


I update my gephi 0.8, and when I would like to re install the plugin, gephi tells me the plugin was already installed. (And it works perfectly).
So there is probably a bug with plugin installer...