Schedule for: 19w5071 - Scaling Limits of Dynamical Processes on Random Graphs

We generalize random walks on graphs to random walks on simplicial complexes, also called hypergraphs, using some notions of topological algebra. The transition matrix of this RW is related to the higher order Laplacian which is the generalization of graph Laplacian. We also analyze the limit behavior of this RW when the number of points in the simplicial complex tends to infinity.

Biochemical reaction networks (BRNs) in a cell frequently consist of reactions with disparate timescales. The stochastic simulations of such multiscale BRNs are prohibitively slow due to the high computational cost for the simulations of fast reactions. One way to resolve this problem is replacing the fast species with their quasi-steady state (QSS): their stationary conditional expectation values for given slow species. In this talk, I will describe types of BRNs which can be reduced by deriving an exact QSS even in the presence of non-linear reactions. Furthermore, in the case when the exact QSS cannot be derived, I will describe how we can derive the approximate QSS. Finally, I will illustrate how the accurately reduced BRNs can be used to identify molecular mechanism underlying robust circadian rhythms and predict accurate drug clearance in the liver.

We discuss critical behavior of percolation on finite random networks. In a seminal paper, Aldous (1997) identified the scaling limit for the component sizes in the critical window of phase transition for the Erdos-Renyi random graph (ERRG). Subsequently, there has been a surge in the literature, revealing several interesting scaling limits of these critical components, namely, the component size, diameter, or the component itself when viewed as a metric space. Fascinatingly, when the third moment of the asymptotic degree distribution is finite, many random graph models have been shown to exhibit a universality phenomenon in the sense that their scaling exponents and limit laws are the same as the ERRG. In contrast, when the asymptotic degree distribution is heavy-tailed (having an infinite third moment), the limit law turns out to be fundamentally different from the ERRG case and in particular, becomes sensitive to the precise asymptotics of the highest degree vertices. In this talk, we will focus on random graphs with a prescribed degree sequence. We start by discussing recent scaling limit results, and explore the universality classes that arise from heavy-tailed networks. Of particular interest is a new universality class that arises when the asymptotic degree distribution has an infinite second moment. Not only it gives rise to a completely new universality class, it also exhibits several surprising features that have never been observed in any other universality class so far. This is based on joint works with Shankar Bhamidi, Remco van der Hofstad, Johan van Leeuwaarden and Sanchayan Sen.

The ferromagnetic Ising model is a paradigmatic model of statistical physics used to study phase transitions in lattice systems. In this talk I shall consider the setting where the regular spatial structure is replaced by a random graph, which is often used to model complex networks. I shall treat both the case where the graph is essentially frozen (quenched setting) and the case where instead it is rapidly changing (annealed setting). I shall prove that quenched and annealed may have different critical temperatures, provided the graph has sufficient inhomogeneity. I shall also discuss how universal results (law of large numbers, central limit theorems, critical exponents) are affected by the disorder in the spatial structure. The picture that I will present emerges from several joint works, involving V.H. Can, S. Dommers, C. Giberti, R.van der Hofstad and M.L.Prioriello.

We study diffusion-driven pattern formation in a class of multilayer systems, where different layers have the same topology, but different internal dynamics. Agents are assumed to disperse within a layer by undergoing random walks, while they can be created or destroyed by reactions between or within a layer. We show that the stability of homogeneous steady states can be analyzed with a master stability function approach that reveals a deep analogy between pattern formation in networks and pattern formation in continuous space. For illustration, we consider a generalized model of ecological meta-food webs. This fairly complex model describes the dispersal of many different species across a region consisting of a network of individual habitats while subject to realistic, nonlinear predator-prey interactions. In this example, the method reveals the intricate dependence of the dynamics on the spatial structure. The ability of the proposed approach to deal with this fairly complex system highlights it as a promising tool for ecology and other applications.

The main object of study in this paper is an epidemic process on a large network in the presence of various public health interventions. As an example, we consider a simple Susceptible-Infected (SI)-type epidemic process on a Configuration Model (CM) random graph with public health interventions in the form of active random surveillance and contact-tracing. While infected individuals attempt to infect their neighbours, they themselves are at risk of removal due to random surveillance and contact-tracing. We allow the random graph to be constructed dynamically as an outcome of the spread of infection and removal due to contact-tracing. We study the large graph limit of these two competing processes (infection and contact-tracing) as the number of vertices grows to infinity. From the public health perspective, the large graph limit can be utilized to determine the optimal rates for surveillance and contact-tracing given a fixed budget constraint by formulating a suitable optimal control problem. Joint work with Soheil Eshghi, Eben Kenah, Forrest W. Crawford and Grzegorz A. Rempała.

A common goal in the domain of systems and synthetic biology is to understand the relationship between design and function of gene regulatory networks. This is a significant challenge for several reasons. Typically understanding the behavior of a gene regulatory network means understanding the associated dynamics. Traditionally this requires having an acceptable nonlinear model, knowledge of parameter values, and knowledge of initial conditions, all of which are difficult to obtain in the setting of complex multi-scale problems. To circumvent these challenges we have developed a novel approach to nonlinear dynamics based on order theory and algebraic topology. This method allows for efficient computations of rigorous combinatorial/algebraic topological descriptions of the global dynamics over large ranges of parameter space. As a consequence, given a regulatory network, we are able to construct a database describing all the associated dynamics. I will discuss the theory behind this tool and demonstrate how it can be applied to specific examples.

Consider a system of N parallel single-server queues with unit-exponential service time distribution and a single dispatcher where tasks arrive as a Poisson process of rate l(N). When a task arrives, the dispatcher assigns it to one of the servers according to the Join-the-Shortest Queue (JSQ) policy. Eschenfeldt and Gamarnik (2015) established that appropriately scaled functionals of the queueing network under the JSQ policy converge weakly to associated functionals for a certain non-elliptic reflected diffusion process as N grows. I will talk about analyzing the detailed behavior of the steady state of this non-standard diffusion process using tools from renewal theory. The tails and bulk behavior of the steady state distribution and sample path fluctuations of the diffusion process will be explored. We will also see how the steady state shows a stark difference in behavior between two regimes governed by a system parameter. This is joint work with Debankur Mukherjee.

I will discuss a class of random spatial networks and show that they have small world-like properties, but the level of clustering is tunable and we can make it arbitrarily small. In some limits we are able to derive a system of integro-differential equations which allows us to accurately predict both the temporal and spatial dynamics of SIR disease. We can use these equations to determine when the network behaves like a small world network with significant long-range transmissions and when the dynamics are dominated by the short-range transmission. Interestingly, we show that the "small-world" properties of disease spread can exist even in the limit of no clustering, and thus the concept of a small-world network is determined more by whether the network has a combination of short-range and long-range connections than whether the network has many clustered connections.

I will present comparisons between large-scale stochastic simulations and mean-field theories for the epidemic thresholds and prevalence of the susceptible-infected-susceptible (SIS) model on networks with power-law degree distributions and degree correlations. We confirm the vanishing of the threshold regardless of the correlation pattern and degree exponent. The thresholds are compared with heterogeneous mean-field (HMF), quenched mean-field (QMF) and pair quenched mean-field (PQMF) theories where the degree correlation patterns are explicitly considered. The PQMF, which additionally reckons dynamical correlations, outperforms the other two theories and its level of quantitative success depends on the type of degree correlation (assortative, disassortative or uncorrelated). Furthermore, we observe a strong correlation between the success of PQMF theory and the properties of the principal eigenvector such as the inverse participation ration (IPR) and the spectral gap. If the IPR is large and tends to a finite value at the limit of large networks the PQMF predictions deviate from numerical simulations. Otherwise, if the IPR is small, PQMF theory shows an excellent match with the simulations. Finally, the epidemic prevalence near to the critical point and the corresponding critical exponents are compared with both QMF theory and exact results.

As highlighted in a recent perspective article (Science 359:738, 2018), in ecology, exact predictions are extremely challenging. In the presentation, we ask how do species evolve in environments with asymmetric fluctuating temperature profiles. We study how natural selection do not lead to adaption to the mean temperature but to a value that is shifted and given by the skewness of the temperature profile. This prediction is derived from first principles and first results are presented in nematodes. More generally, we discuss effects from ergodicity breaking for evolutionary game theory (Stollmeier & Nagler, Phys. Rev. Lett. 120:058101, 2018), coupled ecosystems and for climate change. In the final part, we ask how to beat seemingly universally optimal strategies (Extortion Zero Determinant Strategies) and how seemingly unresolvable conflicts (such as Prisoner's dilemmas) can be resolved in complex noisy environments and how does machine intelligence (Timme & Nagler, Nature Phys. 15:308, 2019) helps in noisy systems.

Consider a large community, structured as a network, in which an epidemic spreads. Infectious individuals spread the disease to each of their susceptible neighbors, independently, at rate $\lambda$, and each infectious individual recovers and becomes immune at rate $\gamma$. The social distancing is modeled by each susceptible who has an infectious neighbor rewires away this individual to a randomly chosen individual at rate $\omega$. Our main result is surprising and says: the rewiring is rational from an individual perspective in that it reduces the risk of being infected, but at the same time it may be harmful for the community at large since the outbreak may get bigger compared to no rewiring ($\omega=0$). Joint work with Frank Ball, KaYin Leung and David Sirl (Interface, 2018, doi/10.1098/rsif.2018.0296)

Epidemic models are increasingly applied in real-world networks to understand various kinds of diffusion phenomena (such as the spread of diseases, emotions, innovations, failures) or the transport of information (such as news, memes in social on-line networks and activity in functional human brain networks). We will mainly focus on Susceptible-Infected-Susceptible (SIS) epidemics on networks. We believe that the SIS Markovian epidemics on a given, fixed graph is one of the simplest "local rule - global emergence" models that allows a remarkable level of analysis. After a brief review of the SIS continuous-time Markovian process on a graph, we will show why SIS epidemics on networks are so interesting and we will overview our recent developments.

In a recent paper KhudaBukhsh et al., we showed that solutions to Ordinary Differential Equations (ODEs) describing the large-population limits of Markovian stochastic compartmental dynamical systems can be interpreted as survival or hazard functions when analyzing data from individuals sampled from the population. An earlier paper by Kenah showed that likelihoods from individual-level mass-action transmission models simplify in the limit of a large population when the depletion of susceptibles is negligible. In this paper, we unify and generalize these results by deriving population-level survival and hazard functions from explicit individual-level models. This allows population-level survival analysis to be applied to a more general class of epidemic models and allows the asymptotic pairwise likelihoods to be applied throughout the course of an epidemic. In practice, this will provide a logically consistent framework for the analysis of both high-resolution outbreak investigations or household studies and population-level surveillance or sentinel data.

The (classical) contact process is a stochastic process on the vertices of a graph, which is a discrete, spatial model for the spread of a disease. The state of the contact process at time t is given by an infected subset of the vertices of the graph. At rate 1, each infected vertex becomes healthy, and therefore susceptible to reinfection. At rate lambda>0, each edge between an infected vertex and a healthy vertex transmits the infection, thus infecting the healthy vertex. The contact process has been thoroughly analyzed on the integer lattices and regular trees, where it is well-known to exhibit a phase transition: for large lambda, epidemics persist, while for smaller lambda, all vertices are eventually healthy. More recently, researchers have made progress in analyzing the behavior of the contact process on (finite) complex networks, where epidemics may persist for all lambda>0 on graphs with `heavy-tailed' degree distributions. I will discuss recent progress on a version of the contact process in which the edges of the graph are also dynamic: at rate alpha, each edge from an infected vertex to a healthy vertex will deactivate; the edge will become active again when the infected vertex becomes healthy, and only active edges can transmit the infection. This emulates avoidance of infected individuals by healthy individuals. We demonstrate that the long-time qualitative behavior of this model may or may not differ from the classical contact process, depending on the underlying network topology. A technical obstacle is the lack of a certain type of monotonicity, which is present for the classical model. Based on joint work with Shirshendu Chatterjee and Matthew Wascher.

The process we consider are voter model perturbations in the sense of Cox, Durrett, and Perkins. We will describe results for two examples: evolutionary games with weak selection and the latent voter model in which individuals who adopt a new technology (e.g. buy an iPhone) have a latent period in which they will not change their state. These examples were analyzed in joint work with Ted Cox (EG) and Ran Huo (LVM). The relevant papers are 179, 202 and 203 on my web page.

Stochastic models of populations have a long history beginning with branching processes and continuing with models in population genetics and models of the spatial distribution of populations. At the same time, models of population genealogies were developed in the population genetics literature. Work with Peter Donnelly (1999) showed how to simultaneously construct models that include both the forward in time evolution of the population distribution and the backward in time genealogy starting at any time point in the forward in time evolution. These "lookdown" constructions were essentially restricted to neutral models, that is, models in which birth rates, offspring distributions, and death rates do not depend on the types or locations of the individuals in the population. Following some earlier preliminary results, work with Eliane Rodrigues (2011) gave lookdown constructions for general Markov branching processes in which the birth rates, offspring distributions, and death rates can depend on the location/type of the individual. Extension of these lookdown/genealogical constructions to very general Markov population models, to appear in a forthcoming paper with Alison Etheridge, will be discussed.

The idea of a survival dynamical system (SDS) is to apply aggregated dynamics of a macro model at the level of an individual agent. SDS may be also viewed a limit of agents’ dynamics obtained when replacing individual’s random hazard function with its large volume limit. Under this second interpretation it is relatively simple to obtain an extension of the classical mass-action SDS to a configuration model random graph and to provide some basic results allowing for estimating the underlying epidemic parameters from micro-level data. As it turns out, in a certain class of degree distributions the SDS model takes a particularly simple from and its statistical analysis is only moderately more complicated than the classical mass-action SDS as given by the standard SIR equations.

The theory of large deviations gives decay rates of probabilities of rare events in terms of certain optimal control problems. In general these control problems do not admit simple form solutions and one needs numerical methods in order to obtain useful information. In this talk I will present some large deviation problems where one can use methods of calculus of variations to give explicit solutions to the associated optimal control problems. These solutions then yield explicit asymptotic formulas for probability decay rates in several settings. The case of the Configuration Model will be discussed in detail.

Very large networks linking dynamical agents are now ubiquitous and there is significant interest in their analysis, design and control. The emergence of the graphon theory of large networks and their infinite limits has recently enabled the formulation of a theory of the centralized control of dynamical systems distributed on asymptotically infinite networks [Gao and Caines, IEEE CDC 2017, 2018]. Furthermore, the study of the decentralized control of such systems has been initiated in [Caines and Huang, IEEE CDC 2018] where Graphon Mean Field Games (GMFG) and the GMFG equations are formulated for the analysis of non-cooperative dynamical games on unbounded networks. In this talk the GMFG framework will be first be presented followed by the basic existence and uniqueness results for the GMFG equations, together with an epsilon-Nash theorem relating the infinite population equilibria on infinite networks to that of finite population equilibria on finite networks.

Seemingly trivial modifications to the classical model of contagion spreading can dramatically alter its phenomenology. For example, discontinuous phase transitions can occur due to complex or interacting contagions, accelerating transmission and hysteresis loops can occur when individuals modify their behaviour after becoming infectious, and double phase transitions can emerge in the presence of asymmetric percolation. In this talk, I will present recent theoretical work on the affect of behaviour on contagion spreading and discuss empirical support for these new models. Our findings demonstrate the inherent complexity of biological contagion and we anticipate that our methods will advance the emerging field of disease forecasting.

Inferring gene regulatory networks from high-throughput omics data is a challenging statistical and computational problem. Classical inferential methods are known to break down due to the curse of dimensionality. The talk will be about work we have done in this area of statistical inference, and focus on recent work to learn the network structure in dynamical systems using Bayesian hierarchical modeling.