OpenOrd: an open-source toolbox for large graph layout
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEPublished 11 January 2011
Shawn Martin, William M. Brown, Richard Klavans, Kevin W. Boyack
Citations278
SJR score0.15
SNIP0.20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An open-source toolbox for drawing large-scale undirected graphs based on a previously implemented closed-source algorithm known as VxOrd, which is extended by incorporating edge-cutting, a multi-level approach, average-link clustering, and a parallel implementation.
Abstract
We document an open-source toolbox for drawing large-scale undirected graphs. This toolbox is based on a previously implemented closed-source algorithm known as VxOrd. Our toolbox, which we call OpenOrd, extends the capabilities of VxOrd to large graph layout by incorporating edge-cutting, a multi-level approach, average-link clustering, and a parallel implementation. At each level, vertices are grouped using force-directed layout and average-link clustering. The clustered vertices are then re-drawn and the process is repeated. When a suitable drawing of the coarsened graph is obtained, the algorithm is reversed to obtain a drawing of the original graph. This approach results in layouts of large graphs which incorporate both local and global structure. A detailed description of the algorithm is provided in this paper. Examples using datasets with over 600K nodes are given. Code is available at www.cs.sandia.gov/~smartin.
Keywords
Computer SciencePhysics and Astronomy
ScienceNonlinear Dimensionality Reduction by Locally Linear Embedding
15,035 Citations2000Sam T. Roweis, Lawrence K. Saul
Locally linear embedding (LLE) is introduced, an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs that learns the global structure of nonlinear manifolds.
ScienceA Global Geometric Framework for Nonlinear Dimensionality Reduction
13,740 Citations2000Joshua B. Tenenbaum, Vin de Silva +1 more
An approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set and efficiently computes a globally optimal solution, and is guaranteed to converge asymptotically to the true structure.
ACM Computing SurveysData clustering
13,184 Citations1999Anil K. Jain, M. Narasimha Murty +1 more
An overview of pattern clustering methods from a statistical pattern recognition perspective is presented, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners.
Software Practice and ExperienceGraph drawing by force‐directed placement
6,359 Citations1991Thomas M. J. Fruchterman, Edward M. Reingold
A modification of the spring‐embedder model of Eades for drawing undirected graphs with straight edges is presented, developed in analogy to forces in natural systems, for a simple, elegant, conceptually‐intuitive, and efficient algorithm.
Molecular Biology of the CellComprehensive Identification of Cell Cycle–regulated Genes of the Yeast<i>Saccharomyces cerevisiae</i>by Microarray Hybridization
4,799 Citations1998Paul T. Spellman, Gavin Sherlock +7 more
A comprehensive catalog of yeast genes whose transcript levels vary periodically within the cell cycle is created, and it is found that the mRNA levels of more than half of these 800 genes respond to one or both of these cyclins.
Information Processing LettersAn algorithm for drawing general undirected graphs
2,771 Citations1989Tomihisa Kamada, Satoru Kawai
Graph Drawing: Algorithms for the Visualization of Graphs
1,996 Citations1998Giuseppe Di Battista, Peter Eades +2 more
A multilevel algorithm for partitioning graphs
1,073 Citations1995Bruce Hendrickson, Robert W. Leland
A multilevel algorithm for graph partitioning in which the graph is approximated by a sequence of increasingly smaller graphs, and the smallest graph is then partitioned using a spectral method, and this partition is propagated back through the hierarchy of graphs.
ScientometricsMapping the backbone of science
952 Citations2005Kevin W. Boyack, Richard Klavans +1 more
A new map representing the structure of all of science, based on journal articles, is presented, including both the natural and social sciences, including biochemistry, which appears as the most interdisciplinary discipline in science.
ScienceA Gene Expression Map for <i>Caenorhabditis elegans</i>
664 Citations2001Stuart K. Kim, Jim Lund +7 more
This work assembled data from Caenorhabditis elegans DNA microarray experiments involving many growth conditions, developmental stages, and varieties of mutants to create a three-dimensional expression map that displays correlations of gene expression profiles as distances in two dimensions and gene density in the third dimension.
Journal of Social StructureVisualizing Social Networks.
646 Citations2000Linton C. Freeman
The historian Alfred Crosby (1997) has proposed that visualization is one of only two factors that are responsible for the explosive development of all of modern science.
A stability based method for discovering structure in clustered data
540 Citations2001Asa Ben‐Hur, André Elisseeff +1 more
The method can be used with any clustering algorithm and provides a means of rationally defining an optimum number of clusters, and can also detect the lack of structure in data.
ACM Transactions on GraphicsDrawing graphs nicely using simulated annealing
489 Citations1996Ron Davidson, David Harel
The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely,” and the algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result.
Proceedings of the National Academy of SciencesMapping knowledge domains
385 Citations2004Richard M. Shiffrin, Katy Börner
The Arthur M. Sackler Colloquium on Mapping Knowledge Domains was designed to showcase the ongoing developments in this transformation and provide pointers toward the directions it will move.
Journal of the American Statistical AssociationStep-Wise Clustering Procedures
358 Citations1967Benjamin King
Lecture notes in computer scienceDrawing Large Graphs with a Potential-Field-Based Multilevel Algorithm
260 Citations2005Stefan Hachul, Michael Jünger
A new force-directed graph drawing method that is based on a combination of an efficient multilevel scheme and a strategy for approximating the repulsive forces in the system by rapidly evaluating potential fields is presented.
Journal of Molecular BiologyLGL: Creating a Map of Protein Function with an Algorithm for Visualizing Very Large Biological Networks
217 Citations2004Alex Adai, Shailesh V. Date +2 more
An algorithm, called large graph layout (LGL), which can be used to dynamically visualize large networks on the order of hundreds of thousands of vertices and millions of edges, and is demonstrated in visualizing an extensive protein map summarizing the results of approximately 21 billion sequence comparisons between 145579 proteins from 50 genomes.
Lecture notes in computer scienceA Multilevel Algorithm for Force-Directed Graph Drawing
179 Citations2001Chris Walshaw
A heuristic method for drawing graphs which uses a multilevel technique combined with a force-directed placement algorithm which can compute both 2 & 3 dimensional layouts and is also very fast.
Journal of Graph Algorithms and ApplicationsA Fast Multi-Scale Method for Drawing Large Graphs
167 Citations2002David Harel, Yehuda Koren
Lecture notes in computer scienceFADE: Graph Drawing, Clustering, and Visual Abstraction
163 Citations2001Aaron Quigley, Peter Eades
A fast algorithm for the 2D drawing, geometric clustering and multilevel viewing of large undirected graphs is presented and the decomposition tree provides a mechanism to view the hierarchical clustering on various levels of abstraction.
Lecture notes in computer scienceAn Energy Model for Visual Graph Clustering
145 Citations2004Andreas Noack
An energy model whose minimum energy drawings reveal the clusters of the drawn graph is introduced, and this characterization shows in what sense the drawings separate clusters, and how the distance of separated clusters to the other nodes can be interpreted.
Journal of the American Society for Information Science and TechnologyDomain visualization using VxInsight® for science and technology management
143 Citations2002Kevin W. Boyack, Brian Wylie +1 more
The application of the knowledge visualization tool, VxInsight, is presented to enable domain analysis for science and technology management within the enterprise to enable quick and powerful analysis of the resulting landscapes.
Proceedings of the National Academy of SciencesMapping knowledge domains: Characterizing PNAS
140 Citations2004Kevin W. Boyack
By using funding source information and citation counts, it is shown that, on an aggregate basis, papers funded jointly by the U.S. Public Health Service and non-U.s. government sources outperform papers funded by other sources.
Journal of Intelligent Information SystemsKnowledge Mining With VxInsight: Discovery Through Interaction
126 Citations1998George S. Davidson, Bruce Hendrickson +3 more
A set of properties that such a presentation should have is discussed, and the design and functionality of VxInsight, a visualization tool built to these principles are described.
IEEE Transactions on Visualization and Computer GraphicsMulti-Level Graph Layout on the GPU
110 Citations2007Y. Frishman, Ayellet Tal
This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures and an application for visualization of the topologies of ISP (Internet service provider) networks is presented.
ScientometricsUsing detailed maps of science to identify potential collaborations
86 Citations2008Kevin W. Boyack
The utility of the method is shown in two different applications: identifying specific potential collaborations at the author level between two institutions, and generating an index that can be used for strategic planning purposes.
Cluster stability and the use of noise in interpretation of clustering
76 Citations2005George S. Davidson, Brian Wylie +1 more
A clustering and ordination algorithm suitable for mining extremely large databases, including those produced by microarray expression studies, is described and analyzed for stability.
Informatik - Forschung und EntwicklungDrawing Subway Maps: A Survey
61 Citations2007Alexander Wolff
A list of rules that should be adhered to by a good subway map, and evidence why drawing good subway maps is difficult (even without labels).
Lecture notes in computer scienceRapid Multipole Graph Drawing on the GPU
46 Citations2009Apeksha Godiyal, Jared Hoberock +2 more
A new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation, using a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout.
Genome ResearchComparative Analysis of Multiple Genome-Scale Data Sets
31 Citations2002Margaret Werner‐Washburne, Brian Wylie +5 more
The use of novel tools for both visualization and data set comparison to analyze yeast gene-expression and protein-interaction studies led to new insights about each data set, indicating that for both data sets, the identification of false-positive interactions may be lower than previously thought.
Graph Drawing Tools for Bioinformatics Research: An Overview
4 Citations2006Kay C. Wiese, Cory Eicher
The specific purpose for the research was to investigate the applicability of existing graph drawing tools for visualization of very large phylogenetic trees.