A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

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.

Single machine scheduling and due date assignment under series-parallel precedence constraints

We consider a single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs tinder series parallel and somewhat wider class of precedence constraints as well as the properties of series-parallel graphs.

Visualizing a temporal consistency checker

The notion of time plays a vital and ubiquitous role of a common universal reference. In knowledge-based systems, temporal information is usually represented in terms of a collection of statements, together with the corresponding temporal reference. This paper introduces a visualized consistency checker for temporal reference. It allows expression of both absolute and relative temporal knowledge, and provides visual representation of temporal references in terms of directed and partially weighted graphs. Based on the temporal reference of a given scenario, the visualized checker can deliver a verdict to the user as to whether the scenario is temporally consistent or not, and provide the corresponding analysis / diagnosis.

An analysis of the changes to the mechanical and acoustical properties of paper caused by the damage mechanisms present in the fibre structure

This paper will analyse two of the likely damage mechanisms present in a paper fibre matrix when placed under controlled stress conditions: fibre/fibre bond failure and fibre failure. The failure process associated with each damage mechanism will be presented in detail focusing on the change in mechanical and acoustic properties of the surrounding fibre structure before and after failure. To present this complex process mathematically, geometrically simple fibre arrangements will be chosen based on certain assumptions regarding the structure and strength of paper, to model the damage mechanisms. The fibre structures are then formulated in terms of a hybrid vibro-acoustic model based on a coupled mass/spring system and the pressure wave equation. The model will be presented in detail in the paper. The simulation of the simple fibre structures serves two purposes; it highlights the physical and acoustic differences of each damage mechanism before and after failure, and also shows the differences in the two damage mechanisms when compared with one another. The results of the simulations are given in the form of pressure wave contours, time-frequency graphs and the Continuous Wavelet Transform (CWT) diagrams. The analysis of the results leads to criteria by which the two damage mechanisms can be identified. Using these criteria it was possible to verify the results of the simulations against experimental acoustic data. The models developed in this study are of specific practical interest in the paper-making industry, where acoustic sensors may be used to monitor continuous paper production. The same techniques may be adopted more generally to correlate acoustic signals to damage mechanisms in other fibre-based structures.

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.

A robust approach to subsequence matching

In terms of a general time theory which addresses time-elements as typed point-based intervals, a formal characterization of time-series and state-sequences is introduced. Based on this framework, the subsequence matching problem is specially tackled by means of being transferred into bipartite graph matching problem. Then a hybrid similarity model with high tolerance of inversion, crossover and noise is proposed for matching the corresponding bipartite graphs involving both temporal and non-temporal measurements. Experimental results on reconstructed time-series data from UCI KDD Archive demonstrate that such an approach is more effective comparing with the traditional similarity model based algorithms, promising robust techniques for lager time-series databases and real-life applications such as Content-based Video Retrieval (CBVR), etc.

Ecological Investigations with the Continuous Plankton Recorder: The Phytoplankton in the Southern North Sea. 1932-37.

1. The changes in the composition and distribution of the plankton of the southern North Sea have been investigated month by month, from June 1932 to December 1937; the present report deals with the phytoplankton. The survey was carried out by the Continuous Plankton Recorder, towed at a standard depth of 10 metres, by ships on regular steamship lines across the North Sea from Hull towards the Skagerrak, to Bremen and to Rotterdam, and later between London and Esbjerg. 2. The material and methods are described, together with a discussion on the validity of this type of survey and some comparison of its results with those obtained by other methods (pp. 76-86). 3. Particular attention has been paid to Rhizosolenia styliformis (pp. 92- 107), Biddulphia sinensis (pp. 108-115), Phaeocystis (pp. 149-153), and the Dinoflagellates (pp. 134-149); of these the first three are known to be of particular importance in relation to the herring fisheries. More generalised data are available for the principal diatoms other than R. styliformis and B. sinensis (pp. 116-134). 4. The main part of the work is an ecological study of the phytoplankton changes in time and space over the 5½ years. Each year is marked by some distinct variations in the abundance and the times of increase, maximum numbers and decline as recorded in the different forms. These variations in the annual cycles are compared on the different lines by a series of graphs arranged against a time scale of months, a set for each year being placed side by side (Plates I-XXI). More detailed studies by more frequent records were made in the autumns of 1934, 1935, 1936 and 1937 (cf. Figs. 3 and 4). The changes in spatial distribution are shown by a series of monthly maps arranged in a similar manner for each year (Plates XXII-LXIV). These intensive studies of the changes in time and space are also intended to form the basis for correlations with other features in the general ecology of the area (e. g. the zooplankton, hydrology, meteorology and fisheries) to be made in later publications. 5. Whilst each form has shown its own peculiar features, a trend towards a general increase in the phytoplankton as a whole has been observed during the period, although the years 1934 and 1936 have in some respects shown deviations and regressive features, and not all organisms have revealed the same trend. The possible relation of this gradual trend to other events observed in recent years in these and neighbouring waters is discussed (pp. 162-167). 6. The application of these results to the study of patchiness (pp. 154-158), inter-relationships in the plankton (pp. 159-160) and to water movements (pp. 160-162) is briefly discussed.

Fecundity and reproductive strategies in deep-sea incirrate octopuses (Cephalopoda: Octopoda).

Coleoid cephalopods show flexibility in their reproductive strategies or mode of spawning, which can range from simultaneous terminal spawning over a short period at the end of the animal’s life to continuous spawning over a long period of the animal’s life. Although a simultaneous terminal spawning strategy is typical of shallow water temperate octopuses, it is not known whether deep-sea octopods would have the same reproductive strategy. The reproductive strategies and fecundity were investigated in nine species of deep-sea incirrate octopuses: Bathypolypus arcticus, Bathypolypus bairdii, Bathypolypus ergasticus, Bathypolypus sponsalis, Bathypolypus valdiviae, Benthoctopus levis, Benthoctopus normani, Benthoctopus sp., and Graneledone verrucosa (total n = 85). Egg-length frequency graphs and multivariate analysis (principal components analysis) suggest that B. sponsalis has a synchronous ovulation pattern and therefore a simultaneous terminal spawning strategy. Although a simultaneous terminal spawning strategy is most likely for B. levis and B. normani, the egg-length frequency graphs and multivariate analysis also suggest a greater variation in egglengths which could lead to spawning over an extended period.

Compact Toffoli gate using weighted graph states

We introduce three compact graph states that can be used to perform a measurement-based Toffoli gate. Given a weighted graph of six, seven, or eight qubits, we show that success probabilities of 1/4, 1/2, and 1, respectively, can be achieved. Our study puts a measurement-based version of this important quantum logic gate within the reach of current experiments. As the graphs are setup independent, they could be realized in a variety of systems, including linear optics and ion traps.

The chronic fatigue syndrome: A comparative pathway analysis

In this paper, we introduce a method to detect pathological pathways of a disease. We aim to identify biological processes rather than single genes affected by the chronic fatigue syndrome (CFS). So far, CFS has neither diagnostic clinical signals nor abnormalities that could be diagnosed by laboratory examinations. It is also unclear if the CFS represents one disease or can be subdivided in different categories. We use information from clinical trials, the gene ontology (GO) database as well as gene expression data to identify undirected dependency graphs (UDGs) representing biological processes according to the GO database. The structural comparison of UDGs of sick versus non-sick patients allows us to make predictions about the modification of pathways due to pathogenesis.

Rigorous conditions for food-web intervality in high-dimensional trophic niche spaces

Food webs represent trophic (feeding) interactions in ecosystems. Since the late 1970s, it has been recognized that food-webs have a surprisingly close relationship to interval graphs. One interpretation of food-web intervality is that trophic niche space is low-dimensional, meaning that the trophic character of a species can be expressed by a single or at most a few quantitative traits. In a companion paper we demonstrated, by simulating a minimal food-web model, that food webs are also expected to be interval when niche-space is high-dimensional. Here we characterize the fundamental mechanisms underlying this phenomenon by proving a set of rigorous conditions for food-web intervality in high-dimensional niche spaces. Our results apply to a large class of food-web models, including the special case previously studied numerically.

The structural information content of chemical networks

We present an information-theoretic method to measure the structural information content of networks and apply it to chemical graphs. As a result, we find that our entropy measure is more general than classical information indices known in mathematical and computational chemistry. Further, we demonstrate that our measure reflects the essence of molecular branching meaningfully by determining the structural information content of some chemical graphs numerically.

Structural information content of networks: Graph entropy based on local vertex functionals

In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties. (C) 2007 Elsevier Ltd. All rights reserved.

Algorithmic computation of knot polynomials of secondary structure elements of proteins

The classification of protein structures is an important and still outstanding problem. The purpose of this paper is threefold. First, we utilize a relation between the Tutte and homfly polynomial to show that the Alexander-Conway polynomial can be algorithmically computed for a given planar graph. Second, as special cases of planar graphs, we use polymer graphs of protein structures. More precisely, we use three building blocks of the three-dimensional protein structure-alpha-helix, antiparallel beta-sheet, and parallel beta-sheet-and calculate, for their corresponding polymer graphs, the Tutte polynomials analytically by providing recurrence equations for all three secondary structure elements. Third, we present numerical results comparing the results from our analytical calculations with the numerical results of our algorithm-not only to test consistency, but also to demonstrate that all assigned polynomials are unique labels of the secondary structure elements. This paves the way for an automatic classification of protein structures.