Scalable Force Directed Graph Layout Algorithms Using Fast Multipole

Scalable Force Directed Graph Layout Algorithms Using Fast Multipole Methods Enas Yunis, Rio Yokota and Aron Ahmadia King Abdullah University of Science and Technology 4700 KAUST, Thuwal, KSA 23955-6900 fenas.yunis, rio.yokota, aron.ahmadiag @kaust.edu.sa Abstract—We present an extension to ExaFMM, a Fast Multipole Method library, as a generalized approach for fast and scalable execution of the Force-Directed Graph Layout algorithm. The Force-Directed Graph Layout algorithm is a physics-based approach to graph layout that treats the vertices V as repelling charged particles

with the edges E connecting them acting as springs. Traditionally, the amount of work re- quired in applying the Force-Directed Graph Layout algorithm is O(jVj2 +jEj) using direct calculations and O(jVjlogjVj+ jEj) using truncation, filtering, and/or multi-level techniques. Correct application of the Fast Multipole Method allows us to maintain a lower complexity of O(jVj + jEj) while regaining most of the precision lost in other techniques. Solving layout problems for truly large graphs with millions of vertices still re- quires a scalable algorithm and implementation. We have been able to leverage the scalability and architectural adaptability of the ExaFMM library to create a Force-Directed Graph Layout implementation that runs efficiently on distributed multicore and multi-GPU architectures. Keywords-Force directed graph layout; Fast multipole meth- ods; Multi-GPUs I. INTRODUCTION Force-Directed Graph Layout (FDGL) is a popular al- gorithm for automatically generating aesthetically pleasing 2D and 3D visualizations of large sparse graphs [1], [2]. FDGL is a physics-based approach to graph layout that treats the vertices as repelling charged particles and the edges connecting them as springs. Given a graph G = (V;E) consisting of a set of vertices V and a set of undirected edges E, a graph layout algorithm associates a position xd for each vertex v in V . FDGL works by assigning an initial random position x0 to each vertex and interactive forces between each vertex (usually an electromagnetic-style repulsion between each vertex modeled after Coulomb’s Law and attractive linear springs among edges modeled after Hooke’s Law), then using either global optimization heuristics to find a configuration of minimal potential energy, where the system’s potential energy P is computed by summing the repulsive vertex-vertex potential interaction energies Pv and the edge potential energies Pe over all vertices. A common heuristic for minimizing potential energy is simulated annealing, [1], [3] where a “warm” system with vertices allowed to freely move is gradually “cooled” allowing the algorithm to occasionally escape local minima in optimizing P. There are several commonly used stopping criterion; [3] bases their approach on total system energy, while [1] relies on a direct temperature cooling technique. Additionally, there are a large variety of force models for interactions, some can be easily connected to existing physical models, while others rely on purely mathematical constructions. Calculating the repulsive interactions na¨ıvely using direct integration requires O(jVj2) computations [1], [2]. Addi- tionally, O(jEj) computations per iteration are needed for spring calculations. Given...

Website: www.bu.edu | Filesize: -
No of Page(s): 7
Download Scalable Force Directed Graph Layout Algorithms Using Fast Multipole.pdf