Editing Force-directed graph drawing

{{Short description|Physical simulation to visualize graphs}}
{{CS1 config|mode=cs2}}
[[File:SocialNetworkAnalysis.png|250px|right|thumb|Social network visualization using a force-directed graph drawing algorithm<ref>{{citation|first=Martin|last=Grandjean|contribution=Introduction à la visualisation de données, l'analyse de réseau en histoire|year=2015|title=Geschichte und Informatik 18/19|pages=109–128|url=http://www.martingrandjean.ch/wp-content/uploads/2015/09/Grandjean2015.pdf}}</ref>]][[Image:Visualization of wiki structure using prefuse visualization package.png|250px|right|thumb|Visualization of links between pages on a wiki using a force-directed layout]]

'''Force-directed graph drawing''' algorithms are a class of [[algorithm]]s for [[graph drawing|drawing graphs]] in an aesthetically-pleasing way. Their purpose is to position the nodes of a [[Graph (discrete mathematics)|graph]] in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible, by assigning forces among the set of edges and the set of nodes, based on their relative positions, and then using these forces either to simulate the motion of the edges and nodes or to minimize their energy.<ref>{{citation|first=Stephen G.|last=Kobourov|title=Spring Embedders and Force-Directed Graph Drawing Algorithms|year=2012|arxiv=1201.3011|bibcode=2012arXiv1201.3011K}}.</ref>

While graph drawing can be a difficult problem, force-directed algorithms, being physical simulations, usually require no special knowledge about graph theory such as [[planar graph|planarity]].

==Forces==
Force-directed graph drawing algorithms assign forces among the set of edges and the set of nodes of a [[graph drawing]]. Typically, [[spring (device)|spring]]-like attractive forces based on [[Hooke's law]] are used to attract pairs of endpoints of the graph's edges towards each other, while simultaneously repulsive forces like those of [[electric charge|electrically charged]] particles based on [[Coulomb's law]] are used to separate all pairs of nodes. In [[Mechanical equilibrium|equilibrium states]] for this system of forces,  the edges tend to have uniform length (because of the spring forces), and nodes that are not connected by an edge tend to be drawn further apart (because of the electrical repulsion). Edge attraction and vertex repulsion forces may be defined using functions that are not based on the physical behavior of springs and particles; for instance, some force-directed systems use springs whose attractive force is logarithmic rather than linear.

An alternative model considers a spring-like force for every pair of nodes <math>(i,j)</math> where the ideal length <math>\delta_{ij}</math> of each spring is proportional to the graph-theoretic distance between nodes ''i'' and ''j'', without using a separate repulsive force.  Minimizing the difference (usually the squared difference) between [[euclidean distance|Euclidean]] and ideal distances between nodes is then equivalent to a metric [[multidimensional scaling]] problem.

A force-directed graph can involve forces other than mechanical springs and electrical repulsion. A force analogous to gravity may be used to pull vertices towards a fixed point of the drawing space; this may be used to pull together different [[Connected component (graph theory)|connected component]]s of a disconnected graph, which would otherwise tend to fly apart from each other because of the repulsive forces, and to draw nodes with greater [[centrality]] to more central positions in the drawing;<ref>{{citation|contribution=Force-directed graph drawing using social gravity and scaling|first1=M. J.|last1=Bannister|first2=D.|last2=Eppstein|author2-link=David Eppstein|first3=M. T.|last3=Goodrich|author3-link=Michael T. Goodrich|first4=L.|last4=Trott|arxiv=1209.0748|title=Proc. 20th Int. Symp. Graph Drawing|year=2012|bibcode=2012arXiv1209.0748B}}.</ref> it may also affect the vertex spacing within a single component. Analogues of [[magnetic field]]s may be used for directed graphs. Repulsive forces may be placed on edges as well as on nodes in order to avoid overlap or near-overlap in the final drawing. In drawings with curved edges such as [[circular arc]]s or [[spline curve]]s, forces may also be placed on the control points of these curves, for instance to improve their [[Angular resolution (graph drawing)|angular resolution]].<ref>{{citation|first1=R.|last1=Chernobelskiy|first2=K.|last2=Cunningham|first3=M. T.|last3=Goodrich|author3-link=Michael T. Goodrich|first4=S. G.|last4=Kobourov|first5=L.|last5=Trott|contribution=Force-directed Lombardi-style graph drawing|title=Proc. 19th Symposium on Graph Drawing|pages=78–90|year=2011|url=http://www.cs.arizona.edu/~kobourov/fdl.pdf}}.</ref>

==Methods==
Once the forces on the nodes and edges of a graph have been defined, the behavior of the entire graph under these sources may then be simulated as if it were a physical system. In such a simulation, the forces are applied to the nodes, pulling them closer together or pushing them further apart. This is repeated iteratively until the system comes to a [[mechanical equilibrium]] state; i.e., their relative positions do not change anymore from one iteration to the next. The positions of the nodes in this equilibrium are used to generate a drawing of the graph.

For forces defined from springs whose ideal length is proportional to the graph-theoretic distance, [[stress majorization]] gives a very well-behaved (i.e., monotonically [[limit of a sequence|convergent]])<ref name="dl88">{{citation
  | last=de Leeuw | first=Jan
  | title=Convergence of the majorization method for multidimensional scaling
  | year=1988
  | journal=Journal of Classification
  | publisher=Springer
  | volume=5 | issue=2 | pages=163&ndash;180
  | doi=10.1007/BF01897162| s2cid=122413124
 }}.</ref> and mathematically elegant way to [[optimization (mathematics)|minimize]] these differences and, hence, find a good layout for the graph.

It is also possible to employ mechanisms that search more directly for energy minima, either instead of or in conjunction with physical simulation. Such mechanisms, which are examples of general [[global optimization]] methods, include [[simulated annealing]] and [[genetic algorithm]]s.

==Advantages==
The following are among the most important advantages of force-directed algorithms:
; Good-quality results: At least for graphs of medium size (up to 50–500 vertices), the results obtained have usually very good quality based on the following criteria: uniform edge length, uniform vertex distribution and showing symmetry. This last criterion is among the most important ones and is hard to achieve with any other type of algorithm.
; Flexibility: Force-directed algorithms can be easily adapted and extended to fulfill additional aesthetic criteria. This makes them the most versatile class of graph drawing algorithms. Examples of existing extensions include the ones for directed graphs, 3D graph drawing,<ref>{{citation|last=Vose|first=Aaron|title=3D Phylogenetic Tree Viewer|url=http://aaronvose.net/phytree3d/|access-date=3 June 2012}}</ref> cluster graph drawing, constrained graph drawing, and dynamic graph drawing.
; Intuitive: Since they are based on physical analogies of common objects, like springs, the behavior of the algorithms is relatively easy to predict and understand. This is not the case with other types of [[Graph drawing|graph-drawing]] algorithms.
; Simplicity: Typical force-directed algorithms are simple and can be implemented in a few lines of code. Other classes of graph-drawing algorithms, like the ones for orthogonal layouts, are usually much more involved.
; Interactivity: Another advantage of this class of algorithm is the interactive aspect. By drawing the intermediate stages of the graph, the user can follow how the graph evolves, seeing it unfold from a tangled mess into a good-looking configuration. In some interactive graph drawing tools, the user can pull one or more nodes out of their equilibrium state and watch them migrate back into position. This makes them a preferred choice for dynamic and [[online algorithm|online]] graph-drawing systems.
; Strong theoretical foundations: While simple ''ad-hoc'' force-directed algorithms often appear in the literature and in practice (because they are relatively easy to understand), more reasoned approaches are starting to gain traction. Statisticians have been solving similar problems in [[multidimensional scaling]] (MDS) since the 1930s, and physicists also have a long history of working with related [[n-body]] problems - so extremely mature approaches exist. As an example, the [[stress majorization]] approach to metric MDS can be applied to graph drawing as described above. This has been proven to [[Monotone convergence theorem|converge monotonically]].<ref name="dl88"/> Monotonic convergence, the property that the algorithm will at each iteration decrease the stress or cost of the layout, is important because it guarantees that the layout will eventually reach a local minimum and stop. Damping schedules cause the algorithm to stop, but cannot guarantee that a true local minimum is reached.

==Disadvantages==
The main disadvantages of force-directed algorithms include the following:
; High [[Time complexity|running time]]: The typical force-directed algorithms are in general ''considered'' to run in cubic time (<math>O(n^3)</math>), where <math>n</math> is the number of nodes of the input graph. This is because the number of iterations is estimated to be linear (<math>O(n)</math>), and in every iteration, all pairs of nodes need to be visited and their mutual repulsive forces computed. This is related to the [[N-body problem]] in physics. However, since repulsive forces are local in nature the graph can be partitioned such that only neighboring vertices are considered. Common techniques used by algorithms for determining the layout of large graphs include high-dimensional embedding,<ref>{{citation
  | last1=Harel | first1=David | author1-link = David Harel
  | last2=Koren | first2=Yehuda
  | contribution=Graph drawing by high-dimensional embedding
  | year=2002
  | title=Proceedings of the 9th International Symposium on Graph Drawing
  | pages=207&ndash;219
  | publisher=Springer | isbn=3-540-00158-1| citeseerx=10.1.1.20.5390 }}</ref> multi-layer drawing and other methods related to [[N-body simulation]]. For example, the [[Barnes–Hut simulation]]-based method FADE<ref name="quigley+eades">{{citation
 |last1        = Quigley
 |first1       = Aaron
 |last2        = Eades
 |first2       = Peter
 |author2-link = Peter Eades
 |contribution = FADE: Graph Drawing, Clustering, and Visual Abstraction
 |url          = https://aaronquigley.org/wp-content/uploads/2019/03/Fade-2000-aquigley.pdf 
 |year         = 2001
 |title        = Proceedings of the 8th International Symposium on Graph Drawing
 |pages        = 197&ndash;210
 |isbn         = 3-540-41554-8
 }}.</ref> can improve the running time to be linearithmic, or <math>n\log(n)</math> per iteration. As a rough guide, in a few seconds one can expect to draw at most 1,000 nodes with a standard <math>n^2</math> per iteration technique, and 100,000 with a <math>n\log(n)</math> per iteration technique.<ref name="quigley+eades" /> Force-directed algorithms, when combined with a graph clustering approach, can draw graphs of millions of nodes.<ref>{{citation|title=A Gallery of Large Graphs|url=http://yifanhu.net/GALLERY/GRAPHS/|access-date=22 Oct 2017}}</ref>

; Poor local minima: It is easy to see that force-directed algorithms produce a graph with minimal energy, in particular one whose total energy is only a [[local minimum]]. The local minimum found can be, in many cases, considerably worse than a global minimum, which translates into a low-quality drawing. For many algorithms, especially the ones that allow only ''down-hill'' moves of the vertices, the final result can be strongly influenced by the initial layout, that in most cases is randomly generated. The problem of poor local minima becomes more important as the number of vertices of the graph increases. A combined application of different algorithms is helpful to solve this problem.<ref>{{citation
 | last1 = Collberg | first1 = Christian
 | last2 = Kobourov | first2 = Stephen
 | last3 = Nagra | first3 = Jasvir
 | last4 = Pitts | first4 = Jacob
 | last5 = Wampler | first5 = Kevin
 | contribution = A System for Graph-based Visualization of the Evolution of Software
 | doi = 10.1145/774833.774844
 | isbn = 1-58113-642-0
 | location = New York, NY, USA
 | pages = 77–86; figures on p.&nbsp;212
 | publisher = ACM
 | title = Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03)
 | url = https://www.researchgate.net/publication/2851716
 | year = 2003| s2cid = 824991
 |quote=To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.}}</ref> For example, using the Kamada–Kawai algorithm<ref name="kk89"/> to quickly generate a reasonable initial layout and then the Fruchterman–Reingold algorithm<ref name="fr91"/> to improve the placement of neighbouring nodes. Another technique to achieve a global minimum is to use a multilevel approach.<ref>{{citation
 | last = Walshaw | first = Chris
 | doi = 10.7155/jgaa.00070
 | issue = 3
 | journal = Journal of Graph Algorithms and Applications
 | mr = 2112231
 | pages = 253–285
 | title = A multilevel algorithm for force-directed graph-drawing
 | volume = 7
 | year = 2003}}</ref>

==History==
Force-directed methods in graph drawing date back to the work of {{harvtxt|Tutte|1963}}, who showed that [[polyhedral graph]]s may be drawn in the plane with all faces convex by fixing the vertices of the outer face of a planar embedding of the graph into [[convex position]], placing a spring-like attractive force on each edge, and letting the system settle into an equilibrium.<ref>{{citation|first=W. T.|last=Tutte|author-link=W. T. Tutte|title=How to draw a graph|journal=Proceedings of the London Mathematical Society|volume=13|issue=52|pages=743–768|year=1963|doi=10.1112/plms/s3-13.1.743}}.</ref> Because of the simple nature of the forces in this case, the system cannot get stuck in local minima, but rather converges to a unique global optimum configuration. Because of this work, embeddings of planar graphs with convex faces are sometimes called [[Tutte embedding]]s.

The combination of attractive forces on adjacent vertices, and repulsive forces on all vertices, was first used by {{harvtxt|Eades|1984}};<ref>{{citation
  | last=Eades | first=Peter | author-link = Peter Eades
  | title=A Heuristic for Graph Drawing
  | year=1984
  | journal=Congressus Numerantium
  | volume=42 | issue=11 | pages=149–160}}.</ref> additional pioneering work on this type of force-directed layout was done by {{harvtxt|Fruchterman|Reingold|1991}}.<ref name="fr91">{{citation
  | last1=Fruchterman | first1=Thomas M. J.
  | last2=Reingold | first2=Edward M. | author2-link = Edward Reingold
  | title=Graph Drawing by Force-Directed Placement
  | year=1991
  | journal=Software: Practice and Experience
  | publisher=Wiley
  | volume=21 | issue=11 | pages=1129&ndash;1164
  | doi=10.1002/spe.4380211102| s2cid=31468174
 }}.</ref> The idea of using only spring forces between all pairs of vertices, with ideal spring lengths equal to the vertices' graph-theoretic distance, is from {{harvtxt|Kamada|Kawai|1989}}.<ref name="kk89">{{citation
  | last1=Kamada | first1=Tomihisa
  | last2=Kawai | first2=Satoru
  | title=An algorithm for drawing general undirected graphs
  | year=1989
  | journal=Information Processing Letters
  | publisher=Elsevier
  | volume=31 | issue=1 | pages=7&ndash;15
  | doi=10.1016/0020-0190(89)90102-6}}.</ref>

==See also==
*[[Cytoscape]], software for visualising biological networks. The base package includes force-directed layouts as one of the built-in methods.
*[[Gephi]], an interactive visualization and exploration platform for all kinds of networks and complex systems, dynamic and hierarchical graphs.
*[[Graphviz]], software that implements a multilevel force-directed layout algorithm (among many others) capable of handling very large graphs.
*[[Tulip (software)|Tulip]], software that implements most of the force-directed layout algorithms (GEM, LGL, GRIP, FM³).
*[[Prefuse]]

==References==
{{Reflist|colwidth=30em}}

==Further reading==
* {{citation
  | last=di Battista | first=Giuseppe
 |author2=Peter Eades | author3-link=Roberto Tamassia
 |author3=Roberto Tamassia |author4=Ioannis G. Tollis
  | title=Graph Drawing: Algorithms for the Visualization of Graphs
  | publisher=Prentice Hall
  | year=1999
  | isbn=978-0-13-301615-4| author2-link=Peter Eades
 }}
* {{citation
  | editor1-last=Kaufmann | editor1-first=Michael
  | editor2-last=Wagner | editor2-first=Dorothea | editor2-link = Dorothea Wagner
  | title=Drawing graphs: methods and models
  | volume=2025
 | publisher=Springer
  | year=2001
  | series=Lecture Notes in Computer Science 2025
  | doi=10.1007/3-540-44969-8
  | isbn=978-3-540-42062-0| s2cid=1808286
 }}

==External links==
*[https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/force-directed.pdf Book chapter on Force-Directed Drawing Algorithms] by Stephen G. Kobourov

{{DEFAULTSORT:Force-Based Algorithms (Graph Drawing)}}
[[Category:Graph algorithms]]
[[Category:Graph drawing]]