Interactive Graph Layout of a Million Nodes

TR Number
Date
2016-12-20
Journal Title
Journal ISSN
Volume Title
Publisher
MDPI
Abstract

Sensemaking of large graphs, specifically those with millions of nodes, is a crucial task in many fields. Automatic graph layout algorithms, augmented with real-time human-in-the-loop interaction, can potentially support sensemaking of large graphs. However, designing interactive algorithms to achieve this is challenging. In this paper, we tackle the scalability problem of interactive layout of large graphs, and contribute a new GPU-based force-directed layout algorithm that exploits graph topology. This algorithm can interactively layout graphs with millions of nodes, and support real-time interaction to explore alternative graph layouts. Users can directly manipulate the layout of vertices in a force-directed fashion. The complexity of traditional repulsive force computation is reduced by approximating calculations based on the hierarchical structure of multi-level clustered graphs. We evaluate the algorithm performance, and demonstrate human-in-the-loop layout in two sensemaking case studies. Moreover, we summarize lessons learned for designing interactive large graph layout algorithms on the GPU.

Description
Keywords
graph layout, big data, visual graph exploration, human-in-the-loop analytics, GPU
Citation
Mi, P.; Sun, M.; Masiane, M.; Cao, Y.; North, C. Interactive Graph Layout of a Million Nodes. Informatics 2016, 3, 23.