Description
The Fruchterman-Reingold Algorithm is a force-directed layout algorithm. The idea of a force directed layout algorithm is to consider a force between any two nodes. In this algorithm, the nodes are represented by steel rings and the edges are springs between them. The attractive force is analogous to the spring force and the repulsive force is analogous to the electrical force. The basic idea is to minimize the energy of the system by moving the nodes and changing the forces between them. For more details refer to the Force Directed algorithm.
In this algorithm, the sum of the force vectors determines which direction a node should move. The step width, which is a constant determines how far a node moves in a single step. When the energy of the system is minimized, the nodes stop moving and the system reaches it's equilibrium state. The drawback of this is that if we define a constant step width, there is no guarantee that the system will reach equilibrium at all. T.M.J. Fruchterman and E.M. Reingold introduced a "global temperature" that controls the step width of node movements and the algorithm's termination. The step width is proportional to the temperature, so if the temperature is hot, the nodes move faster (i.e, a larger distance in each single step). This temperature is the same for all nodes, and cools down at each iteration. Once the nodes stop moving, the system terminates.
Links
Pros & Cons
The Fruchterman-Reingold Algorithm is useful for visualizing very large undirected networks. It guarantees that topologically near nodes are placed in the same vicinity, and far nodes are placed far from each other. Using a global temperature creates an overall satisfying layout, however there will be deficiencies in some local areas of the graph. This can be improved by using the "adaptive temperature scheme" based on local temperatures.
Applications
The BioLayout program which is used for visualisation of biological networks is the C-implementation of the Fruchterman-Reingold algorithm. A Java version of the same program is also available.
Implementation Details
The input is a list of all the nodes and the pairs that are connected by an edge. The visualization requires a layout which takes the graph and determines the location at which each of the nodes are drawn. To generate the layout, the repulsive and attractive force for each node is calculated independently and the total energy of the nodes is obtained iteratively. At each iteration, the nodes are moved around to decrease the total energy. The maximum displacement of each node in an iteration is limited by a constant which is decreased with each iteration. The iterations terminate when the nodes become stationary and the final layout is obtained.
Then the Java Swing component provides a "drawing area" on which the data is rendered using the VisualzationViewer class provided by JUNG. Finally the Renderer takes the data provided by the layout and draws the nodes and edges into the component.
Usage Hints
Use the B-A model to generate a network and visualize it with the Fruchterman-Reingold layout algorithm.
Acknowledgements
This code was implemented by the JUNG team and integrated by Weixia (Bonnie) Huang. Documentation compiled by Soma Sanyal.
References
Fruchterman, T. M. J., & Reingold, E. M. (1991). Graph Drawing by Force-Directed Placement. Software: Practice and Experience, 21(11).
