Force Directed Graph Layout Algorithm
Represent vertices and edges of graphs in an aesthetically pleasing readable format in 3D
Uses
Infrastructure Networks - Router Topology/Connectivity
Biological Networks - Protein-Protein Interactions
Hierarchical Networks - File System
Social Networks - Friendships
Languages - Word Adjacency
Web & Internet - Web Links
Method
Treat vertices as repelling eletrostatic charges and edges as attracting springs. Use time stepping optimization techniques for an acceptable placement [1].
Strengths
Optimized heavily in sparse balanced graphs
Weaknesses
Many tuning parameters and repulsion calculation require O(N2) work for N vertices
Add32 - Computer component design of a 32-bit adder
Jagmesh1 - Finite element mesh
Fast Multipole Method
One of the top 10 algorithms in the 20th century
Used to calculate N-body problems (electrostatics and astrophysics)
Series expansions efficiently transport force data in hierarchical manner [2]
Runs at O(N) with bounded error
Great compatibility and stability for repulsion force calculation
Extends the current feature set of ExaFMM library [3]
Performance on Local Workstation
Breakdown of a single step using a Xeon (R) X5650 @ 2.67 GHz and NVIDIA GF100 series GPU
Performance on TSUBAME 2.0 (#5 on the Nov 2011 Top500 list)
Runtime of repulsion only on 64 cores/GPUs. (N=10^4-10^7)
Breakdown of strong scaling (Runtime is multiplied by the number of cores/GPUs)
Graphs of co-authorships in network science
References
T. M. J. Freuchterman and E. M. Reingold, ``Graph Drawing by Force-directed Placement", Software: Practice and Experience, 21:1129--1164 (1991)
H. Cheng, L. Greengard, and V. Rokhlin, ``A Fast Adaptive Multipole Algorithm in Three Dimensions", Journal of Computational Physics, 155:468--498 (1999)
R. Yokota and L. A. Barba, ``A Tuned and Scalable Fast Multipole Method as a Preeminent Algorithm for Exascale Systems", The International Journal of High Performance Computing Applications, Accepted
Data sources
