JOSTLE: multilevel graph partitioning software: an overview

In this chapter we look at JOSTLE, the multilevel graph-partitioning software package, and highlight some of the key research issues that it addresses. We first outline the core algorithms and place it in the context of the multilevel refinement paradigm. We then look at issues relating to its use as a tool for parallel processing and, in particular, partitioning in parallel. Since its first release in 1995, JOSTLE has been used for many mesh-based parallel scientific computing applications and so we also outline some enhancements such as multiphase mesh-partitioning, heterogeneous mapping and partitioning to optimise subdomain shape

A critical examination of node-similarity based graph matching algorithms

In this paper, we shall critically examine a special class of graph matching algorithms that follow the approach of node-similarity measurement. A high-level algorithm framework, namely node-similarity graph matching framework (NSGM framework), is proposed, from which, many existing graph matching algorithms can be subsumed, including the eigen-decomposition method of Umeyama, the polynomial-transformation method of Almohamad, the hubs and authorities method of Kleinberg, and the kronecker product successive projection methods of Wyk, etc. In addition, improved algorithms can be developed from the NSGM framework with respects to the corresponding results in graph theory. As the observation, it is pointed out that, in general, any algorithm which can be subsumed from NSGM framework fails to work well for graphs with non-trivial auto-isomorphism structure.

Measuring similarity of software designs using graph matching for CBR

This paper examines different ways of measuring similarity between software design models for Case Based Reasoning (CBR) to facilitate reuse of software design and code. The paper considers structural and behavioural aspects of similarity between software design models. Similarity metrics for comparing static class structures are defined and discussed. A Graph representation of UML class diagrams and corresponding similarity measures for UML class diagrams are defined. A full search graph matching algorithm for measuring structural similarity diagrams based on the identification of the Maximum Common Sub-graph (MCS) is presented. Finally, a simple evaluation of the approach is presented and discussed.

Scalable and efficient graph colouring in 3 dimensions using emergence engineering principles

This paper describes ways in which emergence engineering principles can be applied to the development of distributed applications. A distributed solution to the graph-colouring problem is used as a vehicle to illustrate some novel techniques. Each node acts autonomously to colour itself based only on its local view of its neighbourhood, and following a simple set of carefully tuned rules. Randomness breaks symmetry and thus enhances stability. The algorithm has been developed to enable self-configuration in wireless sensor networks, and to reflect real-world configurations the algorithm operates with 3 dimensional topologies (reflecting the propagation of radio waves and the placement of sensors in buildings, bridge structures etc.). The algorithm’s performance is evaluated and results presented. It is shown to be simultaneously highly stable and scalable whilst achieving low convergence times. The use of eavesdropping gives rise to low interaction complexity and high efficiency in terms of the communication overheads.

The global distribution of phytoplankton size spectrum and size classes from their light-absorption spectra derived from satellite data

The absorption spectra of phytoplankton in the visible domain hold implicit information on the phytoplankton community structure. Here we use this information to retrieve quantitative information on phytoplankton size structure by developing a novel method to compute the exponent of an assumed power-law for their particle-size spectrum. This quantity, in combination with total chlorophyll-a concentration, can be used to estimate the fractional concentration of chlorophyll in any arbitrarily-defined size class of phytoplankton. We further define and derive expressions for two distinct measures of cell size of mixed. populations, namely, the average spherical diameter of a bio-optically equivalent homogeneous population of cells of equal size, and the average equivalent spherical diameter of a population of cells that follow a power-law particle-size distribution. The method relies on measurements of two quantities of a phytoplankton sample: the concentration of chlorophyll-a, which is an operational index of phytoplankton biomass, and the total absorption coefficient of phytoplankton in the red peak of visible spectrum at 676 nm. A sensitivity analysis confirms that the relative errors in the estimates of the exponent of particle size spectra are reasonably low. The exponents of phytoplankton size spectra, estimated for a large set of in situ data from a variety of oceanic environments (similar to 2400 samples), are within a reasonable range; and the estimated fractions of chlorophyll in pico-, nano- and micro-phytoplankton are generally consistent with those obtained by an independent, indirect method based on diagnostic pigments determined using high-performance liquid chromatography. The estimates of cell size for in situ samples dominated by different phytoplankton types (diatoms, prymnesiophytes, Prochlorococcus, other cyanobacteria and green algae) yield nominal sizes consistent with the taxonomic classification. To estimate the same quantities from satellite-derived ocean-colour data, we combine our method with algorithms for obtaining inherent optical properties from remote sensing. The spatial distribution of the size-spectrum exponent and the chlorophyll fractions of pico-, nano- and micro-phytoplankton estimated from satellite remote sensing are in agreement with the current understanding of the biogeography of phytoplankton functional types in the global oceans. This study contributes to our understanding of the distribution and time evolution of phytoplankton size structure in the global oceans.

The spectrum of endogenous human chromogranin A-derived peptides identified using a modified proteomic strategy.

The hypothesis that chromogranin A (CgA), a protein of neuroendocrine cell secretory granules, may be a precursor of biologically active peptides, rests on observed activities of peptide fragments largely produced by exogenous protease digestion of the bovine protein. Here we have adopted a modified proteomic strategy to isolate and characterise human CgA-derived peptides produced by endogenous prohormone convertases. Initial focus was on an insulinoma as previous studies have shown that CgA is rapidly processed in pancreatic beta cells and that tumours arising from these express appropriate prohormone convertases. Eleven novel peptides were identified arising from processing at both monobasic and dibasic sites and processing was most evident in the C-terminal domain of the protein. Some of these peptides were identified in endocrine tumours, such as mid-gut carcinoid and phaeochromocytoma, which arise from endocrine cells of different phenotype and in different anatomical sites. Two of the most interesting peptides, GR-44 and ER-37, representing the C-terminal region of CgA, were found to be amidated. These data would imply that the intact protein is C-terminally amidated and that these peptides are probably biologically active. The spectrum of novel CgA-derived peptides, described in the present study, should provide a basis for biological evaluation of authentic entities.

How optimal life history changes with the community size-spectrum

This paper derives optimal life histories for fishes or other animals in relation to the size spectrum of the ecological community in which they are both predators and prey. Assuming log-linear size-spectra and well known scaling laws for feeding and mortality, we first construct the energetics of the individual. From these we find, using dynamic programming, the optimal allocation of energy between growth and reproduction as well as the trade-off between offspring size and numbers. Optimal strategies were found to be strongly dependent on size spectrum slope. For steep size spectra (numbers declining rapidly with size), determinate growth was optimal and allocation to somatic growth increased rapidly with increasing slope. However, restricting reproduction to a fixed mating season changed optimal allocations to give indeterminate growth approximating a von Bertalanffy trajectory. The optimal offspring size was as small as possible given other restrictions such as newborn starvation mortality. For shallow size spectra, finite optimal maturity size required a decline in fitness for large size or age. All the results are compared with observed size spectra of fish communities to show their consistency and relevance.

Goal Recognition through Goal Graph Analysis

We present a novel approach to goal recognition based on a two-stage paradigm of graph construction and analysis. First, a graph structure called a Goal Graph is constructed to represent the observed actions, the state of the world, and the achieved goals as well as various connections between these nodes at consecutive time steps. Then, the Goal Graph is analysed at each time step to recognise those partially or fully achieved goals that are consistent with the actions observed so far. The Goal Graph analysis also reveals valid plans for the recognised goals or part of these goals. Our approach to goal recognition does not need a plan library. It does not suffer from the problems in the acquisition and hand-coding of large plan libraries, neither does it have the problems in searching the plan space of exponential size. We describe two algorithms for Goal Graph construction and analysis in this paradigm. These algorithms are both provably sound, polynomial-time, and polynomial-space. The number of goals recognised by our algorithms is usually very small after a sequence of observed actions has been processed. Thus the sequence of observed actions is well explained by the recognised goals with little ambiguity. We have evaluated these algorithms in the UNIX domain, in which excellent performance has been achieved in terms of accuracy, efficiency, and scalability.