Constrained Graph Layout

Most current graph layout technology does not lend itself to interactive applications such as animation or advanced user interfaces. We introduce the constrained graph layout model which is better suited for interactive applications. In this model, input to the layout module includes suggested positions for nodes and constraints over the node positions in the graph to be laid out. We describe four implementations of layout modules which are based on the constrained graph layout model. The first three implementations are for undirected graph layout while the fourth is for tree layout. The implementations use active set techniques to solve the layout. Our empirical evaluation shows that they are quite fast and give reasonable layout.     

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.     

一种支持超视频创建与可视呈现的草图界面技术

超视频打破了传统视频的单一线性的组织和浏览方式,有效地增强了用户的浏览效率和视频信息的表达能力.基于草图和草图界面在思维表达上的优势,针对目前对视频内容以及视频间或者视频内的关系展示上的不足,提出了一种支持超视频创建的草图界面来直观地表达用户的设计意图,改善了视频编辑过程中的交互体验.提出了一种基于force-directed 的图布局算法.该算法对视频语义进行建模,将时间、空间、视频结构、约束关系等语义信息融入到节点质量、引力和斥力等对象中.系统实例表明,该方法能够很好地适应视频特有的语义类型,表示出超视频的动态创建和编辑过程.     

An approach to automatic display layout using combinatorial optimization algorithms

The introduction of automatic display layout (ADL), i.e. the automatic placing and sizing of windows in a window-oriented graphical user interface, is a major contribution towards an improved user interface. Our approach to ADL is to treat this problem as a combinatorial optimization problem. In this article we describe the concepts we used for implementing an experimental system which controls the computer screen contents and its layout. We give two examples of different standard applications into which we included ADL successfully, namely hypertext for a window layout problem and graph-browser for a hierarchical graph layout problem within a particular window. The results show that automatic (and tool independent) display layout will be possible in the near future even in an interactive environment.     

一种用于Marching-Graph图形绘制的快速收敛布局算法

Marching-Graph是一种将图形隐喻技术和空间隐喻技术集成为一体的新的可视化方法.它为用户提供了高度可交互性地图,使用户可访问那些具有地理属性的信息的逻辑结构.它通过有效的人图交互和跨空间浏览为用户提供了一种可视分析和挖掘未知信息的机制,而不是将已知的信息呈现在地图上.然而,传统的力导向布局算法在达到力量均衡配置方面非常慢.为使一个图形布局收敛,它们通常需花费几十秒的时间.因此。当用户快速行进于地理区间时,那些力导向布局算法就不能满足快速绘制一系列图形的要求.提出了一种快速收敛布局方法,当用户在Marching-Graph中通过力导向布局逐步探究一系列图形时,它可以加速交互时间.通过结合辐射树绘图技术和力导向图形绘制方法来取得能量最小化的快速收敛.     

RailwayDB: adaptive storage of interaction graphs

We are living in an ever more connected world, where data recording the interactions between people, software systems, and the physical world is becoming increasingly prevalent. These data often take the form of a temporally evolving graph, where entities are the vertices and the interactions between them are the edges. We call such graphs interaction graphs. Various domains, including telecommunications, transportation, and social media, depend on analytics performed on interaction graphs. The ability to efficiently support historical analysis over interaction graphs requires effective solutions for the problem of data layout on disk. This paper presents an adaptive disk layout called the railway layout for optimizing disk block storage for interaction graphs. The key idea is to divide blocks into one or more sub-blocks. Each sub-block contains the entire graph structure, but only a subset of the attributes. This improves query I/O, at the cost of increased storage overhead. We introduce optimal integer linear program (ILP) formulations for partitioning disk blocks into sub-blocks with overlapping and nonoverlapping attributes. Additionally, we present greedy heuristics that can scale better compared to the ILP alternatives, yet achieve close to optimal query I/O. We provide an implementation of the railway layout as part of RailwayDB—an open-source graph database we have developed. To demonstrate the benefits of the railway layout, we provide an extensive experimental evaluation, including model-based as well as empirical results comparing our approach to baseline alternatives.     

Design and evaluation of MagnetViz—a graph visualization tool

MagnetViz was designed for the interactive manipulation of force-directed graph layouts, allowing the user to obtain visualizations based on the graph topology and/or the attributes of its nodes and edges. The user can introduce virtual magnets anywhere in the graph and these can be set to attract nodes and edges that fulfill user-defined criteria. When a magnet is placed, the force-directed nature of the layout forces it to reorganize itself in order to reflect the changes in the balance of forces, consequently changing the visualization into one that is more semantically relevant to the user. This paper describes MagnetViz’s concepts, illustrating them with examples and a case study based on a usage scenario. We also describe how the MagnetViz has evolved since its original version and present the evaluation of its latest version. This evaluation consists of two user studies aiming at assessing generated layout quality and how well the concepts can be apprehended and employed, and a task taxonomy assessment focusing on establishing which graph visualization tasks the technique is able to handle.     

A Comparison of User-Generated and Automatic Graph Layouts

The research presented in this paper compares user-generated and automatic graph layouts. Following the methods suggested by van Ham et al. (2008), a group of users generated graph layouts using both multi-touch interaction on a tabletop display and mouse interaction on a desktop computer. Users were asked to optimize their layout for aesthetics and analytical tasks with a social network. We discuss characteristics of the user-generated layouts and interaction methods employed by users in this process. We then report on a web-based study to compare these layouts with the output of popular automatic layout algorithms. Our results demonstrate that the best of the user-generated layouts performed as well as or better than the physics-based layout. Orthogonal and circular automatic layouts were found to be considerably less effective than either the physics-based layout or the best of the user-generated layouts. We highlight several attributes of the various layouts that led to high accuracy and improved task completion time, as well as aspects in which traditional automatic layout methods were unsuccessful for our tasks.     

Video Brush: A Novel Interface for Efficient Video Cutout

We present Video Brush, a novel interface for interactive video cutout. Inspired by the progressive selection scheme in images, our interface is designed to select video objects by painting on successive frames as the video plays. The video objects are progressively selected by solving the graph‐cut based local optimization according to the strokes drawn by the brush on each painted frame. In order to provide users interactive feedback, we accelerate 3D graph‐cut by efficient graph building and multi‐level banded graph‐cut. Experimental results show that our novel interface is both intuitive and efficient for video cutout.     

支持界面生成的扩展对象模型和交互模型

基于模型的用户界面分析和表达是实现界面工程设计的出路所在。FMP是一个涵盖需求、结构和实现的界面模型。该文重点讨论了FMP的内在模型Model部分和对界面实现的作用。指出内在模型由参与界面操作的扩充对象模型和它们的交互模型构成。对象模型给出了界面的局部布局。交互模型给出了界面的功能和对象构成以及它们之间的交互关系,在界面模板的支持下,可以给出界面的宏观布局并支持界面的自动生成。     

MING-I: a distributed interactive multimedia document development mechanism

The next generation of interactive multimedia documents can contain both static media, e.g., text, graph, image, and continuous media, e.g., audio and video, and can provide user interactions in distributed environments. However, the temporal information of multimedia documents cannot be described using traditional document structures, e.g., Open Document Architecture (ODA) and Standard Generalized Mark-up Language (SGML); the continuous transmission of media units also raises some new synchronization problems, which have not been met before, for processing user interactions. Thus, developing a distributed interactive multimedia document system should resolve the issues of document model, presentation control architecture, and control scheme. In this paper, we (i) propose a new multimedia document model that contains the logical structure, the layout structure, and the temporal structure to formally describe multimedia documents, and (ii) point out main interaction-based synchronization problems, and propose a control architecture and a token-based control scheme to solve these interaction-based synchronization problems. Based on the proposed document model, control architecture, and control scheme, a distributed interactive multimedia document development mechanism, which is called MING-I, is developed on SUN workstations.     

Time-varying contour topology

The contour tree has been used to compute the topology of isosurfaces, generate a minimal seed set for accelerated isosurface extraction, and provide a user interface to segment individual contour components in a scalar field. In this paper, we extend the benefits of the contour tree to time-varying data visualization. We define temporal correspondence of contour components and describe an algorithm to compute the correspondence information in time-dependent contour trees. A graph representing the topology changes of time-varying isosurfaces is constructed in real-time for any selected isovalue using the precomputed correspondence information. Quantitative properties, such as surface area and volume of contour components, are computed and labeled on the graph. This topology change graph helps users to detect significant topological and geometric changes in time-varying isosurfaces. The graph is also used as an interactive user interface to segment, track, and visualize the evolution of any selected contour components over time.     

Dynamic visualization of coexpression in systems genetics data

Biologists hope to address grand scientific challenges by exploring the abundance of data made available through modern microarray technology and other high-throughput techniques. The impact of this data, however, is limited unless researchers can effectively assimilate such complex information and integrate it into their daily research; interactive visualization tools are called for to support the effort. Specifically, typical studies of gene co-expression require novel visualization tools that enable the dynamic formulation and fine-tuning of hypotheses to aid the process of evaluating sensitivity of key parameters. These tools should allow biologists to develop an intuitive understanding of the structure of biological networks and discover genes residing in critical positions in networks and pathways. By using a graph as a universal representation of correlation in gene expression, our system employs several techniques that when used in an integrated manner provide innovative analytical capabilities. Our tool for interacting with gene co-expression data integrates techniques such as: graph layout, qualitative subgraph extraction through a novel 2D user interface, quantitative subgraph extraction using graph-theoretic algorithms or by compound queries, dynamic level-of-detail abstraction, and template-based fuzzy classification. We demonstrate our system using a real-world workflow from a large-scale, systems genetics study of mammalian gene co-expression.     

基于K-means和图割的脑部MRI分割算法

为了克服原始图割算法在用户选定的像素种子点较少情况下,目标边界容易出现错分这一现象,本文提出了基于K-means和图割(Graph cut,GC)算法相结合的交互式K-均值图割（K-means and graph cut,KMGC）算法,对脑部核磁共振图像（Magnetic resonance image,MRI） 进行交互式操作,该算法通过K-means聚类,对脑部MRI的灰度不均匀性进行了处理,在此基础上,再使用图割算法进一步对脑部MRI进行细化,从而达到有效地分割脑白质和脑 灰质的目的。本文分别在仿真和真实的脑部MRI数据上进行了大量的实验,分别从定量分析和定性分析两个角度对实验结果进行了分析,并与其他分割算法进行了对比,对比实验结果标明,KMGC算法能够有效地对脑部MRI进行分割,并在分割效果上优于其他算法。     

电子纸显示控制器S1D13521的人机交互设计

新型电子纸显示控制器SID13521的推出,为提升电子纸显示屏人机界面体验带来了强大技术支持。结合SID13521诸多新特性,本文建立一种控制一反馈人机交互结构模型,在此基础上设计了电子纸人机交互基本操控手势及界面布局,并通过动态视觉反馈设计提升交互体验。经在津科V30型手持阅读器上验证,该设计简便易行、效果良好。     

Finding strongly connected components in distributed graphs

The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.     

基于超图的关联规则可视化方法*

针对传统的关联规则可视化方法缺乏多模式关联规则展现形式、无法展示关联规则的内部信息以及分布情况、属性值重要程度突出不明显等问题,提出了基于超图的关联规则表示方法。首先,基于超图中BF-超边基础理论,给出了BF规则图的定义,并且设计了基于超图的一对一、一对多、多对一、多对多关联规则表示原型;接着,结合“沙漏”结构,设计了基于超图的关联规则可视化布局算法;然后,基于交互理论及其相关技术,设计并实现了交互式关联规则可视化系统。最后,以某省全员人口数据为基础,对算法进行了具体实现和分析。实验结果表明,所提出的可视化形式和已有成果相比具有良好的展现效果。     

Ambiguity-free edge-bundling for interactive graph visualization

Graph visualization has been widely used to understand and present both global structural and local adjacency information in relational data sets (e.g., transportation networks, citation networks, or social networks). Graphs with dense edges, however, are difficult to visualize because fast layout and good clarity are not always easily achieved. When the number of edges is large, edge bundling can be used to improve the clarity, but in many cases, the edges could be still too cluttered to permit correct interpretation of the relations between nodes. In this paper, we present an ambiguity-free edge-bundling method especially for improving local detailed view of a complex graph. Our method makes more efficient use of display space and supports detail-on-demand viewing through an interactive interface. We demonstrate the effectiveness of our method with public coauthorship network data.     

Scalable, Versatile and Simple Constrained Graph Layout

We describe a new technique for graph layout subject to constraints. Compared to previous techniques the proposed method is much faster and scalable to much larger graphs. For a graph with n nodes, m edges and c constraints it computes incremental layout in time O ( n log n + m + c ) per iteration. Also, it supports a much more powerful class of constraint: inequalities or equalities over the Euclidean distance between nodes. We demonstrate the power of this technique by application to a number of diagramming conventions which previous constrained graph layout methods could not support. Further, the constraint-satisfaction method—inspired by recent work in position-based dynamics—is far simpler to implement than previous methods.