More Like this

1. Width Helps and Hinders Splitting Flows

   https://doi.org/10.1145/3641820  

   Cáceres, Manuel ; Cairo, Massimo ; Grigorjew, Andreas ; Khan, Shahbaz ; Mumey, Brendan ; Rizzi, Romeo ; Tomescu, Alexandru I. ; Williams, Lucia ( April 2024 , ACM Transactions on Algorithms)

   Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulationXon a directed graphGinto weighted source-to-sink paths whose weighted sum equalsX. We show that, for acyclic graphs, considering thewidthof the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stablegraphs, for which a popular heuristic is aO(logVal(X))-approximation (Val(X) being the total flow ofX), and strengthen its worst-case approximation ratio from\(\Omega (\sqrt {m})\)to Ω (m/logm) for sparse graphs, wheremis the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X‖ being the maximum absolute value ofXon any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.

    

   more » « less
2. Fluctuations of subgraph counts in graphon based random graphs

   https://doi.org/10.1017/S0963548322000335  

   Bhattacharya, Bhaswar B. ; Chatterjee, Anirban ; Janson, Svante ( May 2023 , Combinatorics, Probability and Computing)

   Abstract Given a graphon $W$ and a finite simple graph $H$ , with vertex set $V(H)$ , denote by $X_n(H, W)$ the number of copies of $H$ in a $W$ -random graph on $n$ vertices. The asymptotic distribution of $X_n(H, W)$ was recently obtained by Hladký, Pelekis, and Šileikis [17] in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$ . Towards this we introduce a notion of $H$ -regularity of graphons and show that if the graphon $W$ is not $H$ -regular, then $X_n(H, W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-\frac{1}{2}}$ . On the other hand, if $W$ is $H$ -regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H, W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$ . Our proofs use the asymptotic theory of generalised $U$ -statistics developed by Janson and Nowicki [22]. We also investigate the structure of $H$ -regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$ -regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H, W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$ . We give an example of this degeneracy with $H=K_{1, 3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies. 

   more » « less
3. Reluctant Generalised Additive Modelling

   https://doi.org/10.1111/insr.12429  

   Tay, J. Kenneth ; Tibshirani, Robert ( November 2020 , International Statistical Review)

   Sparse generalised additive models (GAMs) are an extension of sparse generalised linear models that allow a model's prediction to vary non‐linearly with an input variable. This enables the data analyst build more accurate models, especially when the linearity assumption is known to be a poor approximation of reality. Motivated by reluctant interaction modelling, we propose a multi‐stage algorithm, calledreluctant generalised additive modelling (RGAM), that can fit sparse GAMs at scale. It is guided by the principle that, if all else is equal, one should prefer a linear feature over a non‐linear feature. Unlike existing methods for sparse GAMs, RGAM can be extended easily to binary, count and survival data. We demonstrate the method's effectiveness on real and simulated examples.

    

   more » « less
4. Are spatial patterns of soil moisture at plot scales generalisable across catchments, climates, and other characteristics? A synthesis of synoptic soil moisture across the Mid‐Atlantic

   https://doi.org/10.1002/hyp.14313  

   Scaife, Charles I. ; Duncan, Jonathan M. ; Lin, Laurence ; Tague, Christina ; Bell, Colin D. ; Band, Lawrence ( September 2021 , Hydrological Processes)

   The spatial variation of soil moisture over very small areas (<100 m²) can have nonlinear impacts on cycling and flux rates resulting in bias if it is not considered, but measuring this variation is difficult over extensive temporal and spatial scales. Most studies examining spatial variation of soil moisture were conducted at hillslope (0.01 km²) to multi‐catchment spatial scales (1000 km²). They found the greatest variation at mid wetness levels and the smallest variation at wet and dry wetness levels forming a concave down relationship. There is growing evidence that concave down relationships formed between spatial variation of soil moisture and average soil moisture are consistent across spatial scales spanning several orders of magnitude, but more research is needed at very small, plot scales (<100 m²). The goal of this study was to characterise spatial variation in shallow soil moisture at the plot scale by relating the mean of measurements collected in a plot to the standard deviation (SD). We combined data from a previous study with thousands of new soil moisture measurements from 212 plots in eight catchments distributed across the US Mid‐Atlantic Region to (1) test for a generalisable mean–SD relationship at plot scales, (2) characterise how landcover, land use, season, and hillslope position contribute to differences in mean–SD relationships, and (3) use these generalised mean–SD relationships to quantify their impacts on catchment scale nitrification and denitrification potential. Our study found that 98% of all measurements formed a generalised mean–SD relationship like those observed at hillslope and catchment spatial scales. The remaining 2% of data comprised a mean–SD relationship with greater spatial variation that originated from two riparian plots reported in a previous study. Incorporating the generalised mean–SD relationship into estimates of nitrification and denitrification potential revealed strong bias that was even greater when incorporating mean–SD observations from the two riparian plots with significantly greater spatial variation.

    

   more » « less
5. A changing menu in a changing climate: Using experimental and long‐term data to predict invertebrate prey biomass and availability in lakes of arctic Alaska

   https://doi.org/10.1111/fwb.13162  

   Klobucar, Stephen L. ; Gaeta, Jereme W. ; Budy, Phaedra ( August 2018 , Freshwater Biology)

   Changes in seasonality associated with climate warming (e.g. temperature, growing season duration) are likely to alter invertebrate prey biomass and availability in aquatic ecosystems through direct and indirect influences on physiology and phenology, particularly in arctic lakes. However, despite warmer thermal regimes, photoperiod will remain unchanged such that potential shifts resulting from longer and warmer growing seasons could be limited by availability of sunlight, especially at lower trophic levels. Thus, a better understanding of warming effects on invertebrate prey throughout the growing season (e.g. early, peak, late) is important to understand arctic lake food‐web dynamics in a changing climate.

   Here, we use a multifaceted approach to evaluate prey availability to predators in lakes of arctic Alaska. In a laboratory mesocosm experiment, we measured different metrics of abundance for snails (Lymnaea elodes) and zooplankton (Daphnia middendorffiana) across three time periods (early, mid‐ and late growing season) and across three temperature and photoperiod treatments (control, increased temperature and increased temperature × photoperiod). Additionally, we used generalised additive models and generalised additive mixed‐effects models to relate long‐term empirical observations of zooplankton biomass (1983–2015) to observed temperature regimes in an arctic lake. We then simulated zooplankton biomass for the warmest temperature observations across the growing season to inform likely zooplankton biomass regimes under future change.

   We observed variable responses by snails and zooplankton across experiments and treatments. Early in the growing season, snail development was accelerated at multiple life stages (e.g. egg and juvenile). In mid‐season, in accordance with warmer temperatures, we observed significantly increasedDaphniaabundances. However, in the late season,Daphniaappeared to be limited by photoperiod. Confirming our experimental results, our models of zooplankton biomass showed an increase of nearly 20% in warmer years. Further, these model estimates could be conservative as the consumptive demand of fishes may increase in warmer years as well.

   Overall, our results highlight the importance of interactive effects of temperature and seasonality. Based primarily on temperature, we can readily predict the response of fish metabolism in warmer temperatures. However, in this context, we generally require a better understanding of climate‐driven responses of important invertebrate prey resources. Our results suggest invertebrate prey biomass and availability are likely to respond positively with climate change based on temperature and seasonality, as well as proportionally to the metabolic requirements of fish predators. While further research is necessary to understand how other food‐web components will respond climate change, our findings suggest that the fish community at the top of arctic lake food webs will have adequate prey base in a warming climate.

    

   more » « less