A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

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.

Vibrational spectra and crystal structure of the di-amino acid peptide cyclo(L-Met-L-Met): Comparison of experimental data and DFT calculations

Experimental Raman and FT-IR spectra of solid-state non-deuterated and N-deuterated samples of cyclo(L-Met-L-Met) are reported and discussed. The Raman and FT-IR results show characteristic amide I vibrations (Raman: 1649 cm-1, infrared: 1675 cm-1) for molecules exhibiting a cis amide conformation. A Raman band, assigned to the cis amide II vibrational mode, is observed at sim1493 cm-1 but no IR band is observed in this region. Cyclo(L-Met-L-Met) crystallises in the triclinic space group P1 with one molecule per unit cell. The overall shape of the diketopiperazine (DKP) ring displays a (slightly distorted) boat conformation. The crystal packing employs two strong hydrogen bonds, which traverse the entire crystal via translational repeats. B3-LYP/cc-pVDZ calculations of the structure of the molecule predict a boat conformation for the DKP ring, in agreement with the experimentally determined X-ray structure. Copyright © 2009 John Wiley & Sons, Ltd.

DFT calculations of the structures and vibrational spectra of the [Fe(bpy)(3)](2+) and [Ru(bpy)(3)](2+) complexes

Structures of the [M(bpy)(3)](2+) complexes (M = Fe and Ru) have been calculated at the B3-LYP/DZVP level. IR and Raman spectra were calculated using the optimised geometries, employing a scaled quantum chemical force field, and compared with an earlier normal coordinate analysis of [Ru(bpy)(3) ](2+) which was based upon experimental data alone, and the use of a simplified model. The results of the calculations provide a highly satisfactory fit to the experimental data and the normal coordinate analyses, in terms of potential energy distributions, allow a detailed understanding of the vibrational spectra of both complexes. Evidence is presented for Jahn-Teller distortion in the E-1 MLCT excited state. (C) 2008 Elsevier B.V. All rights reserved.

Vibrational spectra of α-amino acids in the zwitterionic state in aqueous solution and the solid state: DFT calculations and the influence of hydrogen bonding

The zwitterionic forms of the two simplest alpha-amino acids, glycine and l-alanine, in aqueous solution and the solid state have been modeled by DFT calculations. Calculations of the structures in the solid state, using PW91 or PBE functionals, are in good agreement with the reported crystal structures, and the vibrational spectra computed at the optimized geometries provide a good fit to the observed IR and Raman spectra in the solid state. DFT calculations of the structures and vibrational spectra of the zwitterions in aqueous solution at the B3-LYP/cc-pVDZ level were found to require both explicit and implicit solvation models. Explicit solvation was modeled by inclusion of five hydrogen-bonded water molecules attached to each of the five possible hydrogen-bonding sites in the zwitterion and the integration equation formalism polarizable continuum model (IEF-PCM) was employed, providing a satisfactory fit to observed IR and Raman spectra. Band assignments are reported in terms of potential-energy distributions, which differ in some respects to those previously reported for glycine and l-alanine.

Co-acquisition of hyperpolarised 13C and 15N NMR spectra

Recent developments in dynamic nuclear polarisation now allow significant enhancements to be generated in the cryo solid state and transferred to the liquid state for detection at high resolution. We demonstrate that the Ardenkjaer-Larsen method can be extended by taking advantage of the properties of the trityl radicals used. It is possible to hyperpolarise 13C and 15N simultaneously in the solid state, and to maintain these hyperpolarisations through rapid dissolution into the liquid state. We demonstrate the almost simultaneous measurement of hyperpolarised 13C and hyperpolarised 15N NMR spectra. The prospects for further improvement of the method using contemporary technology are also discussed.

Pattern of benthic biomass size spectra from shallow waters in the East China Seas

Benthic biomass size spectra (BSS) and normalized biomass size spectra were constructed, and benthic secondary production was estimated by a size spectrum equation in the shallow waters in the East China Sea, ranging latitudinally from 40A degrees N to 29A degrees N. The BSS patterns were bimodal, two biomass peaks corresponding to meiofauna and macrofauna, respectively, separated by a trough of low biomass at 8-256 mu g individual dry weight which varied in position with median sediment particle size. The BSS also displayed bimodality within meiofauna size ranges, which in most stations was due to the relative proportions of nematodes and other meiofauna taxa. Re-analysis of data from sites in the UK, South Africa, and Antarctic showed a similar bimodality in the adult species body size distribution within the meiofauna size range. Macrofaunal production estimated by the size spectrum equation was very similar to the results of Brey90 empirical equation. However, these production values were much lower than those calculated by Brey01. Different individual dry-to-wet conversion ratios, temperature deviation, and macrofauna taxonomic composition might be responsible for the between-model differences. The macrofaunal P/B ratios calculated by this equation ranged from 0.3 to 3.4 which were in accordance with values from Northern Hemisphere mid-latitudes. Meiofaunal production estimates will need further empirical support.

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.