Scaling up Force Directed Graph Layout

​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

  1. T. M. J. Freuchterman and E. M. Reingold, ``Graph Drawing by Force-directed Placement", Software: Practice and Experience, 21:1129--1164 (1991)

  2. H. Cheng, L. Greengard, and V. Rokhlin, ``A Fast Adaptive Multipole Algorithm in Three Dimensions", Journal of Computational Physics, 155:468--498 (1999)

  3. 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

Related Publications