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.

Equidiscrimination contours around an achromatic colour are convex but not balanced

A model based on the postreceptor channels followed by a Minkowski norm (Minkowski model) is widely used to fit experimental data on colour discrimination. This model predicts that contours of equal discrimination in colour space are convex and balanced (symmetrical). We have tested these predictions in an experiment. Two new statistical tests have been developed to analyse convexity and balancedness of experimental curves. Using these tests we have found that while they are in line with the convexity prediction, our experimental contours strongly testify against balancedness. It follows that the Minkowski model is, generally, inappropriate to model colour discrimination data. © 2002 Elsevier Science (USA).

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.

Session 4: Getting balanced nutrition messages across Nutrition communication: consumer perceptions and predicting intentions

Health claims on food products, which aim at informing the public about the health benefits of the product, represent one type of nutrition communication; the use of these is regulated by the European Union. This paper provides an overview of the research on health claims, including consumers' perceptions of such claims and their intention to buy products that carry health-related claims. This is followed by a discussion on the results from some recent studies investigating public perceptions and willingness to use products with health claims. In these studies, claims are presented in the form of messages of different lengths, types, framing, with and without qualifying words and symbols. They also investigate how perceptions and intentions are affected by individual needs and product characteristics. Results show that adding health claims to products does increase their perceived healthiness. Claim structure was found to make a difference to perceptions, but its influence depended on the level of relevance, familiarity and individuals' need for information. Further, the type of health benefit proposed and the base product used also affected perceptions of healthiness. The paper concludes that while healthiness perceptions relating to products with health claims may vary between men and women, old and young and between countries, the main factor influencing perceived healthiness and intention to buy a product with health claim is personal relevance.

The two-way relationship between the Balanced Scorecard and Management Control Systems in organizations:Lessons from a Case Study

This paper reports a case study conducted in Quinta da Aveleda, one of
the three largest Portuguese wine companies. Our aim was to explore the
relationship established between a newly implemented Balanced Scorecard
(BSC) and the elements of the Management Control System (MCS) in the
organization. Thus, two specific objectives were pursued. Firstly, to identify
the influences (barriers, opportunities) of the existing MCS on the implementation
of the BSC. Secondly, to identify the impacts the BSC implementation
was able to exert on the configuration of the organization’s MCS.
We found that the budgeting process, the planning system, the information
infrastructure, and the organizational structure and culture were the elements
of the previous MCS that influenced the BSC implementation process.
Eventually, the BSC implementation led to important changes in the budgeting,
planning, reporting systems and processes. In order to explain these
findings, we briefly explored the main issues and factors accounting for the
scope and nature of the BSC’s impacts on Quinta da Aveleda. These issues
and factors were the mobilized organizational resources, the implementation
approach, the communication, and the organizational support.

Trait directed de novo population transcriptome dissects genetic regulation of a balanced polymorphism in phosphorus nutrition/arsenate tolerance in a wild grass Holcus lanatus

The aim of this study was to characterize the transcriptome of a balanced polymorphism, under the regulation of a single gene, for phosphate fertilizer responsiveness/arsenate toler- ance in wild grass Holcus lanatus genotypes screened from the same habitat.

De novo transcriptome sequencing, RNAseq (RNA sequencing) and single nucleotide poly- morphism (SNP) calling were conducted on RNA extracted from H.lanatus. Roche 454 sequencing data were assembled into c. 22 000 isotigs, and paired-end Illumina reads for phosphorus-starved (P) and phosphorus-treated (P+) genovars of tolerant (T) and nontoler- ant (N) phenotypes were mapped to this reference transcriptome.

Heatmaps of the gene expression data showed strong clustering of each P+/P treated genovar, as well as clustering by N/T phenotype. Statistical analysis identified 87 isotigs to be significantly differentially expressed between N and T phenotypes and 258 between P+ and P treated plants. SNPs and transcript expression that systematically differed between N and T phenotypes had regulatory function, namely proteases, kinases and ribonuclear RNA- binding protein and transposable elements.

A single gene for arsenate tolerance led to distinct phenotype transcriptomes and SNP pro- files, with large differences in upstream post-translational and post-transcriptional regulatory genes rather than in genes directly involved in P nutrition transport and metabolism per se.

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

A balanced polymorphism in biomass resource allocation controlled by phosphate in grasses screened through arsenate tolerance

The response of arsenate and non-tolerant Holcus lanatus L. phenotypes, where tolerance is achieved through suppression of high affinity phosphate/arsenate root uptake, was investigated under different growth regimes to investigate why there is a polymorphism in tolerance found in populations growing on uncontaminated soil. Tolerant plants screened from an arsenic uncontaminated population differed, when grown on the soil from the populations origin, from non-tolerants, in their biomass allocation under phosphate fertilization: non-tolerants put more resources into tiller production and down regulated investment in root production under phosphate fertilization while tolerants tillered less effectively and did not alter resource allocation to shoot biomass under phosphate fertilization. The two phenotypes also differed in their shoot mineral status having higher concentrations of copper, cadmium, lead and manganese, but phosphorus status differed little, suggesting tight homeostasis. The polymorphism was also widely present (40%) in other wild grass species suggesting an important ecological role for this gene that can be screened through plant root response to arsenate.

Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information

We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each bad processor may send an unlimited number of messages. The only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits.

A good quorum is a set of O(logn) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and Õ(vn) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. The collection is balanced in that no processor is in more than O(logn) quorums. This yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model.

The technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.

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.

AGWAN: A Generative Model for Labelled, Weighted Graphs

Real-world graphs or networks tend to exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Much effort has been directed into creating realistic and tractable models for unlabelled graphs, which has yielded insights into graph structure and evolution. Recently, attention has moved to creating models for labelled graphs: many real-world graphs are labelled with both discrete and numeric attributes. In this paper, we present AGWAN (Attribute Graphs: Weighted and Numeric), a generative model for random graphs with discrete labels and weighted edges. The model is easily generalised to edges labelled with an arbitrary number of numeric attributes. We include algorithms for fitting the parameters of the AGWAN model to real-world graphs and for generating random graphs from the model. Using the Enron “who communicates with whom” social graph, we compare our approach to state-of-the-art random labelled graph generators and draw conclusions about the contribution of discrete vertex labels and edge weights to the structure of real-world graphs.