high performance computing on graphics processing units: hgpu.org

Modeling phenomena with networks has a wide application in many disciplines including biology, economics, sociology, and computer science. In network analysis modularity is an important measure for automatically extracting communities of closely connected nodes. Another important aspect of the network analysis is network visualization. Different techniques for network layout generation exist and the force-driven layout is one of the most popular ones. However, generating force-driven layouts of large networks is both time consuming and can produce a layout where distinct communities of nodes are not separated, but rather remain untangled. Such layouts are harder to be visually inspected by an end-user. In this paper, we propose a GPU-based implementation of a force-driven algorithm for layout generation. By exploiting the massively parallel architecture of modern GPUs we reduce the computational time by orders of magnitude compared with the CPU-based implementation. Secondly, we implement a multi-layer force-driven method for network layout generation where communities are less entangled. Again, by exploiting the GPU we obtain significant speed-up of computation over the CPU implementations. Our results imply that GPUs can speed up significantly the computations in network analysis and thus larger networks can be analyzed in real-time.