ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software.
Jacomy M, Venturini T, Heymann S, Bastian M. · 2014
Read ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software. by Jacomy M, Venturini T, Heymann S, Bastian M. (2014) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc4051631.txt.
Introduction
Mathieu Jacomy and four colleagues document ForceAtlas2, the layout engine inside the Gephi network software, in PLoS ONE in 2014. Network maps turn tangled link data into pictures a person can read. Gephi aims that power at users from many fields, and its default layout runs while the user watches and drags.
ForceAtlas2 treats nodes as charged particles that repel and links as springs that pull. Several tricks keep it handy at the sizes users actually bring, roughly ten to ten thousand nodes. A gravity shortcut borrowed from physics speeds the repulsion maths. Repulsion scales with node degree so hubs do not crush the map. Speed adapts locally and globally to settle the picture without wild swings. The paper gives the full formulas and each setting's meaning. The authors claim craft, not theory.
Catalog record
| CREATOR | Jacomy M, Venturini T, Heymann S, Bastian M. |
|---|---|
| YEAR | 2014 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software By Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, Mathieu Bastian, Mark R. Muldoon Published in: PLoS ONE DOI: 10.1371/journal.pone.0098679 ABSTRACT Gephi is a network visualization software used in various disciplines (social network analysis, biology, genomics…). One of its key features is the ability to display the spatialization process, aiming at transforming the network into a map, and ForceAtlas2 is its default layout algorithm. The latter is developed by the Gephi team as an all-around solution to Gephi users’ typical networks (scale-free, 10 to 10,000 nodes). We present here for the first time its functioning and settings. ForceAtlas2 is a force-directed layout close to other algorithms used for network spatialization. We do not claim a theoretical advance but an attempt to integrate different techniques such as the Barnes Hut simulation, degree-dependent repulsive force, and local and global adaptive temperatures. It is designed for the Gephi user experience (it is a continuous algorithm), and we explain which constraints it implies. The algorithm benefits from much feedback and is developed in order to provide many possibilities through its settings. We lay out its complete functioning for the users who need a precise understanding of its behaviour, from the formulas to graphic illustration of the result. We propose a benchmark for our compromise between performance and quality. We also explain why we integrated its various features and discuss our design choices. INTRODUCTION This paper addresses two different audiences. To Gephi users, we offer a complete description of the ForceAtlas2 algorithm and its settings. To the researchers or engineers interested in the development of spatialization algorithms, we offer a discussion of our choices of features and implementation. If developing an algorithm is “research” and implementing it is “engineering”, then a specificity of Gephi overall, is that it is based in engineering rather than in research. This is why it looks so different to a software like Pajek. This is also why ForceAtlas2 is more about usability than originality. Our contribution to the mathematics of network spatialization is limited to the benchmark of a specific implementation of adaptive speed (step length selection). This paper focuses more on how classical techniques fit together in the perspective of a rich user experience - and which techniques do not. It is necessary to explain quickly how the user feedback led us to the specific orientation of ForceAtlas2 (a continuous algorithm). In the next sections we will explore the different techniques gathered in this layout, with some formal terminology and many illustrations. We will discuss our implementation of step length selection with examples and a benchmark. And finally we will offer a short discussion about the general design of the algorithm. In 2008 we started to develop Gephi [1], a software to visualize and manipulate networks, at the Maison des Sciences de l’Homme in Paris under the direction of Dana Diminescu [2]. Our goal was to provide some network analysis methods to social scientists, that would not require learning graph theory. Three reference softwares inspired us: Pajek [3], GUESS [4] and TouchGraph. TouchGraph offered a manipulative interface that we highly appreciated, but it had serious performance issues and the layout was not adapted to scale-free networks of a hundred nodes or more (high visual cluttering). Pajek is very powerful but not adapted to dynamic exploration (it is designed as a computation software, where visualization is a bonus). GUESS was the most adapted to our needs, being user-centric and implementing state-of-the-art spatialization algorithms such as GEM [5]. We do not explore here the reasons why we created Gephi rather than just using GUESS, since it is a much larger discussion. However, an important point for this paper is that we wanted a continuous layout, that runs homogeneously and which can be displayed. Visualizing the “live” spatialization is a key feature of Gephi. It provides a very intuitive understanding of the layout process and its settings. It allows users to have a trial-error approach to the layout, that improves the learning curve of Gephi. We developed ForceAtlas2 by combining existing techniques. We did it “wildly”: we did not start from a systematic review of academic papers, and we eventually redeveloped existing techniques. We implemented features when they were needed by users, and we tried to incorporate user-friendly settings in the design. (When we reworked all the settings, we created a “version 2” of “ForceAtlas” to avoid a too confusing change. Both versions are still available in Gephi even if the first version is obsolete.) We focused ForceAtlas2 on fluency and quality, because fluency is required by Gephi’s interactive user experience, and because researchers prefer quality over performance. The fundamentals of the algorithm are not sophisticated. As long as it runs, the nodes repulse and the edges attract. This push for simplicity comes from a need for transparency. Social scientists cannot use black boxes, because any processing has to be evaluated in the perspective of the methodology. Our features change the forces or how they are simulated, but keep this model of continuous force directed layout: forces apply continuously as long as the layout is running. We give more details about our reasons at this end of this paper. Developing a continuous algorithm prevented us from implementing many powerful techniques. We cite here some techniques that we intentionally avoided for focusing reasons. Simulated annealing [6] cannot be fully implemented, nor can any auto-stop feature (like Yifan Hu [7], also implemented in Gephi). Our layout stops exclusively at the user’s request. Phased strategies, used for example by OpenOrd [8], are by definition incompatible, even if in this case it allows OpenOrd to spatialize much larger networks. Graph coarsening [7], [9] cannot be implemented for the same reason. Finally, strategies where forces do not apply homogeneously do not necessary fit, because the motion of the network during the layout is not as fluid and it impacts the user experience. It is especially the case of the old Kamada Kawai [10] and more recently GEM [5]. We abandoned many techniques by keeping ForceAtlas2 continuous. But most of these are actually optimizations, and our performances are still compatible with the size of networks managed by Gephi (as we will see). We were able to implement qualitative features that impact the placement of the nodes, such as a degree-dependent repulsion force suggested by Noack [11], gravitation, and other features. We also implemented the Lin-Log forces proposed by Noack, a great inspiration for us, since his conception of layout quality corresponds to researchers’ needs (a visual interpretation of modularity). ANATOMY OF FORCEATLAS2 ForceAtlas2 is a force directed layout: it simulates a physical system in order to spatialize a network. Nodes repulse each other like charged particles, while edges attract their nodes, like springs. These forces create a movement that converges to a balanced state. This final configuration is expected to help the interpretation of the data. The force-directed drawing has the specificity of placing each node depending on the other nodes. This process depends only on the connections between nodes. Eventual attributes of nodes are never taken into account. This strategy has its drawbacks. The result varies depending on the initial state. The process can