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.

Physical model for the generation of ideal resources in multipartite quantum networking

We propose a physical model for generating multipartite entangled states of spin-s particles that have important applications in distributed quantum information processing. Our protocol is based on a process where mobile spins induce the interaction among remote scattering centers. As such, a major advantage lies in the management of stationary and well-separated spins. Among the generable states, there is a class of N-qubit singlets allowing for optimal quantum telecloning in a scalable and controllable way. We also show how to prepare Aharonov, W, and Greenberger-Horne-Zeilinger states.

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.

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.

Non-competitive phenotypic differences can have a strong effect on ideal free distributions

1. We present a model of the ideal free distribution (IFD) where differences between phenotypes other than those involved in direct competition for resources are considered. We show that these post-acquisitional differences can have a dramatic impact on the predicted distributions of individuals.

2. Specifically, we predict that, when the relative abilities of phenotypes are independent of location, there will be a continuum of mixed evolutionarily stable strategy (ESS) distributions (where all phenotypes are present in all patches).

3, When the relative strengths of the post-acquisitional trait in the two phenotypes differ between patches, however, we predict only a single ESS at equilibrium. Further, this distribution may be fully or partially segregated (with the distribution of at least one phenotype being spatially restricted) but it will never be mixed.

4, Our results for post-acquisitional traits mirror those of Parker (1982) for direct competitive traits. This comparison illustrates that it does not matter whether individual differences are expressed before or after competition for resources, they will still exert considerable influence on the distribution of the individuals concerned.

How do grazers achieve their distribution? A continuum of models from random diffusion to the ideal free distribution using biased random walks

A conceptual model is described for generating distributions of grazing animals, according to their searching behavior, to investigate the mechanisms animals may use to achieve their distributions. The model simulates behaviors ranging from random diffusion, through taxis and cognitively aided navigation (i.e., using memory), to the optimization extreme of the Ideal Free Distribution. These behaviors are generated from simulation of biased diffusion that operates at multiple scales simultaneously, formalizing ideas of multiple-scale foraging behavior. It uses probabilistic bias to represent decisions, allowing multiple search goals to be combined (e.g., foraging and social goals) and the representation of suboptimal behavior. By allowing bias to arise at multiple scales within the environment, each weighted relative to the others, the model can represent different scales of simultaneous decision-making and scale-dependent behavior. The model also allows different constraints to be applied to the animal's ability (e.g., applying food-patch accessibility and information limits). Simulations show that foraging-decision randomness and spatial scale of decision bias have potentially profound effects on both animal intake rate and the distribution of resources in the environment. Spatial variograms show that foraging strategies can differentially change the spatial pattern of resource abundance in the environment to one characteristic of the foraging strategy.</

Beyond the ideal free distribution: More general models of predator distribution

The ideal free distribution model which relates the spatial distribution of mobile consumers to that of their resource is shown to be a limiting case of a more general model which we develop using simple concepts of diffusion. We show how the ideal free distribution model can be derived from a more general model and extended by incorporating simple models of social influences on predator spacing. First, a free distribution model based on patch switching rules, with a power-law interference term, which represents instantaneous biased diffusion is derived. A social bias term is then introduced to represent the effect of predator aggregation on predator fitness, separate from any effects which act through intake rate. The social bias term is expanded to express an optimum spacing for predators and example solutions of the resulting biased diffusion models are shown. The model demonstrates how an empirical interference coefficient, derived from measurements of predator and prey densities, may include factors expressing the impact of social spacing behaviour on fitness. We conclude that empirical values of log predator/log prey ratio may contain information about more than the relationship between consumer and resource densities. Unlike many previous models, the model shown here applies to conditions without continual input. (C) 1997 Academic Press Limited.</p>

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.

Family caregivers' ideal expectations of Canada's Compassionate Care Benefit

We present the findings of 57 interviews conducted in 2007-2008 with Canadians who have cared for a dying family member to examine their ideal expectations of the Compassionate Care Benefit (CCB) - a social programme providing job security and income support for workers caring for a dying person. Our aims are to (1) appreciate how intended users and other family caregivers view the programme's very nature; (2) identify programme challenges and improvements that emerge from considering family caregivers' ideal expectations; and (3) contribute to a larger evaluative study designed to make policy-relevant recommendations for CCB improvement. Review of transcripts across three respondent groups reveals four categories of ideal expectations: (1) eligibility, (2) informational, (3) timing and (4) financial. Ideal expectations were typically derived from respondents' experiences of care-giving, their knowledge of the programme and, for some, of applying for and/or receiving the CCB. Findings reveal that there are gaps between respondents' ideal expectations and their experienced realities. Such gaps may lead to disappointment being experienced by those who believe they should be eligible for the programme but are not, or should be entitled to receive some form of support that is not presently available. This analysis plays an important role in identifying potential changes for the CCB that may better support family caregivers, in that the ideal expectations serve as a starting point for articulating desirable programme amendments. This analysis also has wider relevance. For jurisdictions looking to create new social programmes to support caregivers based upon labour policy strategies and legislation, this analysis identifies considerations that should be made at the outset of development. For jurisdictions that already have employment-based caregiver support programmes, this analysis demonstrates that programme challenges may not always be met through legislative changes alone but also through measures such as increasing awareness. © 2011 Blackwell Publishing Ltd.