188宝金博页面版

OpenOrd: An Open-Source Toolbox for Large Graph LayoutShawn Martina, W. Michael Browna, Richard Klavansb, and Kevin W. BoyackbaSandia National Laboratories, PO Box 5800, Albuquerque, NM 87185bSciTech Strategies, Inc., 2405 White Horse Rd, Berwyn, PA, 19132ABSTRACTWe document an open-source toolbox for drawing large-scale undirected graphs. This toolbox is based on a previouslyimplemented closed-source algorithm known as VxOrd. Our toolbox, which we call OpenOrd, extends the capabilities ofVxOrd to large graph layout by incorporating edge-cutting, a multi-level approach, average-link clustering, and a parallelimplementation. At each level, vertices are grouped using force-directed layout and average-link clustering. The clusteredvertices are then re-drawn and the process is repeated. When a suitable drawing of the coarsened graph is obtained, thealgorithm is reversed to obtain a drawing of the original graph. This approach results in layouts of large graphs whichincorporate both local and global structure. A detailed description of the algorithm is provided in this paper. Examplesusing datasets with over 600K nodes are given. Code is available at www.cs.sandia.gov/∼smartin.Keywords: Multilevel, Force-Directed, Parallel, Large-Scale Graph Layout1. INTRODUCTIONGraph drawing is used to visualize relational data, typically in two dimensions.1,2Some applications of graph drawinginclude social network analysis,3scientific literature analysis,4,5cartography,6and bioinformatics.7,8There are a varietyof algorithms available for graph drawing, each of which optimizes a different set of aesthetic criteria. Some examples ofaesthetic criteria include minimizing the number of edge crossings, minimizing total edge length, and maximizing separa-tion between vertices. For undirected graphs drawn with straight line edges, one ofthe most commonly used algorithms isforce-directed layout.9–13In this paper, we document a graph drawing algorithm specialized for drawing large-scale real-world graphs. Ouralgorithm uses edge-cutting, average-link clustering, multilevel graph coarsening, and a parallel implementation ofa force-directed method based on simulated annealing. Related algorithms for force-directed layout exist, including algorithmstaking a multilevel approach;13–16algorithms which include node clustering;16–18and algorithms implemented using aparallel GPU architecture.19,20However, our algorithm is the only one available which incorporates all three of theseideas: a multilevel approach, node clustering, and a parallel implementation (note that our parallelism is cluster based,instead of GPU based). In addition, we introduce a heuristic for edge-cutting, designed to allow visualization of graphswhich may not have a desirable degree distribution (often found in real-world graphs).Our algorithm is based on a previous force-directed algorithm called VxOrd.21,22This new version, OpenOrd, isdescribed in the following pages. In Section 2, we give the motivation for our modifications of VxOrd. In Section 3,we describe the various parts of our algorithm, including force-directed layout; layout in parallel (3.2); recursive graphcoarsening (3.3); and average-link clustering (3.4). In Section 4, we demonstrate some of the properties of our algorithmusing applications to several real-world datasets, including a 659K vertex Wikipedia article dataset. Finally, in Section 5,we provide our conclusions. Code for OpenOrd is available at http://www.cs.sandia.gov/∼smartin.Further author information: (Send correspondence to S.M.)S.M.: E-mail: smartin@sandia.gov, Telephone: 1 505 284 3601W.M.B.: E-mail: wmbrown@sandia.gov, Telephone: 1 505 284 8938R.K.: E-mail: rklavans@mapofscience.com, Telephone: 1 610 251 2135K.W.B.: E-mail: kboyack@mapofscience.com, Telephone: 1 505 856-1267Visualization and Data Analysis 2011, edited by Pak Chung Wong, Jinah Park, Ming C. Hao, Chaomei Chen,Katy Börner, David L. Kao, Jonathan C. Roberts, Proc. of SPIE-IS&T Electronic Imaging, SPIE Vol. 7868, 786806 · © 2011 SPIE-IS&T · CCC code: 0277-786X/11/$18 · doi: 10.1117/12.871402SPIE-IS&T/ Vol. 7868 786806-1Downloaded From: http://proceedings.spiedigitallibrary.org/ on 06/01/2013 Terms of Use: http://spiedl.org/terms