TY - JOUR
A1 - Massie, Thomas Michael
A1 - Ryabov, Alexei
A1 - Blasius, Bernd
A1 - Weithoff, Guntram
A1 - Gaedke, Ursula
T1 - Complex transient dynamics of stage-structured populations in response to environmental changes
JF - The American naturalist : a bi-monthly journal devoted to the advancement and correlation of the biological sciences
N2 - Stage structures of populations can have a profound influence on their dynamics. However, not much is known about the transient dynamics that follow a disturbance in such systems. Here we combined chemostat experiments with dynamical modeling to study the response of the phytoplankton species Chlorella vulgaris to press perturbations. From an initially stable steady state, we altered either the concentration or dilution rate of a growth-limiting resource. This disturbance induced a complex transient response-characterized by the possible onset of oscillations-before population numbers relaxed to a new steady state. Thus, cell numbers could initially change in the opposite direction of the long-term change. We present quantitative indexes to characterize the transients and to show that the dynamic response is dependent on the degree of synchronization among life stages, which itself depends on the state of the population before perturbation. That is, we show how identical future steady states can be approached via different transients depending on the initial population structure. Our experimental results are supported by a size-structured model that accounts for interplay between cell-cycle and population-level processes and that includes resource-dependent variability in cell size. Our results should be relevant to other populations with a stage structure including organisms of higher order.
KW - chemostat experiments
KW - Chlorella vulgaris
KW - environmental changes
KW - population dynamics
KW - stage structure
KW - transient dynamics
Y1 - 2013
U6 - https://doi.org/10.1086/670590
SN - 0003-0147
SN - 1537-5323
VL - 182
IS - 1
SP - 103
EP - 119
PB - Univ. of Chicago Press
CY - Chicago
ER -
TY - JOUR
A1 - Massie, Thomas Michael
A1 - Weithoff, Guntram
A1 - Kucklaender, Nina
A1 - Gaedke, Ursula
A1 - Blasius, Bernd
T1 - Enhanced Moran effect by spatial variation in environmental autocorrelation
JF - Nature Communications
N2 - Spatial correlations in environmental stochasticity can synchronize populations over wide areas, a phenomenon known as the Moran effect. The Moran effect has been confirmed in field, laboratory and theoretical investigations. Little is known, however, about the Moran effect in a common ecological case, when environmental variation is temporally autocorrelated and this autocorrelation varies spatially. Here we perform chemostat experiments to investigate the temporal response of independent phytoplankton populations to autocorrelated stochastic forcing. In contrast to naive expectation, two populations without direct coupling can be more strongly correlated than their environmental forcing (enhanced Moran effect), if the stochastic variations differ in their autocorrelation. Our experimental findings are in agreement with numerical simulations and analytical calculations. The enhanced Moran effect is robust to changes in population dynamics, noise spectra and different measures of correlation-suggesting that noise-induced synchrony may play a larger role for population dynamics than previously thought.
Y1 - 2015
U6 - https://doi.org/10.1038/ncomms6993
SN - 2041-1723
VL - 6
PB - Nature Publ. Group
CY - London
ER -
TY - JOUR
A1 - Birnick, Johann
A1 - Bläsius, Thomas
A1 - Friedrich, Tobias
A1 - Naumann, Felix
A1 - Papenbrock, Thorsten
A1 - Schirneck, Friedrich Martin
T1 - Hitting set enumeration with partial information for unique column combination discovery
JF - Proceedings of the VLDB Endowment
N2 - Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations.
In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
Y1 - 2020
U6 - https://doi.org/10.14778/3407790.3407824
SN - 2150-8097
VL - 13
IS - 11
SP - 2270
EP - 2283
PB - Association for Computing Machinery
CY - [New York, NY]
ER -
TY - JOUR
A1 - Bläsius, Thomas
A1 - Freiberger, Cedric
A1 - Friedrich, Tobias
A1 - Katzmann, Maximilian
A1 - Montenegro-Retana, Felix
A1 - Thieffry, Marianne
T1 - Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
JF - ACM Transactions on Algorithms
N2 - A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry.
To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
KW - Random graphs
KW - hyperbolic geometry
KW - scale-free networks
KW - bidirectional shortest path
Y1 - 2022
U6 - https://doi.org/10.1145/3516483
SN - 1549-6325
SN - 1549-6333
VL - 18
IS - 2
SP - 1
EP - 32
PB - Association for Computing Machinery
CY - New York
ER -
TY - JOUR
A1 - Bläsius, Thomas
A1 - Friedrich, Tobias
A1 - Lischeid, Julius
A1 - Meeks, Kitty
A1 - Schirneck, Friedrich Martin
T1 - Efficiently enumerating hitting sets of hypergraphs arising in data profiling
JF - Journal of computer and system sciences : JCSS
N2 - The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
KW - Data profiling
KW - Enumeration algorithm
KW - Minimal hitting set
KW - Transversal hypergraph
KW - Unique column combination
KW - W[3]-Completeness
Y1 - 2022
U6 - https://doi.org/10.1016/j.jcss.2021.10.002
SN - 0022-0000
SN - 1090-2724
VL - 124
SP - 192
EP - 213
PB - Elsevier
CY - San Diego
ER -