This repository contains experimental code for large scale graph layout using the GPU. Currently we only implement the basics of ForceAtlas2, a graph layout algorithm designed for social network visualization in Gephi1,2. Our implementation of ForceAtlas2 is based on the open source implementation used in Gephi itself, and considers the graph to be undirected. For force approximation, we use a CUDA implementation of the Barnes-Hut approximation algorithm3 by Martin Burtscher and Keshav Pingali4. This implementation is available as part of LonstarGPU. The average speedup, compared to a de facto CPU implementation of ForceAtlas2, is over 40x. This makes it feasible to compute layouts for networks with millions of nodes and edges. More details and results can be found in:
- G.G. Brinkmann, K.F.D. Rietveld and F.W. Takes, Exploiting GPUs for fast force-directed visualization of large-scale networks, in Proceedings of the 46th International Conference on Parallel Processing (ICPP), pp. 382-391, 2017.
A CUDA capable GPU. Currently only Linux is supported.
This repository contains a submodule (lib/pngwriter). Be sure to run
git submodule init && git submodule update
from the root of this Git repository before compiling. The code also depends on the libpng library (including its development headers). It should be possible to obtain this using the package manager for your Linux distribution.
A Makefile is located in builds/linux. Running
make graph_viewer
from this directory compiles graph_viewer with CUDA support.
To compile without CUDA support, run make graph_viewer CUDA_SUPPORT=0.
graph_viewer gpu|cpu max_iterations num_snaps sg|wg scale gravity exact|approximate edgelist_path out_path [png|csv|bin]
gpu|cpu : choose between a parallel GPU implementation or a serial CPU implementation.
max_iterations : how many iterations of the layout algorithm to run
num_snaps : choose how many times during the layout process a visualization should be rendered
wg|sg : choose between weak gravity (inversely proportional to distance) or
strong gravity
scale : scale repulsive force
gravity : scale gravitational force
exact|approximate : choose between the exact/pairwise O(|V|^2) repulsive force calculation or the O(|V|lg(|V|))
approximation using Barnes-Hut (GPU implementation only supports Barnes-Hut)
edgelist_path : Text file (ascii) containing node IDs for each edge on a separate line (whitespace separated).
Lines starting with a #, the direction of edges, and self-loops are ignored.
out_path : path to write resulting layout to
[png|csv|bin] is optional, defaulting to png, and determines the format of the layout written to out_path.
1 M. Jacomy, T. Venturini, S. Heymann, and M. Bastian, "Forceatlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software", PLoS ONE, vol. 9, no. 6, pp. 1–12, 2014.
2 M. Bastian, S. Heymann, and M. Jacomy, "Gephi: an open source software for exploring and manipulating networks." in Proceedings of International Conference on Web and Social Media (ICWSM), 2009, pp. 361–362.
3J. Barnes and P. Hut, "A hierarchical O(N log N) force-calculation algorithm", Nature, vol. 324, pp. 446–449, 1986.
4 M. Burtscher and K. Pingali, "An efficient CUDA implementation of the tree-based Barnes Hut n-body algorithm", in GPU Computing Gems Emerald Edition, W. mei W. Hwu, Ed., 2011, ch. 6, pp. 75–92.
Most source files for this program are released under the GNU Affero General Public License. The license notice in each file provides more information. A copy of the GNU Affero General Public License can be found in the LICENCE file.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.