Node overlap removal in clustered directed acyclic graphs

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). This paper presents a new E-Spring algorithm, extended from the popular spring embedder model, which eliminates node overlaps in clustered DAGs. In this framework, nodes are modeled as non-uniform charged particles with weights, and a final drawing is derived by adjusting the positions of the nodes according to a combination of spring forces and repulsive forces derived from electrostatic forces between the nodes. The drawing process needs to reach a stable state when the average distances of separation between nodes are near optimal. We introduce a stopping condition for such a stable state, which reduces equilibrium distances between nodes and therefore results in a significantly reduced area for DAG visualization. It imposes an upper bound on the repulsive forces between nodes based on graph geometry. The algorithm employs node interleaving to eliminate any residual node overlaps. These new techniques have been validated by visualizing eBay buyer–seller relationships and has resulted in overall area reductions in the range of 45–79%.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

High-speed train fault detection with unsupervised causality-based feature extraction methods

With the development of smart sensors, large amount of operating data collected from a complex system as a high-speed train providing opportunities in efficient and effective fault detection and diagnosis (FDD). The data brings also challenges in the FDD modelling process, since the various signals may be redundant, useless and noisy for the FDD modelling of a specific sub-system. The data-driven methods suffer also from the curse of dimensionality. Feature dimension reduction can reduce the dimension of the monitoring dataset and eliminate the useless information. Different from the classical methods based on the correlation among variables, recent studies have shown that causality-based methods can make the FDD model more explanatory and robust. From the adjacency matrix of the causal network diagram, three unsupervised causality-based feature extraction methods for FDD in the braking system of a high-speed train are proposed in this paper. By constructing the causal network diagram among the raw monitoring feature variables through the causal discovery algorithm, the proposed methods extract informative features based on the causal adjacency matrix or the full causal adjacency matrix proposed in this work. These methods are adopted for fault detection with real dataset collected from the braking system in a high-speed train to verify their effectiveness. The experimental results show that the proposed causality-based feature extraction methods are effective and have certain advantages in comparison with the classical correlation-based methods. Especially, the feature extraction method based on the correlation matrix constructed from full causal adjacency matrix achieves better and stable results than the benchmark methods in the experiment.     

Faithfulness and learning hypergraphs from discrete distributions

The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-)faithfulness with respect to a hypergraph is introduced. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. It is proven that strong-faithfulness defined in terms of interaction parameters ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.     

Budget Management with Applications

Abstract. Given a directed acyclic graph with timing constraints, the budget management problem is to assign to each vertex an incremental delay such that the sum of these delays is maximized without violating given constraints. We propose the notion of slack sensitivity and budget gradient to demonstrate the characteristics of budget management. We develop a polynomial-time algorithm for the budget management problem, based on the maximum independent set of an established transitive graph . We show the comparison of our approach with the well-known zero-slack algorithm , and extend it to general weighted graphs . Applications to a class of problems in VLSI CAD are also discussed.     

Second-order tracking control for leader-follower multi-agent flocking in directed graphs with switching topology

This paper investigates the flocking problem for leader-follower multi-agent systems in directed graphs with switching topology. A decentralized state control rule, namely, a second-order protocol, is designed for each agent to track the leader. And it is proved that the proposed control scheme can effectively estimate the tracking error of each agent when the leader is active. Particularly, to ensure the tracking error can be estimated, the following two questions are solved: (1) How many agents are needed to connect to the leader? (2) How should these connections be distributed? Finally, a simple example is also given to verify the effectiveness of the proposed theorems.     

On the design of communication-aware fault-tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices

Fault-tolerant scheduling is an imperative step for large-scale computational Grid systems, as often geographically distributed nodes co-operate to execute a task. By and large, primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary and a backup on two different processors. In this paper, we address the problem of how to schedule DAGs in Grids with communication delays so that service failures can be avoided in the presence of processors faults. The challenge is, that as tasks in a DAG have dependence on each other, a task must be scheduled to make sure that it will succeed when any of its predecessors fails due to a processor failure. We first propose a communication model and determine when communications between a backup and backups of its successors are necessary. Then we determine when a backup can start and its eligible processors so as to guarantee that every DAG can complete upon any processor failure. We develop two algorithms to schedule backups, which minimize response time and replication cost, respectively. We also develop a suboptimal algorithm which targets minimizing replication cost while not affecting response time. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms.     

Modeling, analyzing, and synthesizing expressive piano performance with graphical models

Trained musicians intuitively produce expressive variations that add to their audience’s enjoyment. However, there is little quantitative information about the kinds of strategies used in different musical contexts. Since the literal synthesis of notes from a score is bland and unappealing, there is an opportunity for learning systems that can automatically produce compelling expressive variations. The ESP (Expressive Synthetic Performance) system generates expressive renditions using hierarchical hidden Markov models trained on the stylistic variations employed by human performers. Furthermore, the generative models learned by the ESP system provide insight into a number of musicological issues related to expressive performance. Editor: Gerhard Widmer     

Approximate blocking probabilities in loss models with independence and distribution assumptions relaxed

Effective approximations are developed for the blocking probability in a general stationary loss model, where key independence and exponential-distribution assumptions are relaxed, giving special attention to dependence among successive service times, not studied before. The new approximations exploit recent heavy-traffic limits for the steady-state number of busy servers in the associated infinite-server model with the same arrival and service processes. In addition, a new heavy-traffic approximation is developed for the long-run proportion of time that all servers are busy. These new approximations are then combined to develop new approximations for the separate blocking probabilities of individual arrival streams in multi-class loss models. Simulation experiments show that these approximations are effective.     

Intelligent fault diagnosis for rolling bearings based on graph shift regularization with directed graphs

Graph shift regularization is a new and effective graph-based semi-supervised classification method, but its performance is closely related to the representation graphs. Since directed graphs can convey more information about the relationship between vertices than undirected graphs, an intelligent method called graph shift regularization with directed graphs (GSR-D) is presented for fault diagnosis of rolling bearings. For greatly improving the diagnosis performance of GSR-D, a directed and weighted k-nearest neighbor graph is first constructed by treating each sample (i.e., each vibration signal segment) as a vertex, in which the similarity between samples is measured by cosine distance instead of the commonly used Euclidean distance, and the edge weights are also defined by cosine distance instead of the commonly used heat kernel. Then, the labels of samples are considered as the graph signals indexed by the vertices of the representation graph. Finally, the states of unlabeled samples are predicted by finding a graph signal that has minimal total variation and satisfies the constraint given by labeled samples as much as possible. Experimental results indicate that GSR-D is better and more stable than the standard convolutional neural network and support vector machine in rolling bearing fault diagnosis, and GSR-D only has two tuning parameters with certain robustness.     

On the hardness of finding near-optimal multicuts in directed acyclic graphs

Given an edge-weighted (di)graph and a list of source-sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source-sink pairs. This is also true if we remove vertices instead of arcs.