A similarity measure for graphs with low computational complexity

We present and analyze an algorithm to measure the structural similarity of generalized trees, a new graph class which includes rooted trees. For this, we represent structural properties of graphs as strings and define the similarity of two Graphs as optimal alignments of the corresponding property stings. We prove that the obtained graph similarity measures are so called Backward similarity measures. From this we find that the time complexity of our algorithm is polynomial and, hence, significantly better than the time complexity of classical graph similarity methods based on isomorphic relations. (c) 2006 Elsevier Inc. All rights reserved.

Information theoretic measures of UHG graphs with low computational complexity

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples. (c) 2007 Elsevier Inc. All rights reserved.

Structural similarity of directed universal hierarchical graphs: A low computational complexity approach

In the present paper we mainly introduce an efficient approach to measure the structural similarity of so called directed universal hierarchical graphs. We want to underline that directed universal hierarchical graphs can be obtained from generalized trees which are already introduced. In order to classify these graphs, we state our novel graph similarity method. As a main result we notice that our novel algorithm has low computational complexity. (c) 2007 Elsevier Inc. All rights reserved.

A comparative analysis of multidimensional features of objects resembling sets of graphs

In the present paper, we introduce a notion of a style representing abstract, complex objects having characteristics that can be represented as structured objects. Furthermore, we provide some mathematical properties of such styles. As a main result, we present a novel approach to perform a meaningful comparative analysis of such styles by defining and using graph-theoretic measures. We compare two styles by comparing the underlying feature sets representing sets of graph structurally. To determine the structural similarity between the underlying graphs, we use graph similarity measures that are computationally efficient. More precisely, in order to compare styles, we map each feature set to a so-called median graph and compare the resulting median graphs. As an application, we perform an experimental study to compare special styles representing sets of undirected graphs and present numerical results thereof. (C) 2007 Elsevier Inc. All rights reserved.

Topological mappings between graphs, trees and generalized trees

We present novel topological mappings between graphs, trees and generalized trees that means between structured objects with different properties. The two major contributions of this paper are, first, to clarify the relation between graphs, trees and generalized trees, a graph class recently introduced. Second, these transformations provide a unique opportunity to transform structured objects into a representation that might be beneficial for a processing, e.g., by machine learning techniques for graph classification. (c) 2006 Elsevier Inc. All rights reserved.

Comparing large graphs efficiently by margins of feature vectors

Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. (c) 2006 Elsevier Inc. All rights reserved.

Localization of erythropoietin gene expression in proximal renal tubular cells detected by digoxigenin-labelled oligonucleotide probes

Erythropoietin (EPO) is the main humoral stimulus of erythropoiesis. In adult mammals, the kidney releases EPO in response to hypoxic stress. Conflicting data have suggested either renal tubular or peritubular cell origins of EPO synthesis in vivo. In situ hybridization studies were performed to define further the kidney cell type(s) capable of increasing EPO gene expression during hypoxic stimulation. EPO gene expression was stimulated in mice exposed to acute hypobaric hypoxia. Kidneys from hypoxic and control normoxic mice were obtained. Six digoxigenin-labelled oligonucleotide probes complementary to EPO exon sequences were utilized for in situ hybridization for EPO messenger RNA. Positive hybridization signals were identified in some proximal tubular cells, confined to the inner third of the renal cortex of hypoxic mouse kidney.

Use of data dependence graphs in the design of bit-level systolic arrays

The use of bit-level systolic array circuits as building blocks in the construction of larger word-level systolic systems is investigated. It is shown that the overall structure and detailed timing of such systems may be derived quite simply using the dependence graph and cut-set procedure developed by S. Y. Kung (1988). This provides an attractive and intuitive approach to the bit-level design of many VLSI signal processing components. The technique can be applied to ripple-through and partly pipelined circuits as well as fully systolic designs. It therefore provides a means of examining the relative tradeoff between levels of pipelining, chip area, power consumption, and throughput rate within a given VLSI design.

DESIGNING VLSI SIGNAL PROCESSING CHIPS USING DATA DEPENDENCE GRAPHS.

The highly structured nature of many digital signal processing operations allows these to be directly implemented as regular VLSI circuits. This feature has been successfully exploited in the design of a number of commercial chips, some examples of which are described. While many of the architectures on which such chips are based were originally derived on heuristic basis, there is an increasing interest in the development of systematic design techniques for the direct mapping of computations onto regular VLSI arrays. The purpose of this paper is to show how the the technique proposed by Kung can be readily extended to the design of VLSI signal processing chips where the organisation of computations at the level of individual data bits is of paramount importance. The technique in question allows architectures to be derived using the projection and retiming of data dependence graphs.

A fast transient kinetic study of the effect of H-2 on the selective catalytic reduction of NOx with octane using isotopically labelled (NO)-N-15

The H-2-assisted hydrocarbon selective catalytic reduction (HC-SCR) of NO, was investigated using fast transient kinetic analysis coupled with isotopically labelled (NO)-N-15. This allowed monitoring of the evolution of products and reactants during switches of H-2 in and out of the SCR reaction mix. The results obtained with a time resolution of less than 1 s showed that the effect on the reaction of the removal or addition of H-2 was essentially instantaneous. This is consistent with the view that H-2 has a direct chemical effect on the reaction mechanism rather than a secondary one through the formation of "active" Ag clusters. The effect of H-2 partial pressure was investigated at 245 degrees C, it was found that increasing partial pressure of H-2 resulted in increasing conversion of NO and octane. It was also found that the addition of H-2 at 245 degrees C had different effects on the product distribution depending on its partial pressure. The change of the nitrogen balance over time during switches in and out of hydrogen showed that significant quantities of N-containing species were stored when hydrogen was introduced to the system. The positive nitrogen balance on removal of H-2 from the gas phase showed that these stored species continued to react after removal of hydrogen to form N-2. (c) 2006 Elsevier Inc. All rights reserved.

Implementing efficient graphs in connection networks

We consider the problem of sharing the cost of a network that meets the connection demands of a set of agents. The agents simultaneously choose paths in the network connecting their demand nodes. A mechanism splits the total cost of the network formed among the participants. We introduce two new properties of implementation. The first property, Pareto Nash implementation (PNI), requires that the efficient outcome always be implemented in a Nash equilibrium and that the efficient outcome Pareto dominates any other Nash equilibrium. The average cost mechanism and other asymmetric variations are the only mechanisms that meet PNI. These mechanisms are also characterized under strong Nash implementation. The second property, weakly Pareto Nash implementation (WPNI), requires that the least inefficient equilibrium Pareto dominates any other equilibrium. The egalitarian mechanism (EG) and other asymmetric variations are the only mechanisms that meet WPNI and individual
rationality. EG minimizes the price of stability across all individually rational mechanisms. © Springer-Verlag Berlin Heidelberg 2012

Using Graphs to Visualise and Detect Anomalies in Access Control System Transactions

Physical Access Control Systems are commonly used to secure doors in buildings such as airports, hospitals, government buildings and offices. These systems are designed primarily to provide an authentication mechanism, but they also log each door access as a transaction in a database. Unsupervised learning techniques can be used to detect inconsistencies or anomalies in the mobility data, such as a cloned or forged Access Badge, or unusual behaviour by staff members. In this paper, we present an overview of our method of inferring directed graphs to represent a physical building network and the flows of mobility within it. We demonstrate how the graphs can be used for Visual Data Exploration, and outline how to apply algorithms based on Information Theory to the graph data in order to detect inconsistent or abnormal behaviour.