Skip to content

An experimental GPU accelerated implementation of ForceAtlas2

License

Unknown, AGPL-3.0 licenses found

Licenses found

Unknown
LICENSE
AGPL-3.0
COPYING
Notifications You must be signed in to change notification settings

govertb/GPUGraphLayout

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

86 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

graph_viewer | GPU accelerated graph layout

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:

Citing

To cite this software, please use the aforementioned reference, or the preferred-citation section in CITATION.cff. The latter can be converted to the desired format using various tools, or using the Cite this repository button in the About section of this project's GitHub page.

System Requirements

A CUDA capable GPU. Currently only Linux is supported.

Obtaining all code

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.

Compiling

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.

Usage

graph_viewer gpu|cpu max_iterations num_snaps sg|wg scale gravity exact|approximate edgelist_path out_path [png|csv|bin]

Argument Description
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| \log |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.

References

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.

License

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.

Disclaimer

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.