TY - GEN

T1 - Scalable force directed graph layout algorithms using fast multipole methods

AU - Yunis, Enas Abdulrahman

AU - Yokota, Rio

AU - Ahmadia, Aron

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2012/6

Y1 - 2012/6

N2 - 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 required in applying the Force-Directed Graph Layout algorithm is O(|V|2 + |E|) using direct calculations and O(|V| log |V| + |E|) using truncation, filtering, and/or multi-level techniques. Correct application of the Fast Multipole Method allows us to maintain a lower complexity of O(|V| + |E|) while regaining most of the precision lost in other techniques. Solving layout problems for truly large graphs with millions of vertices still requires 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. © 2012 IEEE.

AB - 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 required in applying the Force-Directed Graph Layout algorithm is O(|V|2 + |E|) using direct calculations and O(|V| log |V| + |E|) using truncation, filtering, and/or multi-level techniques. Correct application of the Fast Multipole Method allows us to maintain a lower complexity of O(|V| + |E|) while regaining most of the precision lost in other techniques. Solving layout problems for truly large graphs with millions of vertices still requires 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. © 2012 IEEE.

UR - http://hdl.handle.net/10754/564557

UR - http://ieeexplore.ieee.org/document/6341510/

UR - http://www.scopus.com/inward/record.url?scp=84870738774&partnerID=8YFLogxK

U2 - 10.1109/ISPDC.2012.32

DO - 10.1109/ISPDC.2012.32

M3 - Conference contribution

SN - 9780769548050

SP - 180

EP - 187

BT - 2012 11th International Symposium on Parallel and Distributed Computing

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -