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.

Understanding and predicting ecological dynamics: Are major surprises inevitable?

Ecological surprises, substantial and unanticipated changes in the abundance of one or more species that result from previously unsuspected processes, are a common outcome of both experiments and observations in community and population ecology. Here, we give examples of such surprises along with the results of a survey of well-established field ecologists, most of whom have encountered one or more surprises over the course of their careers. Truly surprising results are common enough to require their consideration in any reasonable effort to characterize nature and manage natural resources. We classify surprises as dynamic-, pattern-, or intervention-based, and we speculate on the common processes that cause ecological systems to so often surprise us. A long-standing and still growing concern in the ecological literature is how best to make predictions of future population and community dynamics. Although most work on this subject involves statistical aspects of data analysis and modeling, the frequency and nature of ecological surprises imply that uncertainty cannot be easily tamed through improved analytical procedures, and that prudent management of both exploited and conserved communities will require precautionary and adaptive management approaches.

Ecological coherence in marine reserve network design: an empirical evaluation of sequential site selection using genetic structure

Ecological coherence is a multifaceted conservation objective that includes some potentially conflicting concepts. These concepts include the extent to which the network maximises diversity (including genetic diversity) and the extent to which protected areas interact with non-reserve locations. To examine the consequences of different selection criteria, the preferred location to complement protected sites was examined using samples taken from four locations around each of two marine protected areas: Strangford Lough and Lough Hyne, Ireland. Three different measures of genetic distance were used: FST, Dest and a measure of allelic dissimilarity, along with a direct assessment of the total number of alleles in different candidate networks. Standardized site scores were used for comparisons across methods and selection criteria. The average score for Castlehaven, a site relatively close to Lough Hyne, was highest, implying that this site would capture the most genetic diversity while ensuring highest degree of interaction between protected and unprotected sites. Patterns around Strangford Lough were more ambiguous, potentially reflecting the weaker genetic structure around this protected area in comparison to Lough Hyne. Similar patterns were found across species with different dispersal capacities, indicating that methods based on genetic distance could be used to help maximise ecological coherence in reserve networks. ⺠Ecological coherence is a key component of marine protected area network design. ⺠Coherence contains a number of competing concepts. ⺠Genetic information from field populations can help guide assessments of coherence. ⺠Average choice across different concepts of coherence was consistent among species. ⺠Measures can be combined to compare the coherence of different network designs.

Body size in ecological networks

Body size determines a host of species traits that can affect the structure and dynamics of food webs, and other ecological networks, across multiple scales of organization. Measuring body size provides a relatively simple means of encapsulating and condensing a large amount of the biological information embedded within an ecological network. Recently, important advances have been made by incorporating body size into theoretical models that explore food web stability, the patterning of energy fluxes, and responses to perturbations. Because metabolic constraints underpin bodysize scaling relationships, metabolic theory offers a potentially useful new framework within which to develop novel models to describe the structure and functioning of ecological networks and to assess the probable consequences of biodiversity change.