Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.

The potential of microbial ecological indicators to guide ecosophisticated management of hydrocarbon-contaminated soils

Soil is an unrenewable natural resource under increasing anthropogenic pressure. One of the main threats to soils, compromising their ability to provide us with the goods and ecosystem services we expect, is pollution. Oil hydrocarbons are the most common soil contaminants, and they disturb not just the biota but also the physicochemical properties of soils. Indigenous soil micro-organisms respond rapidly to changes in the soil ecosystem, and are chronically in direct contact with the hydrophobic pollutants on the soil surfaces. Soil microbial variables could thus serve as an intrinsically relevant indicator of soil quality, to be used in the ecological risk assessment of contaminated and remediated soils. Two contrasting studies were designed to investigate soil microbial ecological responses to hydrocarbons, together with parallel changes in soil physicochemical and ecotoxicological properties. The aim was to identify quantitative or qualitative microbiological variables that would be practicable and broadly applicable for the assessment of the quality and restoration of oil-polluted soil. Soil bacteria commonly react on hydrocarbons as a beneficial substrate, which lead to a positive response in the classical microbiological soil quality indicators; negative impacts were accurately reflected only after severe contamination. Hydrocarbon contaminants become less bioavailable due to weathering processes, and their potentially toxic effects decrease faster than the total concentration. Indigenous hydrocarbon degrader bacteria, naturally present in any terrestrial environment, use specific mechanisms to improve access to the hydrocarbon molecules adsorbed on soil surfaces. Thus when contaminants are unavailable even to the specialised degraders, they should pose no hazard to other biota either. Change in the ratio of hydrocarbon degrader numbers to total microbes was detected to predictably indicate pollutant effects and bioavailability. Also bacterial diversity, a qualitative community characteristic, decreased as a response to hydrocarbons. Stabilisation of community evenness, and community structure that reflected clean reference soil, indicated community recovery. If long-term temporal monitoring is difficult and appropriate clean reference soil unavailable, such comparison could possibly be based on DNA-based community analysis, reflecting past+present, and RNA-based community analysis, showing exclusively present conditions. Microbial ecological indicators cannot replace chemical oil analyses, but they are theoretically relevant and operationally practicable additional tools for ecological risk assessment. As such, they can guide ecologically informed and sustainable ecosophisticated management of oil-contaminated lands.