Distributed Force-Directed Graph Layout and Visualization

Eurographics Symposium on Parallel Graphics and Visualization (2006) Alan Heirich, Bruno Raffin, and Luis Paulo dos Santos (Editors) Distributed Force-Directed Graph Layout and Visualization ChristopherMueller, DouglasGregor, AndrewLumsdaine Open Systems Laboratory Indiana University Bloomington, IN 47405 {chemuell,dgregor,lums}@osl.iu.edu Abstract While there exist many interactive tools for the visualization of small graphs and networks, these tools do not address the fundamental problems associated with the visualization of large graphs. In particular,larger graphs require much larger display areas (e.g., display walls) to reduce visual

clutter, allowing users to determine the structure of large graphs. Moreover, the layout algorithms employed by these graph visualization tools do not scale to larger graphs, thereby forcing users into a batch- oriented process of generating layouts offline and later viewing of static graph images. In this paper, we present a parallel graph layout algorithm based on the Fruchterman-Reingold force-directed layout algorithm and demonstrate its implementation in a distributed rendering environment.The algorithm uses availabledistributed resources for both compute and renderingtasks, animating the graph as the layout evolves. We evaluatethe algorithm for scalabilityand interactivity and discuss variations that minimize communication for specific types of graphs and applications. 1. Introduction The visualization of large graphsis becoming increas- ingly important in diverse fields including bioinfor- matics, socialnetworkanalysis, andnetwork optimiza- tion (e.g., [ADWM04].However, visualization of large graphs is typically a batch-oriented, sequential pro- cess: users must first constructa layout offline, which can easily require tens of minutes to compute.Users can then view the resulting static image on a single display or display wall. This situationstandsin stark contrast to the plethora of visualization tools [JM04] for small graphs that produce animated, interactive layouts on single workstations. Early results with vi- sualizing dense graphs on large surfacessuggest that they “qualitatively [change] interactive network visu- alization” [AKGN99]. Visualization tools for small graphs do not scale well to larger graphs for two reasons. The first rea- son is that the graph layout algorithms themselves rarely scale well. For instance,many of thesetools use force-directed layout algorithms, which determine the position of each node in a graph by iteratively com- putingattractive forces between connectednodes and repulsive forcesbetweenall pairsof nodes.While these algorithms are ideal for animation—thevisualization systemcan display the graphafter each iteration—the force calculations are expensive and can easily take several secondsper iteration on medium-sized graphs, making them unacceptablyslow for interactive use. The second reason that small-graph visualization tools cannotscale to largergraphsis that few of these toolsprovidesupportfordistributedrenderingto large format display devices such as tiled display walls. Graphvisualizationsare visually limitedby the num- ber of nodes and edges that can be rendered on the display. The node-link graph diagramdisplays nodes as points or glyphs and edges as lines between the nodes. On most displays, only a few hundred edges can be effectively displayed before the image becomes too clutteredto interpret. While techniques exist for c© The Eurographics Association 2006. C. Mueller et al / Distributed Force-Directed Graph Layout and Visualization improving the layout...

Website: osl.iu.edu | Filesize: -
No of Page(s): 8
Download Distributed Force-Directed Graph Layout and Visualization.pdf