ForceAtlas publication

[aary]

ForceAtlas layout turned to be a very useful tool in my research project,
and it will be nice if I can cite it in my next paper.

Is there any publication for this algorithm? form a blog post (http://gephi.org/forum/topic.php?id=5403) I found how it works, but
a blog post is not the best way of citing an algorithm.

[jacomyma]

Hi,

I never took the time to write something about ForceAtlas. I could write a post about it somewhere but I probably won't publish quick enough to be cited.

I suggest you cite the work of Andreas Noack. In particular its PHD http://opus.kobv.de/btu/volltexte/2007/ ... sNoack.pdf (look at page 102).

When I tried to improve the "Früchtermann Rheingold" algorithm, I had an approach that is very similar to Noack's. I tried to improve the quality the same way. That's why ForceAtlas is similar to Noack's edge-directed force layout, and gives similar results in terms of quality. The difference is that I didn't achieve the mathematical perspective, while Noack has done an remarkably elegant work on that.

[seinecle]

Hi Mathieu,

Yes, the community would be very grateful if you could publish a clear explanation of what Force Atlas does, and a description of what its parameters do. That is absolutely necessary for academic publications - reviewers will not accept just the name "Force Atlas", and also to be able to explain to the users what it is that the layout does.

Surely a boring thing to do, but ... !!

Best,

Clement

[jacomyma]

If people help me, I publish with them. I have many things to say so it's not a question of "what to write". But writing a paper is also making the biblio, finding a place where to publish...

I think I'm just going to open an thread dedicated to the writing of this paper. This will be an interesting experience.

[jacomyma]

Oh, finally this thread is fine ^^ !


Participate here to the writing of a paper about ForceAtlas

Here's the deal:
- Everybody may participate
- I'm the developer of ForceAtlas, you are the users, so everybody has something to bring. You'll at least tell me what interests you to read.
- Everybody is enjoined to review the work in progress.
- Those that actually participate will have their name on the paper
- But there is no guarantee that it will work, or that the paper will actually be published...
Even if it would be really cool.


Here is our starting point:
Issues addressed in the ForceAtlas paper

- ForceAtlas is made to spatialize Small-World / Scale-free networks, meaning "real" data (and not theoretical lattices or geometric figures...)

- Performance and Quality: ForceAtlas' purpose is not performance, but quality. Some force directed layouts seek performance (Yifan Hu, OpenOrd) while other seek quality (LinLog, ForceAtlas). The ForceAtlas has been empirically developed to allow a rigorous interpretation of the graph (ex. in SNA), with the fewest biases possible, and a good readability, even if it is slow.

- The pattern of attraction / repulsion is similar to the "Früchtermann Rheingold" layout plus gravity (very classical), but...

- The "quality trick" that gives ForceAtlas its identity comes from its asymmetrical repulsion force, that takes in account the degree of nodes. Andreas Noack proposed the LinLog layout, that features an "edge directed" option that is very close to this principle. Noack formalized a quality measure that fits to the needs we had, and we empirically produces something similar to what Noack produced.

- But contrary to the LinLog, ForceAtlas has no strong mathematical foundation (it's the result of an empirical research). We issued stability problems due to the asymmetry of the force, that's why we developed the "auto-stabilize" function (that is different from the Barnes Hut optimization, and from the optimization in a layout like GEM, but there might be similar things in some layouts that I don't know).

- We claim that as far as the purpose of the layout is to interpret the graph, options that give different views are useful and that's why we propose the "distributed attraction" setting. Once activated, it divides the attraction of an edge by the outdegree of the source nodes. This makes hubs attract less while authorities attract more. This makes sense for some types of graphs like web networks, where we consider that authorities are more central than hubs (the "value" is the authority or the indegree). This features keeps authorities in the center and push hubs to the border.

- As well, we think it's useful to have a "nodes don't overlap" feature. This is not a mathematical feature, but a semiotic feature. Gephi is not a theoretical framework but a tool. These non-purely-mathematic feature are precisely what we want to get in a tool like Gephi.


Tell what you think about that !

[elijah]

I think it's remarkably interesting that this particular force-directed algorithm has been so useful to me given that I'm dealing with humanities datasets that are meant to be positioned theoretically by a scholar in a qualitative manner. I think walking through the explicit algorithm would be useful (even to softies like me), but I'd also like to further explore the idea of a semiotic force-directed layout.

[jacomyma]

My idea is that it works well because it's focused on quality. All other layouts are focused on performance, except Noack's "LinLog". Noack has made such a great job! He achieved a mathematical theory that I couldn't. But the ForceAtlas experience reveals something else: the perspective of improving quality of layouts is valid. It is valid even if this quest is mainly empirical (this is the difference with LinLog) and it is valid if, by "quality", we mean "being useful for exploring real data in a scientific perspective".
On that point, figure out that I developed the Gephi prototype because I had studies to do, and I was deeply frustrated by Eytan Adar's "Guess" software, because layouts were hidden behind progress bars, because I couldn't improve the quality of my graphs, and because I felt that it would be possible if I had a way to edit the settings and see how the impact the spatialization. Because I needed that, I started to build a tool that would passed to Mathieu Bastian and the to the community. But the ForceAtlas is historically, the reason why Gephi has been developed... To be dealing with graphs in humanities.

Could you explain why you find ForceAtlas better than another layout ?

[rotten]

From my perspective -- because it is the only one that produces "intuitive" graphs. The other layouts may produce pretty pictures, but they aren't really intuitive.

[elijah]

I find that Force Atlas's parameters are highly intuitive and when demonstrating the layout I can explain how the graph is forming by referring to repulsive and attractive strength and it frames the intuitive sense of what is occurring. I also like Yifan Hu, because it emphasizes hierarchies, but ForceAtlas seems more locally regular, whereas OpenOrd, which is useful for the giant graphs, is good for large structures but doesn't seem to be good for exploring the middle and small structures. I suppose what I'm describing is the fractal nature of ForceAtlas and how that makes it useful for a wide variety of scales where you are examining patterns at different scales and the interrelation between those patterns.

[seinecle]

I find it intuitive because it mimics a kind of elastic gravitational pull between two magnets of the same polarity - that can be intuitive, with some imagination. A cool thing would be to actually have a small animation representing a real spring with all its twists linking two bipolar magnets. That would s(t)imulate the physical analogy.