Analyzing the effect of introducing a kurtosis parameter in Gaussian Bayesian networks

Gaussian Bayesian networks are graphical models that represent the dependence structure of a multivariate normal random variable with a directed acyclic graph (DAG). In Gaussian Bayesian networks the output is usually the conditional distribution of some unknown variables of interest given a set of evidential nodes whose values are known. The problem of uncertainty about the assumption of normality is very common in applications. Thus a sensitivity analysis of the non-normality effect in our conclusions could be necessary. The aspect of non-normality to be considered is the tail behavior. In this line, the multivariate exponential power distribution is a family depending on a kurtosis parameter that goes from a leptokurtic to a platykurtic distribution with the normal as a mesokurtic distribution. Therefore a more general model can be considered using the multivariate exponential power distribution to describe the joint distribution of a Bayesian network, with a kurtosis parameter reflecting deviations from the normal distribution. The sensitivity of the conclusions to this perturbation is analyzed using the Kullback-Leibler divergence measure that provides an interesting formula to evaluate the effect.     

State splitting,strong shift equivalence and stable isomorphism of Cuntz–Krieger algebras

We prove that if two nonnegative matrices are strong shift equivalent, the associated stable Cuntz–Krieger algebras with generalized gauge actions are conjugate. The proof is done by a purely functional analytic method and based on constructing imprimitivity bimodule from bipartite directed graphs through strong shift equivalent matrices, so that we may clarify K-theoretic behaviour of the stable isomorphism between the associated stable Cuntz–Krieger algebras. We also examine our machinery for the matrices obtained by state splitting graphs, so that topological conjugacy of the topological Markov shifts is described in terms of some equivalence relation of the Cuntz–Krieger algebras with canonical masas and the gauge actions without stabilization.     

Optimized sequencing of analysis components in multidisciplinary systems

System analysis of complex engineering systems is synthesized from a collection of analysis components that have data dependencies on each other. Sequencing interdependent analysis components in order to reduce the execution time has been addressed by multidisciplinary design optimization researchers. Representation of interdependency of analysis components is accomplished as a design structure matrix or as a graph made of nodes and edges. Sequencing of interdependent analysis components that form a directed acyclic graph is trivial. Aggregation (i.e., group of components) of some of the components into a single super-component that can render a directed cyclic graph to a directed acyclic graph is important in sequencing. Identification of components that form an aggregation is the first step in sequencing. We argue that the best form of aggregation is the strongly connected component of the graph. Challenge essentially is in sequencing within aggregations. An aggregation having n components presents a search space of n! candidate sequences. The current state of the art is to use evolutionary algorithms for this search. An aggregation requires repeated traversal (cycle/loop) of components within it for convergence. The central aim of sequencing is to reduce/minimize the overall execution time for achieving convergence through iterations. Several objective functions have been proposed for the associated optimization problems like minimize the number of feedback paths, minimize the weighted sum of feedback paths, minimize feedback and crossovers, etc. These are proxy objectives as they are not backed by mathematically established relation between the proxy objective and the aim. An objective method of predicting the number of iterations based on the sensitivity of components is proposed here. It is shown that the best sequence that takes least time to execute has a particular ordering of components, which we call one-hop-sequence. The one-hop-sequencing of components is easily achieved using a small extension to Tarjans depth first search algorithm, a standard tool in graph theory. Extended TDFS does not use sensitivity information and is much faster than evolutionary algorithms that use sensitivity information. System analysis can have simple aggregation, recursive aggregations (i.e., aggregation within aggregation) or overlapping aggregations. One-hop-sequence is shown to be the best sequence for all three cases. After sequencing of the components is done, we investigate whether an inner aggregation must retain its loop or it must be severed for speed up. This step uses sensitivity information and can offer further speed up. The proposed methodology is implemented as a tool named CASeq. Ideas discussed here may be useful to other design structure matrix applicable domains like software design, systems engineering, organizational design, product development, multidisciplinary design, product architecture, project management, building construction, manufacturing and so on.     

Graph theoretic algorithm for automatic operation sequencing for progressive die design

The paper presents a formal graph representation scheme for stamping operation sequencing for sheetmetal progressive dies and a graph theoretic method for automatic determination of the stamping operation sequence. Operation relations are represented by two graphs: an operation precedence graph and an adjacency graph. The first represents precedence constraints defined by best manufacturing practices. The second represents geometric infeasibility relations between operations. Each operation is a member of both graphs. The graphs are automatically generated from a set of stamping operations, which in turn are associated with stamping features of a part. The operation precedence graph is then verified to be acyclic using a coloured Depth First Search. Based on the operation precedence graph, a modified topological sort algorithm is applied to cluster the operations into partially ordered sets. Finally, a graph-colouring algorithm is applied to the operation adjacency graph on the partially ordered operation sets. The algorithm is implemented in C++ and is fully integrated with SolidWorks computer-aided design system. A case study is presented to illustrate the algorithm.     

Co-citation,bibliographic coupling and a characterization of lattice citation networks

In this article we study directed, acyclic graphs. We introduce the head and tail order relations and study some of their properties. Recalling the notions of generalized bibliographic coupling and generalized co-citation, and introducing a new property, called the l - property, we come to a characterization of lattices. As document citation networks are concrete realizations of directed acyclic graphs all our results are directly applicable to citation analysis. This revised version was published online in June 2006 with corrections to the Cover Date.     

双回路图的部分逆M矩阵完备

逆M矩阵是一类非常重要的非负矩阵,在生物学、物理学等很多领域中都得到了广泛的应用．利用图论理论研究逆M矩阵的完备问题是逆M矩阵研究领域的一个重要方向．双回路图是由两条简单有向回路在任意多个顶点处相交所构建的有向图．本文对此类图形的逆M矩阵完备问题进行了研究,给出了此类图形所对应的部分矩阵在两种不同情况下具有逆M矩阵完备的充分必要条件：当双回路图中的顶点均已知时,每一条回路的回路积均小于其对角元素的乘积;当双回路图中可包含未知顶点时,每一条回路至少包含一个未知顶点．同时,本文给出了具体的完备算法,并通过数值算例验证了算法的有效性．     

An Optimized Labeling Scheme for Reachability Queries

Answering reachability queries is one of the fundamental graph operations. Existing approaches either accelerate index construction by constructing an index that covers only partial reachability relationship, which may result in performing cost traversing operation when answering a query; or accelerate query answering by constructing an index covering the complete reachability relationship, which may be inefficient due to comparing the complete node labels. We propose a novel labeling scheme, which covers the complete reachability relationship, to accelerate reachability queries processing. The idea is to decompose the given directed acyclic graph (DAG) G into two subgraphs, G1 and G2. For G1, we propose to use topological labels consisting of two integers to answer all reachability queries. For G2, we construct 2-hop labels as existing methods do to answer queries that cannot be answered by topological labels. The benefits of our method lie in two aspects. On one hand, our method does not need to perform the cost traversing operation when answering queries. On the other hand, our method can quickly answer most queries in constant time without comparing the whole node labels. We confirm the efficiency of our approaches by extensive experimental studies using 20 real datasets.     

基于无标度先验的有向无环图结构学习

图模型是一种分析网络结构的有效方法,其中有向无环图由于可表示因果关系而受到广泛关注。而大量真实网络中节点的度服从幂律分布,即具有无标度特征。因此,研究了在无标度先验下,节点序已知的有向无环图结构学习问题。通过引入网络中节点度的信息和边的稀疏先验,提出罚项为 Log 型与 $l_q (0相似文献   

A New Encryption-then-Compression Scheme on Gray Images Using the Markov Random Field

Compressing encrypted images remains a challenge. As illustrated in our previous work on compression of encrypted binary images, it is preferable to exploit statistical characteristics at the receiver. Through this line, we characterize statistical correlations between adjacent bitplanes of a gray image with the Markov random field (MRF), represent it with a factor graph, and integrate the constructed MRF factor graph in that for binary image reconstruction, which gives rise to a joint factor graph for gray images reconstruction (JFGIR). By exploiting the JFGIR at the receiver to facilitate the reconstruction of the original bitplanes and deriving theoretically the sum-product algorithm (SPA) adapted to the JFGIR, a novel MRF-based encryption-then-compression (ETC) scheme is thus proposed. After preferable universal parameters of the MRF between adjacent bitplanes are sought via a numerical manner, extensive experimental simulations are then carried out to show that the proposed scheme successfully compresses the first 3 and 4 most significant bitplanes (MSBs) for most test gray images and the others with a large portion of smooth area, respectively. Thus, the proposed scheme achieves significant improvement against the state-of-the-art leveraging the 2-D Markov source model at the receiver and is comparable or somewhat inferior to that using the resolution-progressive strategy in recovery.     

Studentized Range Graph Paper–A Graphical Tool for the Comparison of Treatment Means

This note contains instructions and an example concerning the use of a specially constructed graph paper that facilitates the graphical comparison of pairs of competing treatments. The graph paper helps a data analyst to construct simultaneous and nonsimultaneous confidence intervals for all pairwise differences of treatment means and to test for statistically significant differences between all such pairs of treatment means. Unlike analytical techniques, no specialized statistical knowledge and no special tables are required to use the paper. It is intended as a tool that a statistician can readily give to his clients.

Step-by-step instructions are given for the preparation of the graphs. It is shown by example how the graphs simplify and make more informative the statistical comparision of alternative trentments.     

Traffic fatalities, Peltzman's model, and directed graphs

We show how statistical methods based on directed graphs may be useful in modeling traffic fatalities by comparing models specified using directed graphs to a model originally developed by Peltzman. The comparison uses Peltzman's original data, as well as up-dated data (and coefficients) through 1993. Out-of-sample forecasts of traffic fatalities from Peltzman's model are compared with those from a model constructed using directed graphs over data for the more recent period. The directed graphs model outperforms Peltzman's model in root mean squared forecast error.     

Determination of unknown physical properties in heat conduction problems

By overspecifying the usual boundary and initial data one can use the implicit function theorem to write the thermal conductivity β as a function of the product of the density and heat capacity α. By changing the data specification different graphs of β versus α can be obtained. The correct physical constants must lie on each graph. Hence there must exist at least one common point of intersection for all such graphs. If there is only one point of intersection of the graphs, then the correct physical constants can be obtained from it. Various theorems and numerical experiments are given to illustrate the intersecting graph technique.     

Expanding Hot Code Path for Data Cleaning on Software Graph

Graph analysis can be done at scale by using Spark GraphX which loading data into memory and running graph analysis in parallel. In this way, we should take data out of graph databases and put it into memory. Considering the limitation of memory size, the premise of accelerating graph analytical process reduces the graph data to a suitable size without too much loss of similarity to the original graph. This paper presents our method of data cleaning on the software graph. We use SEQUITUR data compression algorithm to find out hot code path and store it as a whole paths directed acyclic graph. Hot code path is inherent regularity of a program. About 10 to 200 hot code path account for 40%-99% of a program’s execution cost. These hot paths are acyclic contribute more than 0.1%-1.0% of some execution metric. We expand hot code path to a suitable size which is good for runtime and keeps similarity to the original graph.     

On Perturbation Bounds for the Joint Stationary Distribution of Multivariate Markov Chain Models

Multivariate Markov chain models have previously been proposed in for studying dependent multiple categorical data sequences. For a given multivariate Markov chain model, an important problem is to study its joint stationary distribution. In this paper, we use two techniques to present some perturbation bounds for the joint stationary distribution vector of a multivariate Markov chain with s categorical sequences. Numerical examples demonstrate the stability of the model and the effectiveness of our perturbation bounds.     

Graph coloration and group theory for factorization of symmetric dynamic systems

Summary In this article the concept of graph coloration for factorization of the characteristic polynomial of a weighted directed graph is introduced and using the fundamental lemma of Petersdorf and Sachs, it is shown that this concept can be extended to other spectra of graph among which is the spectrum of the Laplacian matrix of graphs. The goal is to use this concept for factorizing the graphs having different types of symmetry properties. In order to present an efficient algorithm, some concepts from group theory are needed. The combination of group theory and graph coloration provides a powerful method for factorizing various structural matrices, an example of which is the stiffness matrices of mass-spring dynamic systems.     

Beyond its cost, the value of maintenance: An analytical framework for capturing its net present value

Maintenance planning and activities have grown dramatically in importance across many industries and are increasingly recognized as drivers of competitiveness if managed appropriately. Correlated with this observation is the proliferation of maintenance optimization techniques in the technical literature. But while all these models deal with the cost of maintenance (as an objective function or a constraint), only a handful addresses the notion of value of maintenance, and seldom in an analytical or quantitative way.In this paper, we propose that maintenance has intrinsic value and argue that existing cost-centric models ignore an important dimension of maintenance, namely its value, and in so doing, they can lead to sub-optimal maintenance strategies. We develop a framework for capturing and quantifying the value of maintenance activities. Our framework is based on four key components. First, we consider systems that deteriorate stochastically and exhibit multi-state failures, and model their state evolution using Markov chains and directed graphs. Second, we consider that the system provides a flow of service per unit time. This flow in turn is “priced” and a discounted cash flow is calculated resulting in a present value (PV) for each branch of the graph—or “value trajectory” of the system. Third as the system ages or deteriorates, it migrates towards lower PV branches of the graph, or lower value trajectories. Fourth, we conceptualize maintenance as an operator (in a mathematical sense) that raises the system to a higher PV branch in the graph. We refer to the value of maintenance as the incremental PV between the pre- and post-maintenance branches of the graphs minus the cost of maintenance. The framework presented here offers rich possibilities for future work in benchmarking existing maintenance strategies based on their value implications, and in deriving new maintenance strategies that are “value-optimized.”     

The study of brain networks driven by steady‐state visual evoked potentials

In this article, we investigated the brain networks during the steady‐state visual evoked potential (SSVEP) task. Two questions: (1) SSVEP‐driven network structures; and (2) the relationship between SSVEP‐driven networks and stimulus frequencies were studied from a network point of view. Method of directed transfer function was applied to brain active signals recorded from electroencephalography (EEG). The resulting connectivity matrices then were converted to graphs by applying a threshold, so that graph theoretical could be used to analyze the characteristics of SSVEP‐driven networks. The results showed that network connections exist in many scalp locations beyond occipital regions. Different from the outflow areas located mainly around the parietal areas, the inflow areas had a widely distribution pattern including the frontal, temporal, and occipital areas. Furthermore, for a wide range of thresholds, with increasing frequency (7–30 Hz), the distribution of clustering coefficient and characteristic path length presented positive and negative correlation with the three parallel flicker SSVEP subsystems, respectively. The results suggested that a specific frequency may evoke certain SSVEP components more than others, and, therefore, one may generate different evoked potentials which results in different network pattern.     

Parallel solution of closely coupled systems

The odd—even permutation and associated unitary transformations for reordering the matrix coefficient A is employed as a means of breaking the strong seriality which is characteristic of closely coupled systems. The nested dissection technique is also reviewed, and the equivalence between reordering A and dissecting its network is established. The effect of transforming A with odd—even permutation on its topology and the topology of its Cholesky factors is discussed. This leads to the construction of directed graphs showing the computational steps required for factoring A , their precedence relationships and their sequential and concurrent assignment to the available processors. Expressions for the speed-up and efficiency of using N processors in parallel relative to the sequential use of a single processor are derived from the directed graph. Similar expressions are also derived when the number of available processors is fewer than required.     

计及运动副间隙的双曲柄六杆压力机机构动力学仿真向量键合图法

针对计及运动副间隙的双曲柄六杆压力机机构动力学仿真问题,提出了相应的向量键合图法。基于修正非线性连续接触碰撞力的混合模型,推导出间隙运动副的相对碰撞速度向量方程。在此基础上,建立了可以更精确描述间隙运动副的向量键合图模型,具有通用性强、模块化的特点,便于嵌入到系统的向量键合图模型中。由机构运动副的约束关系,将各构件的向量键合图模型相互键接,建立了计及驱动电机、运动副间隙的双曲柄六杆压力机机构向量键合图模型。应用相应的方法,使机构向量键合图模型的贮能元件皆具有积分因果关系,实现了计及驱动电机、运动副间隙的双曲柄六杆压力机机构计算机建模及动力学仿真。在此基础上,分析了运动副间隙对压力机机构运动学及动力学性能的影响,验证了所述方法的可靠性及有效性。通过与无质量弹簧阻尼运动副间隙模型的计算对比,进一步表明该方法可以提高系统动力学仿真的精度及实用性。     

A HEURISTIC METHOD FOR THE AUTOMATIC DRAWING OF SYSTEM MODELING GRAPHS

Graphical modeling formalisms are used for systems analysis and design in several knowledge fields. In the past the graphs associated with a given formalism were produced by hand with the help of templates. Today, however, several computer-aided system modeling tools are available on the market and, in order to be useful, they must be able to quickly display large graphs automatically. Unfortunately, the problem of drawing an arbitrary graph on the plane is NP-hard for most practical drawing criteria. The objective of this paper is to develop heuristic procedures to automatically and timely display arbitrary forests and undirected graphs in an interactive, mouse-driven graphic environment on a micro-computer. A fast geometric algorithm to display a tree with vertices of varying and non-negligible dimensions is presented and a general graph drawing heuristic is derived. The latter is based on the generation of a spanning tree with special properties which can be used to compute the rectangular coordinates of the graph vertices. We conclude with an example and with some comments on the performance of our algorithms.