Drawing graphs by eigenvectors: theory and practice

The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Two important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. In this paper, we explore spectral visualization techniques and study their properties from different points of view. We also suggest a novel algorithm for calculating spectral layouts resulting in an extremely fast computation by optimizing the layout within a small vector space.     

Techniques for Edge Stratification of Complex Graph Drawings

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings.     

Tiling, block data layout, and memory hierarchy performance

Recently, several experimental studies have been conducted on block data layout in conjunction with tiling as a data transformation technique to improve cache performance. In this paper, we analyze cache and translation look-aside buffer (TLB) performance of such alternate layouts (including block data layout and Morton layout) when used in conjunction with tiling. We derive a tight lower bound on TLB performance for standard matrix access patterns, and show that block data layout and Morton layout achieve this bound. To improve cache performance, block data layout is used in concert with tiling. Based on the cache and TLB performance analysis, we propose a data block size selection algorithm that finds a tight range for optimal block size. To validate our analysis, we conducted simulations and experiments using tiled matrix multiplication, LU decomposition, and Cholesky factorization. For matrix multiplication, simulation results using UltraSparc II parameters show that tiling and block data layout with a block size given by our block size selection algorithm, reduces up to 93 percent of TLB misses compared with other techniques. The total miss cost is reduced considerably. Experiments on several platforms show that tiling with block data layout achieves up to 50 percent performance improvement over other techniques that use conventional layouts. Morton layout is also analyzed and compared with block data layout. Experimental results show that matrix multiplication using block data layout is up to 15 percent faster than that using Morton data layout.     

An evaluation of multimodal interaction techniques for 3D layout constraint solver in a desktop-based virtual environment

We propose a new approach to the 3D layout problems based on the integration of constraint programming and virtual reality interaction techniques. Our method uses an open-source constraint solver integrated in a popular 3D game engine. We designed multimodal interaction techniques for the system, based on gesture and voice input. We conducted a user study with an interactive task of laying out room furniture to compare and evaluate the mono- and multimodal interaction techniques. Results showed that voice command provided the best performance and was most preferred by participants, based on the analysis of both objective and subjective data. Results also revealed that there was no significant difference between the voice and multimodal input (voice and gesture). Our original approach opens the way to multidisciplinary theoretical work and promotes the development of high-level applications for the VR applications.     

Interaction Techniques for Selecting and Manipulating Subgraphs in Network Visualizations

We present a novel and extensible set of interaction techniques for manipulating visualizations of networks by selecting subgraphs and then applying various commands to modify their layout or graphical properties. Our techniques integrate traditional rectangle and lasso selection, and also support selecting a node's neighbourhood by dragging out its radius (in edges) using a novel kind of radial menu. Commands for translation, rotation, scaling, or modifying graphical properties (such as opacity) and layout patterns can be performed by using a hotbox (a transiently popped-up, semi-transparent set of widgets) that has been extended in novel ways to integrate specification of commands with 1D or 2D arguments. Our techniques require only one mouse button and one keyboard key, and are designed for fast, gestural, in-place interaction. We present the design and integration of these interaction techniques, and illustrate their use in interactive graph visualization. Our techniques are implemented in NAViGaTOR, a software package for visualizing and analyzing biological networks. An initial usability study is also reported.     

Quasidynamic layout optimizations for improving data locality

Compiler-directed locality optimization techniques are effective in reducing the number of cycles spent in off-chip memory accesses. Recently, methods have been developed that transform memory layouts of data structures at compile-time to improve spatial locality of nested loops beyond current control-centric (loop nest-based) optimizations. Most of these data-centric transformations use a single static (program-wide) memory layout for each array. A disadvantage of these static layout-based locality enhancement strategies is that they might fail to optimize codes that manipulate arrays, which demand different layouts in different parts of the code. We introduce a new approach, which extends current static layout optimization techniques by associating different memory layouts with the same array in different parts of the code. We call this strategy "quasidynamic layout optimization." In this strategy, the compiler determines memory layouts (for different parts of the code) at compile time, but layout conversions occur at runtime. We show that the possibility of dynamically changing memory layouts during the course of execution adds a new dimension to the data locality optimization problem. Our strategy employs a static layout optimizer module as a building block and, by repeatedly invoking it for different parts of the code, it checks whether runtime layout modifications bring additional benefits beyond static optimization. Our experiments indicate significant improvements in execution time over static layout-based locality enhancing techniques.     

Automatic metro map layout using multicriteria optimization

This paper describes an automatic mechanism for drawing metro maps. We apply multicriteria optimization to find effective placement of stations with a good line layout and to label the map unambiguously. A number of metrics are defined, which are used in a weighted sum to find a fitness value for a layout of the map. A hill climbing optimizer is used to reduce the fitness value, and find improved map layouts. To avoid local minima, we apply clustering techniques to the map-the hill climber moves both stations and clusters when finding improved layouts. We show the method applied to a number of metro maps, and describe an empirical study that provides some quantitative evidence that automatically-drawn metro maps can help users to find routes more efficiently than either published maps or undistorted maps. Moreover, we have found that, in these cases, study subjects indicate a preference for automatically-drawn maps over the alternatives.     

SmallWorlds: Visualizing Social Recommendations

We present SmallWorlds, a visual interactive graph‐based interface that allows users to specify, refine and build item‐preference profiles in a variety of domains. The interface facilitates expressions of taste through simple graph interactions and these preferences are used to compute personalized, fully transparent item recommendations for a target user. Predictions are based on a collaborative analysis of preference data from a user's direct peer group on a social network. We find that in addition to receiving transparent and accurate item recommendations, users also learn a wealth of information about the preferences of their peers through interaction with our visualization. Such information is not easily discoverable in traditional text based interfaces. A detailed analysis of our design choices for visual layout, interaction and prediction techniques is presented. Our evaluations discuss results from a user study in which SmallWorlds was deployed as an interactive recommender system on Facebook.     

Architectural investigation of matrix data layout on multicore processors

Many practical applications include matrix operations as essential procedures. In addition, recent studies of matrix operations rely on parallel processing to reduce any calculation delays. Because these operations are highly data intensive, many studies have investigated work distribution techniques and data access latency to accelerate algorithms. However, previous studies have not considered hardware architectural features adequately, although they greatly affect the performance of matrix operations. Thus, the present study considers the architectural characteristics that affect the performance of matrix operations on real multicore processors. We use matrix multiplication, LU decomposition, and Cholesky factorization as the test applications, which are well-known data-intensive mathematical algorithms in various fields. We argue that applications only access matrices in a particular direction, and we propose that the canonical data layout is the optimal matrix data layout compared with the block data layout. In addition, the tiling algorithm is utilized to increase the temporal data locality in multilevel caches and to balance the workload as evenly as possible in multicore environments. Our experimental results show that applications using the canonical data layout with tiling have an 8.23% faster execution time and 3.91% of last level cache miss rate compared with applications executed with the block data layout.     

MultiClusterTree: Interactive Visual Exploration of Hierarchical Clusters in Multidimensional Multivariate Data

Visual analytics of multidimensional multivariate data is a challenging task because of the difficulty in understanding metrics in attribute spaces with more than three dimensions. Frequently, the analysis goal is not to look into individual records but to understand the distribution of the records at large and to find clusters of records with similar attribute values. A large number of (typically hierarchical) clustering algorithms have been developed to group individual records to clusters of statistical significance. However, only few visualization techniques exist for further exploring and understanding the clustering results. We propose visualization and interaction methods for analyzing individual clusters as well as cluster distribution within and across levels in the cluster hierarchy. We also provide a clustering method that operates on density rather than individual records. To not restrict our search for clusters, we compute density in the given multidimensional multivariate space. Clusters are formed by areas of high density. We present an approach that automatically computes a hierarchical tree of high density clusters. To visually represent the cluster hierarchy, we present a 2D radial layout that supports an intuitive understanding of the distribution structure of the multidimensional multivariate data set. Individual clusters can be explored interactively using parallel coordinates when being selected in the cluster tree. Furthermore, we integrate circular parallel coordinates into the radial hierarchical cluster tree layout, which allows for the analysis of the overall cluster distribution. This visual representation supports the comprehension of the relations between clusters and the original attributes. The combination of the 2D radial layout and the circular parallel coordinates is used to overcome the overplotting problem of parallel coordinates when looking into data sets with many records. We apply an automatic coloring scheme based on the 2D radial layout of the hierarchical cluster tree encoding hue, saturation, and value of the HSV color space. The colors support linking the 2D radial layout to other views such as the standard parallel coordinates or, in case data is obtained from multidimensional spatial data, the distribution in object space.     

Smashing peacocks further: drawing quasi-trees from biconnected components

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data     

Sizing and layout design of truss structures under dynamic and static constraints with an integrated particle swarm optimization algorithm

Natural frequencies offer useful knowledge on the dynamic response of the structures. It is possible to avoid from the destructive effects of dynamic loads on the structures by optimizing layout and size of their subject to constraints on natural frequencies. Since optimization problems including frequency constraints are highly nonlinear, this kind of problems forms a challenging area to test the performance of the different optimization techniques. This study tests the performance of an integrated particle swarm optimization algorithm (iPSO), a new particle swarm optimizer integrated with the improved fly-back mechanism and the weighted particle concept, in four weight minimization of truss structures with sizing and layout variables under multiple frequency constraints. Optimization results demonstrate that the new algorithm is competitive with other state-of-the-art metaheuristic algorithms in dynamic and static structural optimization problems.     

An experimental evaluation of I/O optimizations on different applications

Many large scale applications have significant I/O requirements as well as computational and memory requirements. Unfortunately, the limited number of I/O nodes provided in a typical configuration of the modern message-passing distributed-memory architectures such as Intel Paragon and IBM SP-2 limits the I/O performance of these applications severely. We examine some software optimization techniques and evaluate their effects in five different I/O-intensive codes from both small and large application domains. Our goals in this study are twofold. First, we want to understand the behavior of large-scale data-intensive applications and the impact of I/O subsystems on their performance and vice versa. Second, and more importantly, we strive to determine the solutions for improving the applications' performance by a mix of software techniques. Our results reveal that different applications can benefit from different optimizations. For example, we found that some applications benefit from file layout optimizations whereas others take advantage of collective I/O. A combination of architectural and software solutions is normally needed to obtain good I/O performance. For example, we show that with a limited number of I/O resources, it is possible to obtain good performance by using appropriate software optimizations. We also show that beyond a certain level, imbalance in the architecture results in performance degradation even when using optimized software, thereby indicating the necessity of an increase in I/O resources.     

The Perception of Graph Properties in Graph Layouts

When looking at drawings of graphs, questions about graph density, community structures, local clustering and other graph properties may be of critical importance for analysis. While graph layout algorithms have focused on minimizing edge crossing, symmetry, and other such layout properties, there is not much known about how these algorithms relate to a user's ability to perceive graph properties for a given graph layout. In this study, we apply previously established methodologies for perceptual analysis to identify which graph drawing layout will help the user best perceive a particular graph property. We conduct a large scale (n = 588) crowdsourced experiment to investigate whether the perception of two graph properties (graph density and average local clustering coefficient) can be modeled using Weber's law. We study three graph layout algorithms from three representative classes (Force Directed ‐ FD, Circular, and Multi‐Dimensional Scaling ‐ MDS), and the results of this experiment establish the precision of judgment for these graph layouts and properties. Our findings demonstrate that the perception of graph density can be modeled with Weber's law. Furthermore, the perception of the average clustering coefficient can be modeled as an inverse of Weber's law, and the MDS layout showed a significantly different precision of judgment than the FD layout.     

A graph grammar‐based approach for graph layout

As a two‐dimensional formal tool, graph grammars are capable of handling the layout problems of visual programming languages. Based on an edge‐based graph grammar (EGG), this paper proposes a novel layout approach that uses the unique features of EGG and overcomes the weakness of existing layout approaches. In order to make the approach rigorous yet concise, the graph grammar mechanisms with layout constraints and quantitative analysis techniques are combined together as an integrity. First, the basic notions of EGG are briefly introduced; second, the layout approach is presented that consists of two phases, ie, bottom‐up parsing and top‐down derivation. Finally, a case study is given by taking the standard flowchart as an example to demonstrate the working process of the proposed approach.     

The effect of the descent technique and truck cabin layout on the landing impact forces

The majority of injuries to truckers are caused by falls during the descent from the cab of the truck. Several studies have shown that the techniques used to descend from the truck and the layout of the truck's cabin are the principal cause of injury. The goal of the present study was to measure the effects of the descent techniques used by the trucker and the layout of the truck's cabin on the impact forces absorbed by the lower limbs and the back. Kinematic data, obtained with the aid of a video camera, were combined with the force platform data to allow for calculation of the lower limb and L₅–S₁ torques as well as L₅–S₁ compressive forces. The trucker descended from two different conventional tractor cabin layouts. Each trucker descended from cabin using either “facing the truck” (FT) or “back to the truck” (BT) techniques. The results demonstrate that the BT technique produces greater ground impact forces than the FT technique, particularly when the truck does not have a handrail. The BT technique also causes an increase in the compressive forces exerted on the back. In conclusion, the use of the FT technique along with the aids (i.e., handrails and all the steps) help lower the landing impact forces as well as the lumbosacral compressive forces.     

Graph Layouts by t‐SNE

We propose a new graph layout method based on a modification of the t‐distributed Stochastic Neighbor Embedding (t‐SNE) dimensionality reduction technique. Although t‐SNE is one of the best techniques for visualizing high‐dimensional data as 2D scatterplots, t‐SNE has not been used in the context of classical graph layout. We propose a new graph layout method, tsNET, based on representing a graph with a distance matrix, which together with a modified t‐SNE cost function results in desirable layouts. We evaluate our method by a formal comparison with state‐of‐the‐art methods, both visually and via established quality metrics on a comprehensive benchmark, containing real‐world and synthetic graphs. As evidenced by the quality metrics and visual inspection, tsNET produces excellent layouts.     

基于自适应光标的图形用户界面输入效率优化

提高图形用户界面(graphical user interface)的输入效率,是人机交互中的一项重要研究内容.已有的研究包括点击增强技术和自适应界面技术,前者改变光标的控制方式或呈现方式,后者改变界面上控件的位置布局,但两种技术都存在不足.通过分析界面操作,提出了图形用户界面输入效率的评价模型;然后,在此基础上提出一种人机交互效率优化技术:自适应光标.它以自适应的方式,有选择地对界面上用户可能访问的控件通过点击增强技术支持,实现快速访问.该方法既解决了以往的自适应界面技术因频繁调整控件布局而给用户带来额外认知成本的问题,也克服了点击增强技术仅适用于稀疏控件布局的限制.为了检验其可用性,在控件较多的Visual Studio上实现了自适应光标技术.实验结果表明,使用自适应光标技术可以将获取目标的时间缩短27.7％,显著提高了图形用户界面的输入效率.     

An expert system to generate associativity data for layout design

In this paper we present an intelligent system which assists the layout designer in producing associativity data as input to an automated layout generation tool. The approach which we adopt combines techniques based on expert systems, object-based data structures and cluster analysis. The system eliminates manual input for the associativity data. The object data structure assures data consistency. The cluster analysis determines the strength of relationship between any two pieces of equipment. The expert system provides guidance for the subjective part of the layout design. This results in automation of associativity data generation, an improved user interface, and consistency and accuracy of data. The concept is illustrated by an example taken from the petrochemical industry.