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.

Detecting Anomalies in Graphs with Numeric Labels

This paper presents Yagada, an algorithm to search labelled graphs for anomalies using both structural data and numeric attributes. Yagada is explained using several security-related examples and validated with experiments on a physical Access Control database. Quantitative analysis shows that in the upper range of anomaly thresholds, Yagada detects twice as many anomalies as the best-performing numeric discretization algorithm. Qualitative evaluation shows that the detected anomalies are meaningful, representing a com- bination of structural irregularities and numerical outliers.

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.

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.

Signal and variability within a Holocene peat bog - Chronological uncertainties of pollen, macrofossil and fungal proxies

A single raised bog from the eastern Netherlands has been repeatedly analysed and ¹⁴C dated over the past few decades. Here we assess the within-site variability of fossil proxy data through comparing the regional
pollen, macrofossils and non-pollen palynomorphs of four of these profiles. High-resolution chronologies were obtained using ¹⁴C dating and Bayesian age-depth modelling. Where chronologies of profiles overlap, proxy curves are compared between the profiles using greyscale graphs that visualise chronological uncertainties. Even at this small spatial scale, there is considerable variability of the fossil proxy curves. Implications regarding signal (climate) and noise (internal dynamics) of the different types of fossil proxies are discussed. Single cores are of limited value for reconstructing centennial-scale climate change, and only by combining multiple cores and proxies can we obtain a reliable understanding of past environmental change and possible forcing factors (e.g., solar variability).

The Computational Complexity of Dominance and Consistency in CP-Nets

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

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.

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

Self-healing systems and virtual structures

Modern networks are large, highly complex and dynamic. Add to that the mobility of the agents comprising many of these networks. It is difficult or even impossible for such systems to be managed centrally in an efficient manner. It is imperative for such systems to attain a degree of self-management. Self-healing i.e. the capability of a system in a good state to recover to another good state in face of an attack, is desirable for such systems. In this paper, we discuss the self-healing model for dynamic reconfigurable systems. In this model, an omniscient adversary inserts or deletes nodes from a network and the algorithm responds by adding a limited number of edges in order to maintain invariants of the network. We look at some of the results in this model and argue for their applicability and further extensions of the results and the model. We also look at some of the techniques we have used in our earlier work, in particular, we look at the idea of maintaining virtual graphs mapped over the existing network and assert that this may be a useful technique to use in many problem domains.

Generating Realistic Labelled, Weighted Random Graphs

Generative algorithms for random graphs have yielded insights into the structure and evolution of real-world networks. Most networks exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Usually, random graph models consider only structural information, but many real-world networks also have labelled vertices and weighted edges. In this paper, we present a generative model for random graphs with discrete vertex labels and numeric edge weights. The weights are represented as a set of Beta Mixture Models (BMMs) with an arbitrary number of mixtures, which are learned from real-world networks. We propose a Bayesian Variational Inference (VI) approach, which yields an accurate estimation while keeping computation times tractable. We compare our approach to state-of-the-art random labelled graph generators and an earlier approach based on Gaussian Mixture Models (GMMs). Our results allow us to draw conclusions about the contribution of vertex labels and edge weights to graph structure.

The prognostic and therapeutic value of EpHA2 in early colorectal cancer (CRC).

Background: EpHA2 is a 130 kD transmembrane glycoprotein belonging to ephrin receptor subfamily and involved in angiogenesis/tumour neovascularisation. High EpHA2 mRNA level has recently been implicated in cetuximab resistance. Previously, we found high EpHA2 levels in a panel of invasive colorectal cancer (CRC) cells, which was associated with high levels of stem-cell marker CD44. Our aim was to investigate the prognostic value of EpHA2 and subsequently correlate expression levels to known clinico-pathological variables in early stage CRC. Methods: Tissue samples from 509 CRC patients were analysed. EpHA2 expression was measured using IHC. Kaplan-Meier graphs were used. Univariate and multivariate analyses employed Cox Proportional Hazards Ratio (HR) method. A backward selection method (Akaike’s information criterion) was used to determine a refined multivariate model. Results: EpHA2 was highly expressed in CRC adenocarcinoma compared to matched normal colon tissue. In support of our preclinical invasive models, strong correlation was found between EpHA2 expression and CD44 and Lgr5 staining (p<0.001). In addition, high EpHA2 expression significantly correlated with vascular invasion (p=0.03).HR for OS for stage II/III patients with high EpHA2 expression was 1.69 (95%CI: 1.164-2.439; p=0.003). When stage II/III was broken down into individual stages, there was significant correlation between high EpHA2 expression and poor 5-years OS in stage II patients (HR: 2.18; 95%CI: 1.28-3.71; p=0.005).HR in the stage III group showed a trend to statistical significance (HR: 1.48; 95%CI=0.87-2.51; p=0.05). In both univariate and multivariate analyses of stage II patients, high EpHA2 expression was the only significant factor and was retained in the final multivariate model. Higher levels of EpHA2 were noted in our RAS and BRAF mutant CRC cells, and silencing EpHA2 resulted in significant decreases in migration/invasion in parental and invasive CRC sublines. Correlation between KRAS/NRAS/BRAFmutational status and EpHA2 expression in clinical samples is ongoing. Conclusions: Taken together, our study is the first to indicate that EpHA2 expression is a predictor of poor clinical outcome and a potential novel target in early stage CRC.

Energy of line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G. © 2010 Elsevier B.V. All rights reserved.