Augmenting Node-Link Diagrams with Topographic Attribute Maps

We propose a novel visualization technique for graphs that are attributed with scalar data. In many scenarios, these attributes (e.g., birth date in a family network) provide ambient context information for the graph structure, whose consideration is important for different visual graph analysis tasks. Graph attributes are usually conveyed using different visual representations (e.g., color, size, shape) or by reordering the graph structure according to the attribute domain (e.g., timelines). While visual encodings allow graphs to be arranged in a readable layout, assessing contextual information such as the relative similarities of attributes across the graph is often cumbersome. In contrast, attribute-based graph reordering serves the comparison task of attributes, but typically strongly impairs the readability of the structural information given by the graph's topology. In this work, we augment force-directed node-link diagrams with a continuous ambient representation of the attribute context. This way, we provide a consistent overview of the graph's topological structure as well as its attributes, supporting a wide range of graph-related analysis tasks. We resort to an intuitive height field metaphor, illustrated by a topographic map rendering using contour lines and suitable color maps. Contour lines visually connect nodes of similar attribute values, and depict their relative arrangement within the global context. Moreover, our contextual representation supports visualizing attribute value ranges associated with graph nodes (e.g., lifespans in a family network) as trajectories routed through this height field. We discuss how user interaction with both the structural and the contextual information fosters exploratory graph analysis tasks. The effectiveness and versatility of our technique is confirmed in a user study and case studies from various application domains.     

Algorithms for Extracting Correct Critical Points and Constructing Topological Graphs from Discrete Geographical Elevation Data

Researchers in the fields of computer graphics and geographical information systems (GISs) have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition.     

基于因子图模型的动态图半监督聚类算法

针对动态图的聚类主要存在着两点不足:首先, 现有的经典聚类算法大多从静态图分析的角度出发, 无法对真实网络图持续演化的特性进行有效建模, 亟待对动态图的聚类算法展开研究, 通过对不同时刻图快照的聚类结构进行分析进而掌握图的动态演化情况.其次, 真实网络中可以预先获取图中部分节点的聚类标签, 如何将这些先验信息融入到动态图的聚类结构划分中, 从而向图中的未标记节点分配聚类标签也是本文需要解决的问题.为此, 本文提出进化因子图模型(Evolution factor graph model, EFGM)用于解决动态图节点的半监督聚类问题, 所提EFGM不仅可以捕获动态图的节点属性和边邻接属性, 还可以捕获节点的时间快照信息.本文对真实数据集进行实验验证, 实验结果表明EFGM算法将动态图与先验信息融合到一个统一的进化因子图框架中, 既使得聚类结果满足先验知识, 又契合动态图的整体演化规律, 有效验证了本文方法的有效性.     

IEH graphs

We propose a new family of interconnection topology that can be used to design communication architecture for distributed systems with an arbitrary number of computing nodes. The design is based on a novel generalization of the well known hypercube graphs. The proposed topology is shown to be incrementally extensible in steps of 1 (cost of restructuring or adding edges is very low), optimally fault tolerant and its diameter is logarithmic in the number of nodes. Moreover, for any given number of nodes, the difference of the maximum and the minimum degree of a node in the graph is ≤1, i.e., the graph is almost regular. A shortest routing algorithm for the proposed family of graphs has been developed.     

One-to-Many Embeddings of Hypercubes into Cayley Graphs Generated by Reversals

Among Cayley graphs on the symmetric group, some that have a noticeably low diameter relative to the degree of regularity are examples such as the ``star' network and the ``pancake' network, the latter a representative of a variety of Cayley graphs generated by reversals. These diameter and degree conditions make these graphs potential candidates for parallel computation networks. Thus it is natural to investigate how well they can simulate other standard parallel networks, in particular hypercubes. For this purpose, constructions have previously been given for low dilation embeddings of hypercubes into star networks. Developing this theme further, in this paper we construct especially low dilation maps (e.g., with dilation 1, 2, 3, or 4) of hypercubes into pancake networks and related Cayley graphs generated by reversals. Whereas obtaining such results by the use of ``traditional' graph embeddings (i.e., one-to-one or many-to-one embeddings) is sometimes difficult or impossible, we achieve many of these results by using a nontraditional simulation technique known as a ``one-to-many' graph embedding. That is, in such embeddings we allow each vertex in the guest (i.e., domain) graph to be associated with some nonempty subset of the vertex set of the host (i.e., range) graph, these subsets satisfying certain distance and connection requirements which make the simulation possible. Received July 30, 1997, and in revised form July 18, 2001. Online publication October 30, 2001.     

Network mining: Applications to business data

This research addresses the problem of analyzing the temporal dynamics of business organizations. In particular, we concentrate on inferring the related businesses, i.e., are there groups of companies that are highly correlated through some measurement (metric)? We argue that business relationships derived from general literature (i.e., newspaper articles, news items etc.) may help us create a network of related companies (business networks). On the other hand, relative movement of stock prices can give us an indication of related companies (asset graphs). We also expect to see some relationships between these two kinds of networks. We adapt the asset graph construction approach from the literature for our asset graph implementations, and then, define our methodology for business network construction. Finally, an introduction to the exploration of some relationships between the asset graphs and business networks is presented.     

State agnostic planning graphs: deterministic,non-deterministic,and probabilistic planning

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source.We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i.e., search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.     

Achieving Integrity in Geographic Information Systems—Maps and Nested Maps

This article provides a formal data model which allows to establish geometrical-topological integrity of areal objects in a geographical information system (GIS). The data model leads to an automatic tool able to check consistency of a given set of data and to avoid inconsistencies caused by updates of the database. To this end we start from the mathematical notion of a map which provides an irregular tessellation, i.e., a partition of the plane which is non-overlapping and covering. From another perspective, a map is a plane graph with an explicit representation of faces as its atomic areal components. The concept of nested maps extends this standard notion by the specification of a hierarchical structure which aggregates the set of faces. Such aggregations are common in political and administrative structures. Whereas the mathematical notion of a map is familiar in GIS and the base for many tools supporting topological editing, there was a lack of effectively checkable integrity constraints which are correct and complete, i.e., equivalent, for maps. This article provides an axiomatic, effectively checkable characterization of maps which is equivalent to the standard mathematical one, extends it to nested maps and discusses how to use them in order to achieve and maintain integrity in a GIS.     

Graph embeddings and simplicial maps

An undirected graph is viewed as a simplicial complex. The notion of a graph embedding of a guest graph in a host graph is generalized to the realm of simplicial maps. Dilation is redefined in this more general setting. Lower bounds on dilation for various guest and host graphs are considered. Of particular interest are graphs that have been proposed as communication networks for parallel architectures. Bhattet al. provide a lower bound on dilation for embedding a planar guest graph in a butterfly host graph. Here, this lower bound is extended in two directions. First, a lower bound that applies to arbitrary guest graphs is derived, using tools from algebraic topology. Second, this lower bound is shown to apply to arbitrary host graphs through a new graph-theoretic measure, called bidecomposability. Bounds on the bidecomposability of the butterfly graph and of thek-dimensional torus are determined. As corollaries to the main lower-bound theorem, lower bounds are derived for embedding arbitrary planar graphs, genusg graphs, andk-dimensional meshes in a butterfly host graph.     

Nested Tracking Graphs

Tracking graphs are a well established tool in topological analysis to visualize the evolution of components and their properties over time, i.e., when components appear, disappear, merge, and split. However, tracking graphs are limited to a single level threshold and the graphs may vary substantially even under small changes to the threshold. To examine the evolution of features for varying levels, users have to compare multiple tracking graphs without a direct visual link between them. We propose a novel, interactive, nested graph visualization based on the fact that the tracked superlevel set components for different levels are related to each other through their nesting hierarchy. This approach allows us to set multiple tracking graphs in context to each other and enables users to effectively follow the evolution of components for different levels simultaneously. We demonstrate the effectiveness of our approach on datasets from finite pointset methods, computational fluid dynamics, and cosmology simulations.     

Distance‐based control of formations with hybrid communication topology

In this paper, we focus on the control of multiagent formations with hybrid communication topology through a distance‐based approach. By saying hybrid topology, we mean that the communication topology contains both undirected and directed links, or the underlying graph of the formation contains both undirected and directed edges. A new type of graph, ie, hybrid graph, is introduced. We discuss the persistence of hybrid graphs and present the persistence verification strategy for hybrid graphs. It is proved that all the minimally persistent hybrid graphs can be obtained from persistent directed graphs by the operation of edge transformation. As the main result, it is shown that multiagent formations modeled by acyclic persistent hybrid graphs can be stabilized locally under distance‐based controllers.     

Performance metrics in the average consensus problem: A tutorial

The average consensus algorithm is a distributed procedure which allows a network of agents to agree on the average of a set of initial values. The computation occurs through local exchange of information only, namely the information exchange takes place only between agents which are neighbors with respect to a graph representing the system communication architecture. Several performance metrics have been proposed for the evaluation of this algorithm. Particularly interesting and challenging is to relate them to the communication topology. Different performance metrics may yield different answers in comparing alternative communication topologies. In this paper, we present a few performance metrics and we show how these metrics are related to the communication topology. In particular, when available, we present bounds which permit to relate performance and topology for general graphs, for graphs with symmetries, called d-dimensional tori, and for geometric graphs.     

Steady states of continuous-time open quantum walks

Continuous-time open quantum walks (CTOQW) are introduced as the formulation of quantum dynamical semigroups of trace-preserving and completely positive linear maps (or quantum Markov semigroups) on graphs. We show that a CTOQW always converges to a steady state regardless of the initial state when a graph is connected. When the graph is both connected and regular, it is shown that the steady state is the maximally mixed state. As shown by the examples in this article, the steady states of CTOQW can be very unusual and complicated even though the underlying graphs are simple. The examples demonstrate that the structure of a graph can affect quantum coherence in CTOQW through a long-time run. Precisely, the quantum coherence persists throughout the evolution of the CTOQW when the underlying topology is certain irregular graphs (such as a path or a star as shown in the examples). In contrast, the quantum coherence will eventually vanish from the open quantum system when the underlying topology is a regular graph (such as a cycle).     

A graph-based framework for sub-pixel image segmentation

Many image segmentation methods utilize graph structures for representing images, where the flexibility and generality of the abstract structure is beneficial. By using a fuzzy object representation, i.e., allowing partial belongingness of elements to image objects, the unavoidable loss of information when representing continuous structures by finite sets is significantly reduced, enabling feature estimates with sub-pixel precision.This work presents a framework for object representation based on fuzzy segmented graphs. Interpreting the edges as one-dimensional paths between the vertices of a graph, we extend the notion of a graph cut to that of a located cut, i.e., a cut with sub-edge precision. We describe a method for computing a located cut from a fuzzy segmentation of graph vertices. Further, the notion of vertex coverage segmentation is proposed as a graph theoretic equivalent to pixel coverage segmentations and a method for computing such a segmentation from a located cut is given. Utilizing the proposed framework, we demonstrate improved precision of area measurements of synthetic two-dimensional objects. We emphasize that although the experiments presented here are performed on two-dimensional images, the proposed framework is defined for general graphs and thus applicable to images of any dimension.     

TopoLayout: multilevel graph layout by topological features

We describe TopoLayout, a feature-based, multilevel algorithm that draws undirected graphs based on the topological features they contain. Topological features are detected recursively inside the graph, and their subgraphs are collapsed into single nodes, forming a graph hierarchy. Each feature is drawn with an algorithm tuned for its topology. As would be expected from a feature-based approach, the runtime and visual quality of TopoLayout depends on the number and types of topological features present in the graph. We show experimental results comparing speed and visual quality for TopoLayout against four other multilevel algorithms on a variety of data sets with a range of connectivities and sizes. TopoLayout frequently improves the results in terms of speed and visual quality on these data sets     

Spatial-temporal modeling of malware propagation in networks

Network security is an important task of network management. One threat to network security is malware (malicious software) propagation. One type of malware is called topological scanning that spreads based on topology information. The focus of this work is on modeling the spread of topological malwares, which is important for understanding their potential damages, and for developing countermeasures to protect the network infrastructure. Our model is motivated by probabilistic graphs, which have been widely investigated in machine learning. We first use a graphical representation to abstract the propagation of malwares that employ different scanning methods. We then use a spatial-temporal random process to describe the statistical dependence of malware propagation in arbitrary topologies. As the spatial dependence is particularly difficult to characterize, the problem becomes how to use simple (i.e., biased) models to approximate the spatially dependent process. In particular, we propose the independent model and the Markov model as simple approximations. We conduct both theoretical analysis and extensive simulations on large networks using both real measurements and synthesized topologies to test the performance of the proposed models. Our results show that the independent model can capture temporal dependence and detailed topology information and, thus, outperforms the previous models, whereas the Markov model incorporates a certain spatial dependence and, thus, achieves a greater accuracy in characterizing both transient and equilibrium behaviors of malware propagation.     

Sketch-based retrieval of drawings using spatial proximity

Currently, there are large collections of drawings from which users can select the desired ones to insert in their documents. However, to locate a particular drawing among thousands is not easy. In our prior work we proposed an approach to index and retrieve vector drawings by content, using topological and geometric information automatically extracted from figures. In this paper, we present a new approach to enrich the topological information by integrating spatial proximity in the topology graph, through the use of weights in adjacency links. Additionally, we developed a web search engine for clip art drawings, where we included the new technique. Experimental evaluation reveals that the use of topological proximity results in better retrieval results than topology alone. However, the increase in precision was not as high as we expected. To understand why, we analyzed sketched queries performed by users in previous experimental sessions and we present here the achieved conclusions.     

A systematic approach to constructing incremental topology control algorithms using graph transformation

Communication networks form the backbone of our society. Topology control algorithms optimize the topology of such communication networks. Due to the importance of communication networks, a topology control algorithm should guarantee certain required consistency properties (e.g., connectivity of the topology), while achieving desired optimization properties (e.g., a bounded number of neighbors). Real-world topologies are dynamic (e.g., because nodes join, leave, or move within the network), which requires topology control algorithms to operate in an incremental way, i.e., based on the recently introduced modifications of a topology. Visual programming and specification languages are a proven means for specifying the structure as well as consistency and optimization properties of topologies. In this paper, we present a novel methodology, based on a visual graph transformation and graph constraint language, for developing incremental topology control algorithms that are guaranteed to fulfill a set of specified consistency and optimization constraints. More specifically, we model the possible modifications of a topology control algorithm and the environment using graph transformation rules, and we describe consistency and optimization properties using graph constraints. On this basis, we apply and extend a well-known constructive approach to derive refined graph transformation rules that preserve these graph constraints. We apply our methodology to re-engineer an established topology control algorithm, kTC, and evaluate it in a network simulation study to show the practical applicability of our approach.     

Compound graph based hybrid data center topologies

In large-scale data centers, many servers are interconnected via a dedicated networking structure, so as to satisfy specific design goals, such as the low equipment cost, the high network capacity, and the incremental expansion. The topological properties of a networking structure are critical factors that dominate the performance of the entire data center. The existing networking structures are either fully random or completely structured. Although such networking structures exhibit advantages on given aspects, they suffer obvious shortcomings in other essential fields. In this paper, we aim to design a hybrid topology, called R3, which is the compound graph of structured and random topology. It employs random regular graph as a unit cluster and connects many such clusters by means of a structured topology, i.e., the generalized hypercube. Consequently, the hybrid topology combines the advantages of structured as well as random topologies seamlessly. Meanwhile, a coloring-based algorithm is proposed for R3 to enable fast and accurate routing. R3 possesses many attractive characteristics, such as the modularity and expansibility at the cost of only increasing the degree of any node by one. Comprehensive evaluation results show that our hybrid topology possesses excellent topology properties and network performance.