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 -