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.

‘The ‘Complexity of Imprisonment: The Northern Ireland Experience'

This article will examine the thesis that Northern Ireland experiences a relatively low level of crime. It will explore the possible reasons why crime in the North has not witnessed a dramatic increase. In light of this, the article will highlight the difficulties surrounding the current prison system and illustrate that once again Northern Ireland is experiencing a very different criminal justice system in comparison to Great Britain. Although the prisons are now being used predominately to deal with “ordinary’ crime”, they are still part of the political process.

Assessing software upgrades, plan properties and patient geometry using intensity modulated radiation therapy (IMRT) complexity metrics

Purpose: The aim of this study is to compare the sensitivity of different metrics to detect differences in complexity of intensity modulated radiation therapy (IMRT) plans following upgrades, changes to planning parameters, and patient geometry. Correlations between complexity metrics are also assessed.

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.

Scaling of Food-Web Properties with Diversity and Complexity Across Ecosystems

Trophic scaling models describe how topological food-web properties such as the number of predator prey links scale with species richness of the community. Early models predicted that either the link density (i.e. the number of links per species) or the connectance (i.e. the linkage probability between any pair of species) is constant across communities. More recent analyses, however, suggest that both these scaling models have to be rejected, and we discuss several hypotheses that aim to explain the scale dependence of these complexity parameters. Based on a recent, highly resolved food-web compilation, we analysed the scaling behaviour of 16 topological parameters and found significant power law scaling relationships with diversity (i.e. species richness) and complexity (i.e. connectance) for most of them. These results illustrate the lack of universal constants in food-web ecology as a function of diversity or complexity. Nonetheless, our power law scaling relationships suggest that fundamental processes determine food-web topology, and subsequent analyses demonstrated that ecosystem-specific differences in these relationships were of minor importance. As such, these newly described scaling relationships provide robust and testable cornerstones for future structural food-web models.

ON THE MOLECULAR COMPLEXITY OF THE HOT CORES IN ORION-A - GRAIN SURFACE-CHEMISTRY AS THE LAST REFUGE OF THE SCOUNDREL

We have modeled the gas phase chemistry of warm molecular material around protostars that is seeded with evaporating grain mantles. We show that the release of simple molecules into the gas drives ion-molecule and neutral chemistries which can account for many of the complex 0-bearing and N-bearing molecules observed in hot cores. Initial grain mantle components and secondary product molecules are identified, and the observational consequences are discussed.

Average household income, crime, and smoking behaviour in a local area: The Finnish 10-Town study

Social environments, like neighbourhoods, are increasingly recognised as determinants of health. While several studies have reported an association of low neighbourhood socio-economic status with morbidity, mortality and health risk behaviour, little is known of the health effects of neighbourhood crime rates. Using the ongoing 10-Town study in Finland, we examined the relations of average household income and crime rate measured at the local area level, with smoking status and intensity by linking census data of local area characteristics from 181 postal zip codes to survey responses to smoking behaviour in a cohort of 23,008 municipal employees. Gender-stratified multilevel analyses adjusted for age and individual occupational status revealed an association between low local area income rate and current smoking. High local area crime rate was also associated with current smoking. Both local area characteristics were strongly associated with smoking intensity. Among ever-smokers, being an ex-smoker was less likely among residents in areas with low average household income and a high crime rate. In the fully adjusted model, the association between local area income and smoking behaviour among women was substantially explained by the area-level crime rate. This study extends our knowledge of potential pathways through which social environmental factors may affect health. (c) 2007 Elsevier Ltd. All rights reserved.

A Low Complexity Real-time MIMO-Preprocessing For Fixed Complexity Sphere Decoder

Modern Multiple-Input Multiple-Output (MIMO) communication systems place huge demands on embedded processing resources in terms of throughput, latency and resource utilization. State-of-the-art MIMO detector algorithms, such as Fixed-Complexity Sphere Decoding (FSD), rely on efficient channel preprocessing involving numerous calculations of the pseudo-inverse of the channel matrix by QR Decomposition (QRD) and ordering. These highly complicated operations can quickly become the critical prerequisite for real-time MIMO detection, exaggerated as the number of antennas in a MIMO detector increases. This paper describes a sorted QR decomposition (SQRD) algorithm extended for FSD, which significantly reduces the complexity and latency
of this preprocessing step and increases the throughput of MIMO detection. It merges the calculations of the QRD and ordering operations to avoid multiple iterations of QRD. Specifically, it shows that SQRD reduces the computational complexity by over 60-70% when compared to conventional
MIMO preprocessing algorithms. In 4x4 to 7x7 MIMO cases, the approach suffers merely 0.16-0.2 dB reduction in Bit Error Rate (BER) performance.